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