SINGLE-MACHINE SCHEDULING TO MINIMIZE TOTAL LATE WORK
成果类型：
Article
署名作者：
POTTS, CN; VANWASSENHOVE, LN
署名单位：
INSEAD Business School
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.3.586
发表日期：
1992
页码：
586-595
关键词：
摘要：
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(n log n) 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.