Pareto Optimization Scheduling Problems

Pareto optimization scheduling(also called trade-off scheduling) is an important research direction in scheduling theory. For Pareto optimization scheduling,we need to consider multiple performance indicators and take trade-off between them. Pareto optimization scheduling aims at enumerating all Pareto optimal points and finding a corresponding Pareto optimal schedule for each Pareto optimal point. The characteristics of Pareto optimization scheduling lies in huge theoretical hardness and strong applications. Once we obtain all the Pareto optimal points of a Pareto optimization scheduling problem, the deciders can make effective production schemes based on them. Therefore, our research has important theoretical interest and application prospect.We study in this thesis several Pareto optimization scheduling problems. The thesis consists of six chapters:In Chapter 1, we first introduce the background, development history, common notations and terminologies etc on scheduling theory, and emphatically introduce the fundamental notions and methods on Pareto optimization scheduling.Then we give a review of the related research results.In Chapter 2, we study the Pareto optimization scheduling problem 1|p-batch,b ≥ n|#(Cmax, fmax), and give an O(n4)-time algorithm. We also show that the bound of the number of Pareto optimal points n(n- 1)/2 + 1 established by He et al. [29] is tight by constructing an instance.In Chapter 3, we study the Pareto optimization scheduling problem 1|p-batch,family-job, b ≥ n|#(Cmax, Lmax), and give an O(n2K+1)-time algorithm. When the number K of job-families is a constant, our algorithm is of polynomial-time. We also show that problem 1|p-batch, family-job, b ≥ n|#(Cmax, Lmax) has at most O(nK+1) Pareto optimal points.In Chapter 4, we study the Pareto optimization scheduling problem 1|p-batch,family-job, b ≥ n, rj|#(Cmax, Fmax). When the number of the job-families is arbitrary, we prove that problem 1|p-batch, family-job, b ≥ n, rj|Fmaxis strongly NP-hard. When the number of the job-families is a fixed constant, we give an O(n3K+3)-time algorithm for the Pareto optimization problem 1|p-batch, family-job, b ≥n, rj|#(Cmax, Fmax).In Chapter 5, we study the following five related scheduling problems on a serial-batch machine:(I) 1|s-batch, b < n|#(Cmax, fmax),(II) 1|, s-batch, b =2|Lmax,(III) 1|, s-batch, b = 2|Lmax,(IV) 1|, s-batch, b ≥ n|#(Cmax, fmax),(V) 1|, s-batch, b ≥ n|#(Cmax, Lmax). Concretely, for(I) and(IV), we both give an O(n4)-time algorithm. For(V), we give an O(n2)-time algorithm. Contrastively, we prove that(II) and(III) are both strongly NP-hard.In Chapter 6, we study the scheduling problem 1||#( CA j, fmax), where CAjis the total completion time of all the jobs of agent A, and fmax, called a global criterion, is a maximum cost of all jobs. For this problem, we give an O(n4)-time algorithm, whose running time can be reduced to O(n3log n) when fmax= Lmax. We also show that problem 1||#( CA j, fmax) has at most O(n2)Pareto optimal points.