1998
Scheduling with deteriorating jobs to minimize makespan
Publication
Publication
Naval Research Logistics: an international journal p. 511- 523
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 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) time and O(nd(D - d)) space, the other runs in pj)2) time and pj) space
Additional Metadata | |
---|---|
, , , , , | |
doi.org/AID-NAV5%3E3.0.CO;2-6, hdl.handle.net/1765/12337 | |
ERIM Article Series (EAS) | |
Naval Research Logistics: an international journal | |
Organisation | Erasmus Research Institute of Management |
Kubiak, W., & van de Velde, S. (1998). Scheduling with deteriorating jobs to minimize makespan. Naval Research Logistics: an international journal, 511–523. doi:AID-NAV5%3E3.0.CO;2-6 |