Research On Some Scheduling Problems And Related Games With Set Cover Constraints

Scheduling problem is one of the most classical combinatorial optimization problem.In general,scheduling problem is to design an appropriate processing plan for the given set of jobs on the machines such that those jobs are completed as early as possible.With the depth of research,some complicated models of scheduling problem are characterized clearly which has become the practical hot topic.This topic not only has highly value of theoretic,but also has widely application in real life.This thesis studies the optimization problems related with scheduling,such as scheduling game,traveling salesman problem and scheduling problem with set cover constraints.The first chapter mainly introduces the concepts and basic knowledge which are used in this thesis.Meanwhile,this chapter introduces the related works for the related problems and lists the results that we obtained.Chapter 2 studies two-agent single machine scheduling game problem.In this game,two agents compete to perform their jobs on a common single machine and both of two agents aim to minimize their own total completion time.When one of them has exactly two jobs and all processing times are positive,we show that all the KS-fair schedules can be found in polynomial time and the price of fairness is PoFKS=1/2.Chapter 3 studies the single depot m-Steiner online traveling salesman problem.Under the assumption that the salesmen might encounter some blockages on the roads which are nonrecoverable in a short time.The goal of the Min-Max online m-Steiner traveling salesman problem(MinMax-mSTSPonline)is to find m closed tours that visit each customer at least once such that the maximum cost of the m salesmen is as small as possible.This chapter gives an online algorithm and show that its competitive ratio is at most k-1/m+10 for m≥2 and k+2 for m=1,where k is the number of blockages.This ratio is asymptotically tight since the lower bound for this problem is(?)+1.For Min-Sum online m-Steiner traveling salesman problem(MinSum-mSTSPonline),above algorithm is suitable and the competitive ratio is 5m+k-1.Chapter 4 studies the scheduling problem with set cover constraints.In this scheduling problem,the given set of jobs is corresponding to the collection of sets of set cover problem.The goal of this problem is to choose some jobs that satisfy the set cover constraints for processing.This chapter discusses several types of this problem from different environment and number of machine.A factor fmax+1 approximation algorithm is obtained for arbitrary number unrelated machines,where fmax is the maximum frequency for any element;When the machines are identical,this ratio can be improved to fmax(1+2ε)where ε is an arbitrary positive number.And for the fixed number of machines,a factor α is obtained when the machines are identical where a is the best ratio for set cover problem;When the machines are unrelated,a factor fmax algorithm is presented.Chapter 5 concludes the thesis and provides some related problems for the future researches.