Research On Preemptive Scheduling Of Single-criterion And Two-criteria With Late Work

Scheduling is the issue to reasonable allocation of existing resources according to time order under certain limited conditions for accomplishing a number of given tasks such that one or more criteria reach the ideal or optimal.Scheduling research has important theoretical significance and practical application value.Research on scheduling problems related to the late work criterion is a hot research topic in recent years.In this thesis,we mainly study some preemptive scheduling problems of single-criterion and two-criteria with late work.In Chapter 1,we introduce the background of the scheduling theory and the related notation,terminology and basic rules,and emphatically introduce the scheduling models related to this thesis with the research status.In Chapter 2,we consider the single-machine scheduling problems with release dates of the jobs and forbidden intervals of the machine.The main results are as follows.(a)For problem 1,hm|pmtn|∑Yj,we present an O(n log n+mlogm)-time algorithm and a formula expression for the optimal value.(b)By modifying the release dates and due dates,we show that the two problems 1,hm|rj,pmtn|∑wjYj and 1,hm|rj,pmtn|∑wjUj can be equivalently reduced to 1|rj,pmtn|∑wjYj and l|rj,pmtn|∑wjUj in polynomial time,respectively,and so,can be solved by using the known algorithms in the literature.(c)For the bi-criteria scheduling problems 1,hm|pmtn|{f,g},where(f,g)∈(∑Yj,∑Uj),{∑Yj,∑wjUj),(∑Yj,∑wjYj),we Prove that,for each problem,there is a feasible schedule that is optimal for both criteria.Then solutions for these problems are presented.In Chapter 3,we study some single-machine two-agent Pareto-scheduling problems in which the trade-off curves are piecewise continuous,and provide polynomial-time algorithms to characterize the corresponding trade-off curves,respectively.These problems can be classified as the following two families:(a)1|pmtn|#(fA,∑YjB),where fA∈{∑CjA,LmaxA,∑YjA｝;(b)1|pmtn,pjA=p|#(gA,∑YjB),where gA∈{∑wjACjA,∑jA｝.In Chapter 4,we study the single-machine two-agent,Pareto-scheduling problem l|pmtn|#(∑UjA,∑YjB),in which the Pareto-optimal points are of discrete form.By using multiple composite techniques,we present an O(nnAlognA+nB lognB)-time algorithm to generate all the Pareto-optimal points.