Λ-Shaped Policies to Schedule Deteriorating Jobs
研究了单机环境下加工时间随开始时间线性增长的恶化作业调度问题，目标是极小化加权完成时间和，发现最优调度呈Λ形，即基本加工时间序列只有一个局部最大值，并给出了O(N log N)的求解算法。
We study a problem of scheduling deteriorating jobs, i.e. jobs whose processing times are an increasing function of their starting times. We consider the case of a single machine and linear job-independent deterioration. The objective is to minimize the sum of weighted completion times, with weights proportional to the basic processing times. The optimal schedule is shown to be Λ-shaped, i.e. the sequence of the basic processing times has a single local maximum. Moreover, we show that the problem is solved in O(N log N) time. In the last section we test heuristics for the case of general weights.