Pareto and scalar bicriterion optimization in scheduling deteriorating jobs

In the paper two problems of a single machine bicriterion scheduling of a set of deteriorating jobs are considered. The jobs are independent, nonpreemptable and are ready for processing at time 0. The processing time pj of each job is a linear function of the starting time Sj of the job, pj=1+αjSj, where Sj≥0 and αj>0 for j=0, 1, …, n. The first problem is to find a schedule which is Pareto optimal with respect to ∑Cj and Cmax criteria. The second problem is to find an optimal schedule subject to the minimization of the criterion in the form of λ∑Cj + (1−λ)Cmax, where λ ∈ [0,1]. There are given necessary and sufficient conditions for a schedule to be Pareto optimal for the first problem. It is proved that there exists 0<λ0<1 such that for all λ∈[0,λ0] the second problem is solvable in O(n log n) time. It is also proved that an optimal schedule for the second problem has a V-shape for all λ∈[λ1,1], where λ0<λ1<1.