Scheduling deteriorating jobs to minimize makespan

Wieslaw Kubiak and Steef van de Velde

Naval Research Logistics (NRL), 1998, vol. 45, issue 5, 511-523

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 \sum^n_{j=1}p_j)$ 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) $ \sum^n_{j=1}p_j)$ time and O(nd(D − d)) space, the other runs in $O(nd \sum^n_{j=1}) w_j(\sum^n_{j=1}$ pj)2) time and $O(nd \sum^n_{j=1} w_j \sum^n_{j=1}p_j)$ pj) space. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 511–523, 1998

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199808)45:53.0.CO;2-6

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:45:y:1998:i:5:p:511-523

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().