The Parallel Machine Scheduling Problem With Graph Constraints

In this thesis,we consider the parallel machine scheduling problem with graph constraints,i.e,the identical parallel machine scheduling problem with tree structure or path constraints,and the unrelated parallel machine scheduling problem with graph covering constraint.The first problem is described as follows:Given an undirected graph G(or directed graph D,respectively)and a set of jobs,where the set of jobs corresponds to the set of edeges of the undirected graph G(or the set of arcs of the directed graph D).The goal is to select a subset of jobs that satisfies the given requried property which is the tree structure or path constraints,and then execute the jobs chosen on the identical parallel machines to minimize the makespan.The second problem is described as fol-lows:Given an undirected graph G and a set of jobs,where the set of jobs corresponds to the union of set of edeges and set of vertices of G,we need to select a subset of jobs that satisfies the graph covering constraint,and then execute the jobs chosen on the unrelated parallel machines to minimize the makespan.For the two problems mentioned-above,we get the following results:(1)When the jobs chosen is consisted of the K-tree in G or the single-source shortest paths tree in D,each of which has an efficient polynomial-time approximation scheme(EPTAS)with time complexity f(1/?)+ O(k2),where f/(1/?)is doubly exponential in 1/?;(2)When the jobs chosen is consisted of the path between two fixed vertices s and t in G,we design a(2-1/n)-approximation algorthm TVP,and its complexity is O(k(n2,k));especially,with the constraint of the shortest paths between two fixed vertices in D,we also present a 1.618-approximation algorithm SPP and the algorithm runs in time O(n2+k(n2+klog k));(3)We design two approximation algorithms GCR and GCRm to solve the unrelated parallel machine scheduling problem with graph covering constraint,where an algorithm GCR is a 4-approximation algorithm for the case that the number of unrelated parallel machines is not fixed,and other algorithm GCRm is a 3-approximation algorithm for the case that the number of unrelated parallel machines is fixed.Where n is the number of vertices,m is the number of machines and k is the number of jobs.