The Artifacts Have A Sorting Problem With In-tree Or Chain Constraints

Scheduling theory is an active branch of combinatorial optimization.It originated from manufacturing and has since been extended to more and more high-tech fields.With the intersection and integration of various industries,many production and transportation prob-lems will be used as scheduling problems.The new model has been paid attention and exchanged by experts and scholars.This article mainly discusses several types of schedul-ing problems with in-tree or chains precedence constraint.When considering scheduling problems with these precedence constraints between jobs,we need to pay attention to the position of the jobs in the directed acyclic graph.We address some problems of this model in this thesis and four chapters are considered.In the first chapter,we introduce the basic background,some basic fundamental knowl-edge and symbols of scheduling problems in this thesis.In the second chapter,we consider the two-uniform-machine scheduling problem with in-tree precedence constraints and identical unit processing time.In this problem,jobs have different release dates and the objective is to minimize the makespan.For the NP-hard problem,we first design a branch-and-bound algorithm and give the optimality of the algorithm.Then we use an instance to show how the algorithm works.In the third chapter,we consider the parallel-machine scheduling problem with chains precedence constraints.The objective is to minimize the total weighted completion time.For the given NP-hard problem,we first present one pseudo-polynomial time dynamic program-ming algorithm for the two-identical-machine problem.Then prove that the special case of identical processing times is polynomial solvable.Finally,we extend this algorithm and conclusion to the m-identical-machine scheduling problem and uniform-machine scheduling problem.In the fourth chapter,we consider the single machine scheduling problem with chain precedence constraints and proportionally linear deteriorating jobs,where the processing time of the job is linear function of its starting time,and the objective is to minimize the weighted total completion time.We prove that both the problem with the case that the chain could be interrupted during processing and the problem with the case that non-interruptible are solvable in polynomial time.