Scheduling Problems About Order And Parallel Machines

Scheduling is an important part of combinatorial optimization which is widelyused in computer system, transports, production management and other sectors.Order scheduling is a profound practical scheduling model. In this paper wemainly deal with its computational complexity. In recent years, with the need ofproduction, people pay more attention to chain precedence constraints schedulingand semi-online scheduling. We also consider these two scheduling problems onparallel machines in the paper.The thesis is organized as follows.In the first chapter, we give an introduction of the basic knowledge aboutscheduling, semi-online scheduling and the main research results obtained in thisthesis.In the second chapter, we study scheduling problem of minimizing the rangeof order completion times with multiple job classes. We prove that the schedulingproblem is N P hard and present a branch and bound algorithm.In the third chapter, we study the problem of scheduling four chains on threeidentical parallel machines. We explain the NP-hardness of this problem, whichcomputational complexity is characterized by giving a pseudo-polynomial timealgorithm and a F P T AS.In the fourth chapter, we study the semi-online scheduling problem on twouniform machines with set-up time. We present an algorithm and the correspond-ing competitive ration for the considered problem.