A Study On Two Parallel Machines Scheduling With A Conflcit Graph

This thesis studies parallel machines scheduling with process conflicts,where a process conflict is referred to as two jobs that cannot be processed concurrently due to their competition for the same non-shareable resource.Such conflicts are usually defined by a simple graph named the conflict graph.In this thesis,we consider only the conflict graph whose complement(known as the agreement graph)is a bipartite graph,denoted by G=(A U B,E).For scheduling jobs of processing time 1,2,3 or 4 on two parallel identical machines to minimize the makespan,we propose an idea of algorithms utilizing the maximum(weight)matchings and a linear programming approach for the worst case analysis of algorithms.We make seven chapters as follows.In the first chapter,we define the problem formally,and introduce useful algorithms,concepts and notations,including the scheduling model under conflict graphs,matchings and their algorithms,and the theory of approximation algorithms and computational complexity.In the second chapter,we first provide a full review of scheduling with a conflict graph.Then we give a strong NP-hardness proof for the {a,b;rab}-problem where jobs in set A have processing time either a or b while jobs in set B have the same processing time of rab(Note we take in what follows the same notation and definition).Here a,b,r are all positive integers and a,b are coprime.In the third chapter,we focus on the {2,3;1,4}-problem.This problem has been shown to be APX-hard but no better approximation algorithms were found except the only 3/2-approximation algorithm,LS,that was designed for general conflict graphs without restrictions on the processing times.We first assign weights to the edges of the bipartite graph and compute the maximum weight matching;then adjust the maximum weight matching into a specific structure in polynomial time and construct the auxiliary bipartite graph between the edges in the matching and the isolated nodes;finally compute the maximum matching of the auxiliary bipartite graph and construct a feasible schedule from the two matchings.We show that the so-designed double-matching based approximation algorithm must have a worst case ratio between 13/9 and 19/13.The next chapter studies the {1,3;2}-problem,which has been shown strongly NPhard and can be approximated within 4/3(the 4/3-approximation for the {1,2,3}-problem under a general conflict graph).To improve the algorithm,we design a similar doublematching based algorithm as that for the {2,3;1,4}-problem.The difference is that in the first step we have to divide each job with processing time 3 into a job with processing time 1 and a job with processing time 2,then modify the original conflict graph accordingly,assign weights to the edges and finally compute the(first)maximum weight matching.We prove such modification can give an approximation algorithm with worst case ratio between 6/5 and 409/313≈1.307 for the {1,3;2}-problem.In the fifth chapter,we consider the {1,2;4}-problem.We design an approximation algorithm that takes the idea of division plus double-matching similar to that for the{1,3;2}-problem.Its worst case ratio is shown to be in the interval[11/8,10/7].Finally,the sixth chapter studies the case where jobs have different release times.When the processing times equal either 1 or 2,and the release times are either 0 and r,the problem is known to be strongly NP-hard.By constructing an edge-weighted auxiliary graph and computing the maximum weight matching for the graph,we obtain an approximation algorithm with worst case ratio 3/2 for this problem.The seventh chapter summarizes the thesis and gives some potential research issues.