Scheduling Problem With Incompatibility Graph Constraint

In this paper,the uniform machine scheduling problem with bipartite incompatibility graph constraint is first studied.Given a bipartite incompatibility graph,the goal is to find a feasible schedule such that the maximum completion time is minimized.We study three cases of four uniform machines with speed ratios of 2:1:1:1,2:2:2:1 and k:k:k:1,and design approximation algorithms,respectively.Then,three identical machines scheduling with incompatible graph constraint is studied,and the corresponding polynomial time optimal algorithms are designed for the caterpillar graph of 0 and 2-branch,the caterpillar graph of 0,1,and 2-branch,the bipartite graph of Δ≤2,and the bipartite graph of Δ≤3.The specific contents of each chapter are as follows.In the chapter 1,we introduce some basic knowledge of scheduling problem,graph theory and approximation algorithm,and summarize the research status of the uniform and identical machine scheduling problem with incompatibility graph constraint.In the chapter 2,we study three cases of four uniform machines with speed ratios of 2:1:1:1,2:2:2:1 and k:k:k:l.By utilizing the property of the maximum independent set on bipartite graph is polynomial-time solvable,the approximation algorithm with ratio 5/4 for the two cases 2:1:1:1 and 2:2:2:1 are designed,and the tight instances are provided.Finally,the approxiamtion algorithm with ratio(3k+1)/(2k+1)+1/k for the case k:k:k:1 is designed.In the chapter 3,we first study three identical machines scheduling problem with 0 and 2-branch caterpillar graph constraint,and a polynomial time optimal algorithm is designed by utilizing the property of the graph is 3-colorable.Then,based on the above result,a polynomial time optimal algorithm is designed similarly for the three identical machines scheduling problem with 0,1,and 2-branch caterpillar graph constraint.Finally,for the three identical machines scheduling problems with the bipartite graph of Δ≤2 and Δ≤3 constraint,we provide two corresponding polynomial time optimal algorithms by utilizing the property of equitable coloring and the independence of K3,3 in bipartite graph.In the chapter 4,we summarize the content of the thesis,and give some relevant analyses and prospects for future research directions.