Scheduling problem with job-independent deterioration rates and linear processing times

This paper considers the scheduling problem with job-independent deterioration rates and linear processing times. We first consider the single machine problem with parallel chain-structured jobs, the objective is to minimize the makespan. For the two cases, where the chains can be interrupted or not, the optimal algorithms are presented. Then for the parallel machine problem to minimize the sum of completion times, we show that an optimal schedule can be obtained by sequencing jobs in non-decreasing order of basic processing times.