SCHEDULING DETERIORATING JOBS TO MINIMIZE MAKESPAN

We consider a single-machine problem of scheduling n independent jobs to minimize makespan, in which the processing time of job J(j) grows b y w(j) with each time unit its start is delayed beyond a given common critical date d. This processing time is p(j) if J(j) starts by d. We show that this problem is NP-hard, give a pseudopolynomial algorithm t hat runs in O(nd Sigma(j=1)(n) 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 t his case, we give two pseudopolynomial time algorithms: one runs in O( n(2)d(D - d) Sigma(j=1)(n) p(j)) time and O(nd(D - d)) space, the othe r runs in O(nd Sigma(j=1)(n) w(j)(Sigma(j=1)(n) p(j))(2)) time and O(n d Sigma(j=1)(n) w(j) Sigma(j=1)(n) p(j)) space. (C) 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 511-523, 1998.