Abstract
We consider a two-stage flexible flow shop problem with a single machine at one stage and m identical machines at the other stage, where the processing times of each job at both stages are identical. The objective is to minimize the makespan. We describe some optimality conditions and show that the problem is NP-hard when m is fixed. Finally, we present an approximation algorithm that has a worst-case performance ratio of \(\frac{5}{4}\) for m=2 and \(\frac{\sqrt{1+m^{2}}+1+m}{2m}\) for m≥3.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326
Hoogeveen JA, Lenstra JK, Veltman B (1996) Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. Eur J Oper Res 89:172–175
Huang YM, Shiau DF (2008) Combined column generation and constructive heuristic for a proportionate flexible flow shop scheduling. Int J Adv Manuf Technol 38:691–704
Jansen K, Sviridenko MI (2000) Polynomial time approximation schemes for the multiprocessor open and flow shop scheduling problem. Lect Notes Comput Sci 1770:455–565
Koulamas C, Kyparisis GJ (2007) A note on performance guarantees for sequencing three-stage flexible flowshops with identical machines to minimize makespan. IIE Trans 39:559–563
Lee CY, Vairaktarakis GL (1994) Minimizing makespan in hybrid flowshop. Oper Res Lett 16:149–158
Linn R, Zhang W (1999) Hybrid flow shop scheduling: a survey. Comput Ind Eng 37:57–61
Ow PS (1985) Focused scheduling in proportionate flowshops. Manag Sci 31:852–869
Pinedo M (2008) Scheduling: theory, algorithms and systems, 3rd edn. Springer, Berlin
Riane F, Artiba A, Elmaghraby SE (1998) A hybrid three-stage flowshop problem: efficient heuristics to minimize makespan. Eur J Oper Res 109:321–329
Ribas I, Leisten R, Framinan JM (2010) Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Comput Oper Res 37(8):1439–1454
Ruiz R, Antonio J, Rodriguez V (2010) The hybrid flow shop scheduling problem. Eur J Oper Res 205:1–18
Schuurman P, Woeginger GJ (2000) A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem. Theor Comput Sci 237:105–122
Sevastyanov SV (2008) An improved approximation scheme for the Johnson problem with parallel machines. J Appl Ind Math 2(3):406–420
Shakhlevich N, Hoogeveen H, Pinedo M (1998) Minimizing total weighted completion time in a proportionate flow shop. J Sched 1:157–168
Shiau DF, Cheng SC, Huang YM (2008) Proportionate flexible flow shop scheduling via a hybrid constructive genetic algorithm. Expert Syst Appl 34:1133–1143
Soewandi H, Elmaghraby SE (2001) Sequencing three-stage flexible flowshops with identical machines to minimize makespan. IIE Trans 33(11):985–994
Thornton HW, Hunsucker JL (2004) A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage. Eur J Oper Res 152:96–114
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Choi, BC., Lee, K. Two-stage proportionate flexible flow shop to minimize the makespan. J Comb Optim 25, 123–134 (2013). https://doi.org/10.1007/s10878-011-9423-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-011-9423-1