Given a set of tasks with associated processing times, deadlines and weights unrestricted in sign, we consider the problem of determining a task schedule on one machine by minimizing the sum of weighted completion times. The problem is NP-hard in the strong sense. We present a lower bound based on task splitting, an approximation algorithm, and two exact approaches, one based on branch-and-bound and one on dynamic programming. An overall exact algorithm is obtained by combining these two approaches. Extensive computational experiments show the effectiveness of the proposed algorithm. © 1995.
Minimizing the sum of weighted completion times with unrestricted weights / Dell'Amico M.; Martello S.; Vigo D.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 63:1(1995), pp. 25-41. [10.1016/0166-218X(94)00028-C]
Minimizing the sum of weighted completion times with unrestricted weights
Martello S.;Vigo D.
1995
Abstract
Given a set of tasks with associated processing times, deadlines and weights unrestricted in sign, we consider the problem of determining a task schedule on one machine by minimizing the sum of weighted completion times. The problem is NP-hard in the strong sense. We present a lower bound based on task splitting, an approximation algorithm, and two exact approaches, one based on branch-and-bound and one on dynamic programming. An overall exact algorithm is obtained by combining these two approaches. Extensive computational experiments show the effectiveness of the proposed algorithm. © 1995.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
