Algorithms For Parallel Machine Scheduling With Covering Constraints

Parallel machine scheduling has many variants with respect to diferent constraintsand objects. In this paper, we study parallel machine scheduling with cover problem as theconstraints, which is a combination problem of two classical combinatorial optimizationproblems. We discussed about the characteristics of the sub-problems respectively andaggregated them with the special structure of the combination problem to obtain efectiveapproximation algorithms.In this paper, we considered vertex cover and general covering problem as the con-straints. Base on LPT and Local Ratio, we designed a series of approximate algorithms.To Pm|Vertex Cover|Cmax, LLR Algorithm has approximation ratio of (3-2/(m+1)), wherem is the number of machines. And for m=2case, we gave LRBi Algorithm which hasapproximation ratio of2. Then we apply the idea of LLR Algorithm to Pm|X|Cmax, andget LArE algorithm which is (r+max{0,(m-r)/r}) approximate, where r is the approxima-tion ratio of Ar algorithm. At the end, Pm|X|Cmaxwe presented LArE Algorithm, whichcan reach an approximation ratio of (r+∈).The innovation of this paper can be summarized as follows:1. presented a (3-2/(m+1)) approximation algorithm to Pm|Vertex Cover|Cmax.2. combined an idea of enumerating under specified conditions with algorithm de-signing to obtain a better approximation algorithm.3. presented an algorithm with the best approximation ratio to Pm|X|Cmaxwith afixed m.