Several Results Of Pareto Optimization Scheduling Problems On A Single Machine

A very important issue in the management of production plans is how to efficiently use the finite resources to complete the predetermined production plans so that one or more criteria achieve the optimal or ideal values,in which many problems can be described as scheduling models.When multiple criteria need to be considered in a comprehensive way, seeking all Pareto optimal points and their corresponding Pareto optimal schedules would be an ideal pattern for solving the problem.In this case,we call the problem under research the Pareto optimal scheduling problem.We denote by 1 |β|(f,g)the Pareto optimization scheduling problem for minimizing two objective functions f and f under the rest ricted condition β,where β indicates the job-position constraints or add assumption.The job-position constraint σ(ji)≤ki means that the job Ji can only be processed in the furst ki positions and add assnmption means that n given due dates are assigned to the jobs in any order. Given a faasible schedule π,if there is no feasible schedule σ such that f(σ)≤f(π)and g(σ)≤g(π)where at least oe of the two inequalities is strict,we say that π is a Pareto optimal schedule and(f(π),g(π))is a Pareto optimal point corresponding to π. The goal of the Pareto optimization scheduling problem is to find all Pareto optimal points and,for each Pareto optimal point,a corresponding Pareto optimal schedule.We study in this thesis the followng single-machine Pareto optimization scheduling problems:.The Pareto optimization scheduling problem under the job-position constraints and unit length jobs 1|σ(ji)≤ki,pi=1|(∑in=1,fmax);.The Pareto optimization scheduling problem under the add assumption1 |add| (∑in,Ui,fmax);.The two-agent Pareto optimization scheduling problem under the B-job-position constraints and unit length A-jobs 1|σ(JjB)≤kjB,piA=1|(∑i=1 nAUiA,fmaxB);.The two-agent Pareto optimizatiom scheduling problem under add(A)assumption 1|add(A)|(∑i=1nA UiA,fmaxB);.The Pareto optimization scheduling problem under add(B)assumption 1 |add(B)| (fmaxA,LmaxB).The main results of this thesis are as follows:.Problem 1|σ(Ji)≤ki,pi=1|(∑i=1n Ui,fmax)can be solved in O(n4)time;.Problem 1 | add |(∑in=1Ui,fmax)can be solved in O(n3)time；.Problem 1 | σ(JjB)≤kjB,piA=1 | (∑i=1·An,fmaxB)can be solved in O(n2nA)time；.Problem 1 | add(A) | (∑i=1nA,fmaxB)can be solved in O(n2nA)time:.Problem 1 | add(B) | (fmaxA,LmaxB)can be solved in O(nnA2nB+nAn2BlognB)time.