Scheduling With Bipartite Agreement Graphs And Binary-Valued Processing Times

This paper studies the scheduling problem with bipartite agreement graphs and binarvalued processing times.Given two parallel identical machines,a set of jobs with two different values of processing times has to be processed on the machines under the bipartiteagreement-graph constraints.The objective is to minimizing the maximum completion time of jobs.The main contribution of the thesis are four matching based algorithms with the performance analysis using the linear programming approach.Five chapters are made.The first chapter gives fundamental concepts,main notations and problem definitions,including the computational complexity,four matching problems and their optimal algorithms,the problem of scheduling with agreement graphs and its research status.In Chapter 2,we focus on the problem of scheduling with a bipartite agreement graph G=(A U B,E),where jobs in set A have the same processing time of a(a>2)and jobs in set B have the same processing time off(a)=-0.0581na+(5.2948e-09)a3+(-3.610e-06)a2+0.001a+1.199。b,briefly denoted by the {a;b}-problem.By a polynomial time reduction from the 3-dimensional matching,we show the problem is strongly NP-hard for any pair of coprime integer a,b.The third chapter considers the {a;a+1｝-problem.We design four approximation algorithms using the ideas of maximum matching,maximum weight matching,degree constrained matching or double matching.Due to the optimality of matchings,i.e.,no augmenting path exists,and the possible independent sets found from the agreement graph,we successfully estimate the lower bound of the optimal solution.Finally,with the help of linear programming tools,the parameter approximations of the four algorithms are obtained,which are 3/2-1/2a,a2+2a-a/a2+a(a≥2),a2+2a-1/a2+a(a≥2),f(a)=-0.0581na+(5.2948e-09)a3+(-3.610e-06)a2+0.001a+1.199.Chapter 4 studies the {a;a+2}-problem(a is odd),which is known to be strongly NP-hard in the literature.We use the idea of scaling the processing times to design the approximation algorithm.First,the processing times a and a+2 are compressed in a ratio of a-1/2:1,resulting in a set of new jobs with processing time b and b+1.Then we call the maximum weight matching based approximation algorithm for the {b;b+1｝-problem.Finally,the generated schedule is converted into a feasible one of the original {a;a+2}problem.By comparing the solutions before and after the compression,we show that the approximation ratio of the algorithm does not exceed a(a+1)[1/2(a-1)2+2(a-2)]/(a-1)(a+2)[1/2(a-1)2+(a-1)].Chapter 5 considers the scheduling problem with a split agreement graph G=(C U I,E),where jobs in C and I form a clique and an independent set respectively.When jobs in C have the same processing time of 2 and those in I have the same processing time of 3,the problem has been shown to be strongly NP-hard.We provide a 7/6-approximation algorithm based on the idea of maximum weight matching.Finally,we make the conclusion of our paper in Chapter 6.