Research On Several Kinds Of Pareto Optimization Scheduling Problems On A Single Machine

In the classical scheduling problems, people mainly study one objective function. However, in the practical applications, we usually consider multiple performance indicators, and take trade-off between them. In this case, the ideal situation is to find all Pareto optimal points. Then the production manager can formulate a reasonable production plan according to these Pareto optimal points.With the three-parameter method, the Pareto optimization scheduling problem to minimize two objective functions f and g can be denoted by1‖(f,g). Given a schedule π, we denote by (f(π),g(π)) its objective vector. If there exists no schedule a such that (f(σ))g(σ))≤f(/(π),g(7r)), and at least one of the two strict equalities f(σ)<f(π) and g(σ)<g(π) holds, 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.In this paper, we study the Pareto optimization scheduling problem with two objec-tives on a single machine. The contents in research can be divided into two parts. In the first part, we study the Pareto optimization scheduling problem with a single agent. In the second part, we study the Pareto optimization scheduling problem with two agents.In Chapter2, we study the following two Pareto optimization scheduling problems with a single agent, and present polynomial time algorithms:●The Pareto optimization scheduling problem under the job-position constraints:1σ(Jj)≤kj|(Σn(j=1) Cj,fmax), where σ(Jj)<kj means that job Jj can only be processed in the first kj positions and fmax represents the maximum scheduling cost of the jobs.●The Pareto optimization scheduling problem under the gdd assumption:1|gdd|(Σn(j=1) Tj,fmax), where gdd means that n given due dates d1≤d,2≤…<dn are as-signed to the jobs according to the order of their completion time.In Chapter3, we study the following three Pareto optimization scheduling problems with two agents, and present polynomial time algorithms:●The Pareto optimization scheduling problem under the job-position constraints:1|σJAi)<kAi,σ(JjB)<kjB(Σi=1(nA)CiA,fmaxBwhere σ(JiA)≤kiA means that job JiA can only be processed in the first kiA positions,⊙(JiB)<kjB means that job JjB can only be processed in the first kjBf positions and fmaxB represents the maximum scheduling cost of the B-jobs.●The Pareto optimization scheduling problem under the gdd（A) assumption:1|gdd(A)|(Σ(i=1)(nA) TiA,fmaxB), where gdd(A) means that nA given due dates d1≤d2≤…≤dnA are assigned to the A-jobs according to the order of their completion time.●The Pareto optimization scheduling problem under the gdd(B) assumption:1|gdd(B)|(Σ(i=1)(nA) CiA,LmaxB), where gdd(B) means that nB given due dates d1≤d2≤…≤dnB are assigned to the B-jobs according to the order of their completion time.