Single Machine Scheduling with Deteriorating Jobs

In this paper we consider a single scheduling problem with release dates concerning time-deteriorating job processing time, where the processing time of a job is a piecewise linear deterioration function of its starting time. The objective of the problem is to minimize the total completion times of jobs. This problem is strongly NP-hard since it is a generalization of the single-machine total completion times 1|r|SigmaC_j. We develop the first implementation of the Lagrangian relaxation (LR) for the problem under study. A shorten time horizon strategy is derived to speed-up implementing algorithm of LR. The extensive computational experiments are carried out and the computational results demonstrate that the proposed method is highly effective for our problem in a relatively short computation time.