A Study Of Two Proportionate Scheduling Problems

In this thesis, we mainly study about two types of two-stage proportionate shop scheduling problems. One is two-stage proportionate hybrid flow shop scheduling problem. The other is two-stage proportionate hybrid open shop scheduling problem. We design corresponding approximation algorithm for each problem and analyze worst-case performance ratio of the algorithm. The remainder of this thesis is organized as follows:In section1, we briefly introduce some concepts and theoretical foundation of the scheduling problem.In section2, we study a two-stage proportionate hybrid flow shop scheduling problem arising from data transmission in the network. By using the three-field representation, the problem can be denoted as HFS(2,m)|p;j=pj IC max. The jobs should be non-preemptively processed through two stages(denoted by stage1and stage2) in series where stage1has two identical parallel machines and stage2has m identical machines. The processing times of each job at both stages are identical, we present a polynomial time approximation algorithm for m=2. And the worst-case performance ratio of the algorithm is shown to be4/3and the bound is tight. At the same time, we present a polynomial time approximation algorithm with a worst-case performance ratio of3/2for m≥3.In section3, we study a two-stage proportionate hybrid open shop scheduling problem arising from parallel data processing. By using the three-field representation, the problem can be denoted as O2(m1,m2)|pij=pj|Cmax,. The jobs must be non-preemptively processed arbitrarily through two stages at different time slots, where stage1has m1identical parallel machines and stage2has m2identical machines. The processing times of each job at both stages are identical. We prove that the new problem with min{m1,m2}≥2is a NP-hard by polynomial time reduction method. We then present a polynomial time approximation algorithm with the worst-case performance ratio of (3/2)3/[2(2min{m1,m2}+1]. In addition, we illustrate that the algorithm is optimal for the problem when min{m1,m2}=1. Finally, we make an improvement via improving the scheduling of the jobs in the first stage, because we find theworst-case performance ratio of the algorithm is depended on the algorithm used in the firststage.The fourth section, we make conclusion of the whole thesis and provide future work.