Some Combination Problems Related To The Parallel Machine Scheduling

Parallel machine scheduling is one of the fundamental combinatorial optimizationproblem, it has been widely studied and many variants have been put forward since1950’s. Though there are a lot of models for parallel machine scheduling problem, acommon aspect is that all jobs should be assigned or otherwise a penalty should be af-ford.Recently, Wang and Cui give out a new thought, they consider a problem whichcan be regard as a combination of a parallel machine scheduling problem and anothercombinatorial problem X, precisely, we only need to assign the jobs corresponding to afeasible solution of X in the parallel machine scheduling problem. They first considerthe combination of parallel machine scheduling problem and vertex cover problem andput forward a3=2/(m+1)approximation algorithm. Then Wang put forward a model ofcombination of parallel machine scheduling problem and a type of minimization problemwhich named a covering problem. Based on Wang’s work, He put forward a model ofcombination of parallel machine scheduling problem and a type of maximization problemwhich named a packing problem. He also give corresponding approximation algorithmfor this problem.In this paper, we give out improved approximation algorithm for the three modelabove, that is the combination of parallel machine scheduling problem and vertex coverproblem, the combination of parallel machine scheduling problem and a covering prob-lem and the combination of parallel machine scheduling problem and a packing problem.Meanwhile we extend the algorithm for the combination of parallel machine schedulingproblem and vertex cover problem to the combination of parallel machine schedulingproblem and hitting set problem. We give out several examples for the the combinationof parallel machine scheduling problem and a covering problem and we also give out reallife application for the problem in this paper.