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 00. The processing time pjpj of each job is a linear function of the starting time SjSj of the job, pj=1+αjSjpj=1+αjSj, where Sj⩾0Sj⩾0 and αj>0αj>0 for j=0,1,...,nj=0,1,...,n.The first problem is to find a schedule which is Pareto optimal with respect to ΣCjΣCj and CmaxCmax criteria. The second problem is to find an optimal schedule subject to the minimization of the criterion in the form of λΣCj+λΣCj+(1-λ)Cmax(1-λ)Cmax, where λ∈[0,1]λ∈[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<10<λ0<1 such that for all λ∈[0,λ0]λ∈[0,λ0] the second problem is solvable in O(nlogn) time. It is also proved that an optimal schedule for the second problem has a V-shape for all λ∈[λ1,1]λ∈[λ1,1], where λ0<λ1<1λ0<λ1<1.Scope and PurposeTime-dependent scheduling and bicriterion scheduling are today subjects of intensive research. The main motivation for studying such problems is the important role they play in many applications. In the paper we consider two problems of a single machine bicriterion scheduling of a set of deteriorating jobs. The processing time of each job is a linear function of the starting time of the job. The first problem is to find a Pareto optimal schedule with respect to the total completion time and the maximum completion time criteria. The second problem is to minimize a convex combination of the above two criteria. We give necessary and sufficient conditions for a schedule to be Pareto optimal for the first problem and prove several theorems concerning the form of an optimal schedule for the second problem.