Single machine scheduling to minimize total weighted late work

Single machine scheduling to minimize total weighted late work

0.00 Avg rating0 Votes
Article ID: iaor19982696
Country: United States
Volume: 7
Issue: 2
Start Page Number: 232
End Page Number: 242
Publication Date: Mar 1995
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: programming: dynamic, programming: branch and bound
Abstract:

In the problem of scheduling a single machine to minimize total weighted late work, there are n jobs to be processed for which each has an integer processing time, a weight and a due date. The objective is to minimize the total weighted late work, where the late work for a job is the amount of processing of this job which is performed after its due date. An O(n log n) algorithm is derived for the preemptive total weighted late work problem. For non-preemptive scheduling, efficient algorithms are derived for the special cases in which all processing times are equal and in which all due dates are equal. A pseudopolynomial algorithm is presented for the general non-preemptive total weighted late work problem. Also, a branch and bound algorithm in which lower bounds are obtained using the dynamic programming state-space relaxation method is proposed for this general problem. Computational results with the branch and bound algorithm for problems with up to 700 jobs are given.

Reviews

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