Approximation Algorithms For Two Scheduling Problems

This paper studies two off-line scheduling problems, which are two-machine flowshop scheduling problems with setup time and group technology and a single machine scheduling problem with maintenance.This paper includes three chapters. In chapter 1, we introduce basic definitions and notations of combinatorial optimization, scheduling problems and algorithm, worst-case ratio. In chapter 2, we consider two-machine flowshop scheduling problems with group technology, where set-up time is needed from one group to other group. For the problem F₂ |S,GT W_ijC_ij , an approximate algorithm withworst-case ratio 2 is presented. For the on-line problem F₂|S,GT|C_max, anapproximate algorithm with competitive ratio 2 is also proposed while it can be proved that there is not online approximation algorithm with competitive ratio less than 2. In chapter 3, we study a single machine scheduling problem with maintenance under the objective function of minimizing total completion time. The best approximation algorithm in literature is MSPT with worst-case ratio 20/17. Based on the idea of local search, we generalize 2-OPT operation proposed in literature to k, k - exchange operation. With new operation, we present a polynomial time approximation scheme for the considered problem, which greatly improves the known result.