Two Parallel Dedicated Machine Scheduling Problems With Conflict

This thesis focuses on scheduling with conflict constraints for processing jobs.Consider the environment of two parallel dedicated machines,where each job is pre-assigned to a machine,the conflicts can be described by a bipartite graph.The problem of minimizing the maximum completion time of jobs is strongly NP-hard,even when the sequence of jobs on one machine is given in advance.This thesis contributes to this strongly NP-hard variant by providing its first approximation algorithm.The algorithm is mostly based on the LPT rule and has a worst case ratio of 35.We also discuss the computational complexity of other variants with different conflict graphs.Four chapters are made.In Chapter 1,we first define the scheduling problem,the concepts of approximat ion algorithm and computational complexity.Then we introduce parallel dedicated machines and the conflict constraints.Finally,we review the previous study on scheduling.Chapter 2 considers two parallel dedicated machines scheduling with conflict constraints.When the sequence of jobs on the first machine is fixed,we utilize the classical LPT rule to design a polynomial time algorithm.In addition,we prove it turns out to be a 5/3-approxiamtion and confirm the tightness.In Chapter 3,we first observe two variants of two parallel dedicated machines scheduling,the variant with an additional constraint that the maximum degree of jobs(vertices)on the second machine is at most 1 and that the processing of jobs on the first machine is given in advance.By polynomially reducing the variants to the Partition problem,we prove that the former is NP-hard and the latter cannot be approximated within any constant ratio.Moreover,we show that the latter problem cannot be approximated within the worst case ratio k(10)3)2(if the maximum degree of jobs(vertices)on the second machine is no more than k.Chapter 4 summarizes the full thesis.