ℝà-Shaped policies to schedule deteriorating jobs

This paper studies a problem of scheduling deteriorating jobs, i.e. jobs whose processing times are an increasing function of their starting times. It considers the case of a simple 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, the paper shows that the problem is solved in O(NlogN) time. In the last section heuristics are tested for the case of general weights.