Preemptive scheduling with simple linear deterioration on a single machine

In this paper we study the problem of scheduling n deteriorating jobs with release dates on a single machine. The processing time of a job is assumed to be the product of its deteriorating rate and its starting time. Precedence relations may be imposed on the set of jobs. Unlike the classical time-dependent scheduling problems, we assume that the execution of a job can be preempted in the sense that the job’s deteriorating rate is reduced when it is preempted and each continuously processed part of a job can be regarded as an independent job with a specified deteriorating rate. The objective is to minimize some common regular scheduling performance measures. We first show that minimizing a class of regular symmetric functions is polynomially solvable. Then we construct an O(n2) algorithm for minimizing the maximum job completion cost with or without precedence constraints. Finally we show that minimizing the total weighted completion time is NP-hard even if there are only two distinct release dates.