An approximation algorithm for proportionate scheduling in the two-stage hybrid flow shop

• We consider a two-stage proportionate hybrid flow shop scheduling problem arises from data transmission in computer networks.
• A approximation algorithm is presented for the case when two identical machines at one stage and m identical machines at the other stage.
• We prove that the worst case ratio of the algorithm is at most 3/2 for any m≥2m≥2.
• We also show that the tight bound of the algorithm is 4/3 when m=2m=2.

In the hybrid flow shop, jobs are subjected to process through stages in series as in the classical flow shop, while each stage contains one or more identical machines. This paper mainly studies the scheduling problem in the two-stage hybrid flow shop, namely the proportionate scheduling. In such problem, it is assumed that each job has the same processing time in different stages. The objective of minimizing the makespan is considered. If there are two machines in the first stage and m machines in the second, then an approximation algorithm with worst case ratio no more than 3/2 is provided. If each stage consists of only two machines, we show that the tight bound of our algorithm can be reduced to 4/3.