Research On Approximation Algorithms For Parallel-machine Scheduling With Job Constraints

Scheduling theory is an important part in the field of combinatorial optimiza-tion and has important theoretical significance and practical application value.Scheduling is actually a kind of decision-making process.In the offline schedul-ing,all the information is known in advance and the scheduler makes decisions with everything known.In the online scheduling,the information of the jobs are released by stages and the scheduler makes decisions only on the basis of known information.We study in this thesis some scheduling problems with job constraints.When jobs are restricted by chain precedence constraints,each chain is a totally ordered set of some jobs and each job can be processed only after all of its predecessors have been completed;When jobs are with weights,the weight of each job represents its priority factor?importance or urgency?;When jobs are with processing set restrictions,each job has a restricted set of machines to which it can be assigned.Moreover,for batch scheduling,a batch machine can process a batch of jobs at the same time.The longest processing lenght of the jobs dictates the processing time of the batch,and the maximum number of jobs that can be processed in each batch is called its batch capacity.When the batch capacity B is not less than the number n of all the jobs,we call it the unbounded batch capacity model;otherwise,we call it the bounded batch capacity model.In Chapter 1,we introduce some preliminary concepts and necessary knowl-edge about scheduling theory.We then give a review for the achievements of scheduling problems related to this thesis.In Chapter 2,we consider the online scheduling with chain precedence con-straints on m parallel machines.Jobs are with identical processing lengths,and the objective is to minimize the maximum completion time.In the literature,a best possible online algorithm is given for the case m=2.We consider the general case that m?3.First,we show that there is no online algorithm which has a competitive ratio less than 1+?_m,where?_mis the unique positive root of?_m²+3?_m-1=0 when 3?m?5 and is the unique positive root of?_m³+4?_m²+5?_m-2=0 when m?6,respectively.Second,we provide a best possible online algorithm matching the low bound.In Chapter 3,we consider the online scheduling with chain precedence con-straints on m bounded batch machines.The batch capacities are bounded and not less than 2.Jobs are with identical processing lengths,and the objective is to minimize the maximum completion time.We show that there is no online algo-rithm which has a competitive ratio less than???,and provide a best possible online algorithm matching the low bound.In Chapter 4,we consider the online scheduling on m uniform batch machines of jobs with weights,where the batch capacities are unbounded B?n.Jobs are with identical processing lengths,and the objective is to minimize the total weighted completion time.For the m uniform machines,the first????2?machines are with speeds s?s?1?,and the other m-?machines are with speeds 1.First,we show that there is no online algorithm which has a competitive ratio less than?=???,respectively.Second,we present a best possible online algorithm matching the low bound.In Chapter 5,we consider the online scheduling on m batch machines of jobs with weights to minimize the maximum weighted flow-time of all jobs.Jobs are with identical processing lengths,and weights in a given range?i.e.,w_j?[1,w]?.When the batch capacities are unbounded B?n,we show that there is no on-line algorithm which has a competitive ratio less than min???,and present a best possible online algorithm matching the low bound.When the batch capacities are bounded and not less than 2,for the case of w=2,we present a best possible online algorithm with a competitive ratio of 2.Furthermore,we consider the bounded batch capac-ities model on a single machine.For the general case that w_j?[1,w],we show that there is no online algorithm which has a competitive ratio less than min???.And we provide an online algorithm,which is showed to be the best possible with a competitive ratio of???when w?[1,2],and to have a competitive ratio not greater than w when w??2,+??.In Chapter 6,we consider two offline scheduling problems of jobs with pro-cessing set restrictions.The batch capacities are bounded,and the objective is to minimize the maximum completion time.For the scheduling on parallel-bath machines with the nested processing set restrictions,we design a strongly polynomial-time algorithm with a worst-case bound of 2 for the case with non-identical batch capacities and a worst-case bound of 2-1/m for the case with identical batch capacities.It is better than a known fast algorithm with a worst case bound of 3-1/m,which only applies to the case with identical batch ca-pacities.For the scheduling on uniform batch machines with the tree-hierarchical processing set restrictions,we design a fast algorithm with a worst-case bound of2 for the case with non-identical batch capacities.It is also better than a known fast algorithm with a worst-case bound of₄⁹,which only applies to the special case with batch machines and the inclusive processing set restrictions.We also provide another fast algorithm with an improved worst-case bound of 2-1/m for the case with identical batch capacities.