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.
Dell'Amico M., Martello S., Vigo D. (1995). Minimizing the sum of weighted completion times with unrestricted weights. DISCRETE APPLIED MATHEMATICS, 63(1), 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.
