Given a set of tasks with associated processing times, deadlinesand weights unrestricted in sign,we consider the problem of determining a task schedule on one machineby 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 basedon branch-and-bound and one on dynamic programming. An overall exact algorithmis obtained by combining these two approaches. Extensive computationalexperiments show the effectiveness of the proposed algorithms.
Minimizing the Sumof Weighted Completion Times with Unrestricted Weights / Dell'Amico, Mauro; S., Martello; D., Vigo. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 63:(1995), pp. 25-41.
Minimizing the Sumof Weighted Completion Times with Unrestricted Weights.
DELL'AMICO, Mauro;
1995
Abstract
Given a set of tasks with associated processing times, deadlinesand weights unrestricted in sign,we consider the problem of determining a task schedule on one machineby 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 basedon branch-and-bound and one on dynamic programming. An overall exact algorithmis obtained by combining these two approaches. Extensive computationalexperiments show the effectiveness of the proposed algorithms.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
