Single machine scheduling to minimize total late work

Single machine scheduling to minimize total late work

0.00 Avg rating0 Votes
Article ID: iaor1993114
Country: United States
Volume: 40
Issue: 3
Start Page Number: 586
End Page Number: 595
Publication Date: May 1992
Journal: Operations Research
Authors: ,
Keywords: programming: dynamic, programming: integer
Abstract:

In the problem of scheduling a single machine to minimize total late work, there are n jobs to be processed for which each has an integer processing time and a due date. The objective is to minimize the total late work, where the late work for a job is the amount of processing of this job that is performed after its due date. For the preemptive total late work problem, an O(nlogn) algorithm is derived. The nonpreemptive total late work problem is shown to be NP-hard, although efficient algorithms are derived for the special cases in which all processing times are equal and all due dates are equal. A pseudopolynomial dynamic programming algorithm is presented for the general nonpreemptive total late work problem; it requires O(nUB) time, where UB is any upper bound on the total late work. Computational results for problems with up to 10,000 jobs are given.

Reviews

Required fields are marked *. Your email address will not be published.