Flow-shop Scheduling Problem For Unit Jobs Under Precedence Constraints

Scheduling is an old and vibrant combinatorial optimization problem.The concepts of dependent jobs were introduced as soon as the field was formed,among which,jobs' process order precedence constraint is a typical one.This thesis studies flow-shop scheduling with precedence constraints.The goal is to minimize the maximum completion time of jobs.For the case of unit-job scheduling where all jobs have the same processing times,the solution of scheduling is related to the layering of the precedence graph.And different layering algorithms can bring different scheduling algorithms,which was rarely seen in previous study.The main contribution of this thesis is a 5/3-approximation algorithm for three-machine flow shop scheduling,which is mainly by the natural layering of the precedence graph.The ratio is further improved to a tight one of 3/2 if the precedence graph is structured as the longest chains(Longest Chain Graph,LCG).In addition,an improved layering of the precedence graph is provided,which implies an improved algorithm for the scheduling problem too.All the above results can apply to any number of flow-shop machines.For easy elaboration,we divide the full text into five chapters of the following.Chapter 1 first defines scheduling problems and gives some concepts on computational complexity and approximation algorithms.Then,it introduces precedence constrains and precedence graphs of various types.In Chapter 2,we review the research of scheduling with precedence constraints,including the results of computational complexity and approximation algorithms on different precedence graphs,with different objective functions and under different machine environments.Additionally,we are noticed that many problems,including ours,are still open.Chapter 3 mainly studies three-machine flow-shop scheduling for unit jobs with precedence constraints.The objective is to minimize the maximum completion time of jobs.Firstly,the structure of optimal schedules and the lower bound of optimal solutions are analyzed,and an approximation algorithm with a worst case ratio of 5/3 is presented through the natural layering of the precedence graph.Then for the LCG graph,an additional matching between agreeable jobs and the layers are provided,which implies animproved 3/2-approximation algorithm.Finally,our instance shows that the bound 3/2 is tight.In Chapter 4,the precedence graph is divided into LCG and a residual sub-graph,and vertices(jobs)in the residual sub-graph are matched with the complete bipartite sub-graphs of LCG.As a result,we obtain a new layering algorithm as well as a new scheduling algorithm.Properties of the new algorithm and the optimal solutions are further discussed.Finally,Chapter 5 summarizes the full thesis,and conjectures the worst case ratio of the algorithm proposed in Chapter 4,as well as the proof idea.