Research On Computational Complexity Of Some Newly Developing Scheduling Problems

Scheduling is the issue to allocate limited resources under certain conditions for accomplishing one or more tasks such that one or more objectives are ideal or optimal.The quality of the scheduling immediately affects the costs and profits of manufacturer.Thus,scheduling theory plays an important role in efficiency improvement,scientific decision,resource development,configuration,and so on.In the scheduling theory,tasks are called jobs and resources are called machines.In this thesis,we study the computational complexity of several newly developing scheduling problems.In chapter 2,we study the single-machine scheduling with generalized or assignable due dates.Under the assumption of generalized due dates,the due dates are sequenced in the EDD order and assigned to the jobs by the increasing order of their completion times so that the i-th completed job receives the i-th due date.Alternatively,under the assumption of assignable due dates,the due dates are assigned to the jobs independently.We prove that two open problems 1|GDD| ?(Ei+ Ti)and 1|ADD| ?(Ei +Ti)have no approximation algorithm with a constant performance ratio.Our proof also means that these two prob-lems are unary NP-hard.Furthermore,we also prove that the open problem 1|GDD| ?wiTi is unary NP-hard.In chapter 3,we study the Pareto scheduling with due-index constraints on a single machine.First,we amend some deduction flaws in the literature.Then for problem 1|?[Jj]?kj,prec|?(fmax,gmax),where "?[Jj]?kj" means that job Jj can only be processed in the first kj positions and "prec" denotes the precedence constraints,we present an O(n4)-time algorithm.As a consequence,we further show that the two-agent problem 1| ?[Jj]?kj,prec|#(f/maxA,gmaxB)is solvable in O(nA3nB+nAnB3)time.In chapter 4,we study the unbounded parallel-batch scheduling with drop-line jobs,where for drop-line jobs,we mean that the completion time of each job is equal to the sum of the starting time of the batch containing the job and the pro-cessing time of the job.First,we show that problem p-batch(+?)|drop-line,rj|Lmax is binary NP-hard.Furthermore,we prove that,for every ? ?(fmax,?fj),problem p-batch(+?)|drop-line,rj|-? is binary NP-hard,is solvable in pseudo-polynomial time,and is solvable in polynomial time when either the number of distinct processing times or the number of distinct release dates is a constant.In chapter 5,we study the unbounded parallel-batch scheduling with the jobs having agreeable release dates and processing times.We consider two type-s of jobs:batch jobs and drop-line jobs.For batch jobs,the completion time of a job is given by the completion time of the batch containing this job.For the bi-criteria problem p-batch(+?))|?*,(rj.pj)-agreeable|#(Cmax,fmax),where?*?(batch,drop-line),we present an O(n3 log(rmax + ?pj))-time algorithm and an O(n4)-time algorithm.For the single-criteria problem p-batch(+?)|?*,(rj,pj)-agreeable|?wjUj,we prove that the problem is binary NP-hard,and has a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme.In chapter 6,we study the two-agent scheduling on a parallel-batch machine to minimize makespan,where the jobs are batch jobs,and have release dates and linear deteriorating processing times.The objective is to minimize the makespan of agent A with the makespan of agent B being bounded.Tang et al.[144]presented comprehensive research for this scheduling model.Especially,they p-resented polynomial-time algorithms for the following four problems.In the first problem,the batch capacity is unbounded and the two agents are compatible.In the second problem,the batch capacity is bounded,the two agents are incompat-ible,the A-jobs have a fixed number of normal processing times,and the B-jobs have a common release date.In the third and forth problems,the batch capaci-ty is bounded,the two agents are compatible,and the release dates and normal processing times are either agreeable or reversely agreeable.In this chapter,we show that their algorithms for the four problems are all invalid.We present a new polynomial-time algorithm for the first problem and show that the other three problems are binary NP-hard.We also present a pseudo-polynomial-time algorithm for the version where the batch capacity is bounded,the two agents are incompatible,and the A-jobs and the B-jobs have their common release dates,respectively.We finally present a strongly polynomial-time algorithm for the ver-sion where the batch capacity is unbounded and the two agents are incompatible.