Scheduling deteriorating jobs to minimize makespan

Scheduling deteriorating jobs to minimize makespan

0.00 Avg rating0 Votes
Article ID: iaor19991780
Country: United States
Volume: 45
Issue: 5
Start Page Number: 511
End Page Number: 523
Publication Date: Aug 1998
Journal: Naval Research Logistics
Authors: ,
Keywords: programming: dynamic, programming: branch and bound
Abstract:

We consider a single-machine problem of scheduling n independent jobs to minimize makespan, in which the processing time of job Jj grows by wj with each time unit its start is delayed beyond a given common critical date d. This processing time is pj if Jj starts by d. We show that this problem is NP-hard, give a pseudopolynomial algorithm that runs in O(nd Σnj=1 pj) time and O(nd) space, and develop a branch-and-bound algorithm that solves instances with up to 100 jobs in a reasonable amount of time. We also introduce the case of bounded deterioration, where the processing time of a job grows no further if the job starts after a common maximum deterioration date D > d. For this case, we give two pseudopolynomial time algorithms: one runs in O(n2d(D – d) Σnj=1 pj) time and O(nd(D – d)) space, the other runs in O(nd Σnj=1 wjnj=1 pj)2) time and O(nd Σnj=1 wj Σnj=1 pj) space.

Reviews

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