Abstract
The bi-objective hybrid flow shop problem with sequence-dependent setup times and limited buffers is mentioned in this paper. In this environment, there are limited buffer spaces between any two successive stages; thus, maybe there is not enough room for queues of jobs that are waiting in the system for their next operations. This problem is shown to be NP-hard in the strong sense. Up to now, some heuristic and metaheuristic approaches are proposed to minimize makespan or total tardiness of jobs. This paper presents several methods for optimization which consider two objectives simultaneously. The resolution of several specific instances from the open literature with the adaptations of non-dominated sorting genetic algorithm and sub-population genetic algorithm suggest that the proposed algorithms are effective and useful methods for solving this problem.
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
Abadi INK, Hall NG, Sriskandarajah C (2000) Minimizing cycle time in a blocking flowshop. Oper Res 48:177–180
Behnamian J, Fatemi Ghomi SMT, Zandieh M (2009) A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic. Expert Syst Appl 36:11057–11069
Caraffa V, Ianes S, Bagchi TP, Sriskandarajah C (2001) Minimizing makespan in a flowshop using genetic algorithms. Int J Prod Econ 70:101–115
Chang P-C, Chen S-H (2009) The development of a sub-population genetic algorithm II (SPGA II) for multi-objective combinatorial problems. Appl Soft Comput 9:173–181
Davoudpour H, Ashrafi M (2009) Solving multi-objective SDST flexible flow shop using GRASP algorithm. Int J Adv Manuf Technol 44(7–8):737–747. doi:10.1007/s00170-008-1887-5
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm (NSGA-II). IEEE Trans Evol Comput 6:2
Hung TSL, Ching JL (2003) A case study in a two-stage hybrid flow shop with setup time and dedicated machines. Int J Prod Econ 86:133–143
Jolai F, Sheikh Sh, Rabbani M, Karimi M (2009) A genetic algorithm for solving no-wait flexible flow lines with due windows, and job rejection. Int J Adv Manuf Technol 42(5–6):523–532
Kurz ME, Askin RG (2003) Comparing scheduling rules for flexible flow lines. Int J Prod Econ 85:371–388
Kurz ME, Askin RG (2004) Scheduling flexible flow lines with sequence-dependent setup times. Eur J Oper Res 159(1):66–82
Leisten R (1990) Flowshop sequencing problems with limited buffer storage. Int J Prod Res 28:2085–2100
Luh PB, Gou L, Zhang Y, Nagahora T, Tsuji M, Yoneda K, Hasegawa T, Kyoya Y, Kano T (1998) Job shop scheduling with group dependent setups, finite buffers, and long time horizon. Ann Oper Res 76:233–259
McCormick ST, Pinedo ML, Shenker S, Wolf B (1989) Sequencing in an assembly line with blocking to minimize cycle time. Oper Res 37:925–936
Norman BA (1999) Scheduling flowshops with finite buffers and sequence-dependent setup times. Comput Ind Eng 36:163–177
Nowicki E (1999) The permutation flow shop with buffers: a tabu search approach. Eur J Oper Res 116:205–219
Pinedo M (1995) Scheduling theory, algorithms, and systems, 2nd edn. Prentice-Hall, Englewood Cliffs
Ronconi DP (2004) A note on constructive heuristics for the flowshop problem with blocking. Int J Prod Econ 87:39–48
Ronconi DP, Henriques LRS (2007) Some heuristic algorithms for total tardiness minimization in a flowshop with blocking. Omega 37:272–281
Sawik TJ (1993) A scheduling algorithm for flexible flow lines with limited intermediate buffers. Appl Stoch Models Data Anal 9:127–138
Sawik TJ (1995) Scheduling flexible flow lines with no in-process buffers. Int J Prod Res 33(5):1357–1367
Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64:278–285
Wang L, Zhang L, Zheng D-Z (2006) An effective hybrid genetic algorithm for flow shop scheduling with limited buffers. Comput Oper Res 33:2960–2971
Wardono B, Fathi Y (2004) A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities. Eur J Oper Res 155:380–401
Wittrock RJ (1988) An adaptable scheduling algorithm for flexible flow lines. Oper Res 36:445–453
Yaurima V, Burtseva L, Tchernykh A (2008) Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers. Comput Ind Eng. doi:10.1016/j.cie.2008.09.004
Zandieh M, Fatemi Ghomi SMT, Moattar Husseini SM (2006) An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Appl Math Comput 180:111–127
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hakimzadeh Abyaneh, S., Zandieh, M. Bi-objective hybrid flow shop scheduling with sequence-dependent setup times and limited buffers. Int J Adv Manuf Technol 58, 309–325 (2012). https://doi.org/10.1007/s00170-011-3368-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-011-3368-5