Scheduling deteriorating jobs to minimize makespan
研究了单机环境下作业加工时间随开工延迟而增长的调度问题，目标是极小化最大完工时间，给出了伪多项式算法和分支定界算法，可求解多达100个作业的实例。
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. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 511–523, 1998