Research On Parallel Machine Scheduling Problem With Vertex Covering Constraints

The scheduling problem is to allocate and arrange the jobs and machines according to the time under certain constraints,so that one or some goals can reach the optimal.Vertex cover is a set of vertices that satisfy all edges on the overlay graph.The concept of combination of combinatorial optimization problems was first proposed by Wang and Cui.Epstein and others gave a 2+? approximation algorithm for the combination problems of point set covering and parallel machine sequencing.This approximation factor should be a better approximation so far.The classical scheduling problem is to find an allocation scheme given m parallel machines and n jobs,so that the overall completion time can be as small as possible after the n jobs are allocated to m machines.If the processing time of each job satis-fies certain conditions,the classical scheduling is expected to get the optimal allocation scheme effectively in polynomial time.Most of the vertex covering problems are solved by the framework of Local Ratio.It is a new research direction to combine two com-binatorial optimization problems.At the same time,it provides a new idea to study a kind of combinatorial optimization problems with multi-layer structure.This thesis presents a new algorithm for the classical parallel machine scheduling problem.In fact,this algorithm is a polynomial time algorithm for solving the classical parallel machine scheduling problem where the processing time satisfies the integer division relation.We find that there are two versions of the new algorithm.In this thesis,we consider two versions of the new algorithm and obtain approximate ratios of 3/2 and 2-(1/2~q)(q?Z+)respectively.The compact example shows that the analysis of the two versions of the new algorithm is tight.In addition,this thesis introduces some results of weak vertex covering problems on some special graphs and combinatorial problems on some special graphs.At the same time,it gives some algorithms and examples of parallel machine scheduling problems with covering constraints.This thesis also gives some practical application background of these problems.