Research On Single-machine Scheduling With Positional Due-indices And Completion-time Deadlines On The Jobs

Owing to the importance of scheduling in operational research,scheduling problems have drawn attentions of a lot of scholars from various perspectives.In order for scheduling to be in touch with reality,many scheduling models have been widely studied by scholars,such as multi-agents scheduling,multi-criteria scheduling,and scheduling under constraints.In the scheduling theory,"jobs" are usually used to denote tasks or orders,and "machines" are usually used to denote resources.In this thesis,we consider the single-machine scheduling with positional due-indices and completion-time deadlines on the jobs,where the positional due-index kj of job Jj means that job Jj must be processed in the first kj positions,and the completion-time deadline dj of job Jj means that job Jj must be completed by time dj.In Chapter One,we introduce the background knowledge of scheduling the-ory,together with some related notation and terminology.In particular,we em-phatically introduce the scheduling models and give a review of the achievements of scheduling problems corresponding to this thesis.In Chapter Two,we consider the single-machine scheduling problems with positional due-indices and completion-time deadlines.When the problem 1|kj,dj|f is solvable in polynomial time,we show that the Pareto scheduling problem 1|kj,dj|#(Lmax,(V),f)can be also solved in polynomial time,where f is an arbi-trary regular function.Moreover,we also study the scheduling model for linear-deteriorating jobs,and show that each of the considered problems can be solved in polynomial time.In Chapter Three,we consider the scheduling problems with positional due-indices on a single machine.When the processing times of jobs are of linear-deteriorating,by applying Lawler's rule in section 2.3 and the expended Smith's rule,we present polynomial algorithms for problems 1|rj,kj,prec,pj(t)=?j(a+bt)|f,where f?{Cmax,Tmax,Tmax,Lmax,WCax,fmax,Fmax}.When processing times of the jobs have no deterioration,we also present some new NP-hardness re-sults,i.e.,the unary hardness results of problems 1|rj,pj=?j|WCmax,1|rj,pj=?j,chains|Fmax,and 1|kj,pj=?j| ?Uj.When we study the ND-agent model,we present an O(n4)-time algorithm for the Pareto scheduling problem 1|ND,kj,pj(t)=?j(a+bt)|#(?Cj(A),fmax(B),where "ND" denotes the non-disjoint agents.Further-more,we also consider the positive-combination scheduling problem and the hi-erarchical scheduling problem related to the two criteria ?Cj and ??jVj.For this two types of bicriteria scheduling problems,we present the corresponding polynomial-time algorithms,respectively.In Chapter Four,we consider the scheduling problems with completion-time deadlines on a single machine.We show that the two open problems 1|dj|?Tj and 1|rj,dj,pmtn|?Cj are unary NP-hard,respectively.For prob-lem 1|CO|?Cj(A):?Uj(B)?Q,we amend some deduction flaws for the bi-nary NP-hardness proof in the literature,and show that problem 1|CO,pj(A)=p(A)|?Cj(A):?Uj(B)?Q is binary NP-hard,where "CO" denotes the com-petitive agents.We also consider the scheduling problems with the number of position-violated jobs criterion under the completion-time deadline restriction.For problem 1|dj|?Vj,we show that it is unary NP-hard,and for two special versions of this problem,we present an O(n2)-time algorithm and an O(n log n)-time algorithm,respectively.Furthermore,we firstly investigate the scheduling problems with the late work criterion under the completion-time deadline restric-tion.When the jobs have the same due date,we show that 1|dj=d,dj|??jYj is binary NP-hard and it can be solved in pseudo-polynomial time.The two results indeed show that 1|dj=d,dj | ??jYj is binary NP-hard.We also present a fully polynomial-time approximation scheme for 1|dj=d,dj|??jYj.And when all the jobs have a unit weight,we show that 1|dj|?Yj is unary NP-hard.