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 p(j) of each job is a linear function of the starting time S-j of the job, p(j) = 1 + alpha S-j(j), where S-j >=, 0 and alpha j > 0 for j = 0, 1,..., n. The first problem is to find a schedule which is Pareto optimal with respect to Sigma C-j and C-max criteria. The second problem is to find an optimal schedule subject to the minimization of the criterion in the form of lambda Sigma C-j + (1-lambda)C-max where lambda is an element of [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 < lambda(0) < 1 such that for all), E [0, 0] the second problem is solvable in 0(n log n) time. It is also proved that an optimal schedule for the second problem has a V-shape for all A E [lambda(1), 1], where lambda(0) < lambda(1) < 1.