Abstract
The hybrid flow shop with parallel batching (HFSPB) is a kind of flow shop production system wherein some stages may be populated by parallel processors that simultaneously process groups of jobs. This paper addresses the makespan minimization problem for a HFSPB system whose machines are characterized by both capacity and eligibility restrictions. Firstly, a mixed integer linear programming model concerning the proposed problem is presented. Then, a specific genetic algorithm (GA) that makes use of a permutation encoding scheme as well as a crossover operator specifically designed for effectively managing the batch processing is discussed. The relevant parameters of the developed algorithm were calibrated by means of a full factorial design of experiments, and an extensive comparison campaign has been carried out with the aim to statistically assess the performance of the proposed GA with respect to five alternative procedures, four of which arisen from the relevant literature. The obtained results, also supported by a properly developed ANOVA analysis, demonstrate the effectiveness of the proposed GA-based metaheuristics in tackling the HFSPB problem investigated, under both quality of solutions and computational burden viewpoints.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ruiz R, Vázquez-Rodríguez JA (2010) The hybrid flow shop scheduling problem. Eur J Oper Res 205:1–18
Gupta JND (1988) Two-stage hybrid flow shop scheduling problem. J Oper Res Soc 39(4):359–364
Gourgand M, Grangeon N, Norre S (1999) Metaheuristics for the deterministic hybrid flow shop problem. Proc international conference on industrial engineering and production management, IEPM’99. FUCAMINRIA, Glasgow, pp 136–145
Sherali HD, Sarin SC, Kodialam MS (1990) Models and algorithms for a two-stage production process. Prod Plann Contr 1(1):27–39
Brah SA, Hunsucker JL (1991) Branch and bound algorithm for the flow-shop with multiple processors. Eur J Oper Res 51(1):88–99
Carlier J, Néron E (2000) An exact method for solving the multi-processor flowshop. RAIRO, Oper Res 34(1):1–25
Guinet AGP, Solomon MM (1996) Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time. Int J Prod Res 34(6):1643–1654
Brah SA, Loo LL (1999) Heuristics for scheduling in a flow shop with multiple processors. Eur J Oper Res 113:113–122
Botta-Genoulaz V (2000) Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness. Int J Prod Econ 64:101–111
Yang J (2011) Minimizing total completion time in two stage hybrid flow shop with dedicated machines. Comput Oper Res 38:1045–1053
Wang S, Liu M (2013) A heuristic method for two-stage hybrid flow shop with dedicated machines. Comput Oper Res 40:438–450
Xiao W, Hao P, Zhang S, Xu X (2000) Hybrid flow shop scheduling using genetic algorithms. Proc 3rd world conference on intelligent control and automation, Hefei, pp 537–541
Ruiz R, Maroto C (2006) A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. Eur J Oper Res 169:781–800
Yaurima V, Burtseva L, Tchernykh A (2009) Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers. Comput Ind Eng 56:1452–1463
Wardono B, Fathi Y (2002) A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities. Eur J Oper Res 155:380–401
Engin O, Döyen A (2004) A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Gener Comp Sy 20:1083–1095
Ying KC, Lin SW (2006) Multiprocessor task scheduling in multistage hybrid flowshops: an ant colony system approach. Int J Prod Res 44(16):3161–3177
Tseng CT, Liao CJ (2008) A particle swarm optimization for hybrid flow-shop scheduling with multiprocessor tasks. Int J Prod Res 46(17):4655–4670
Singh MR, Mahapatra SS (2012) A swarm optimization approach for flexible flow shop scheduling with multi-processor tasks. Int J Adv Manuf Technol 62:267–277
Tavakkoli-Moghddam R, Sfaei N, Sassani F (2009) A memetic algorithm for the flexible flow line scheduling problem with processor blocking. Comput Oper Res 36:402–414
Mirsanei HS, Zandieh M, Moayed MJ, Khabbazi MR (2011) A simulated annealing approach to hybrid flow shop scheduling with sequence-dependent setup times. J Intell Manuf 22:965–978
Kurz ME, Askin RG (2004) Scheduling flexible flow lines with sequence dependent setup times. Eur J Oper Res 159:66–82
Mathirajan M, Sivakumar AI (2006) A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. Int J Adv Manuf Technol 29:990–1001
Attar SF, Mohammadi M, Tavakkoli-Moghaddam R (2013) Hybrid flexible flowshop scheduling problem with unrelated parallel machines and limited waiting times. Int J Adv Manuf Technol 68:1583–1599
Webster S, Baker KR (1995) Scheduling groups of jobs on a single machine. Oper Res 43(4):692–703
Yuan JJ, Yang AF, Cheng TCE (2004) A note on the single machine serial batching scheduling problem to minimize maximum lateness with identical processing times. Eur J Oper Res 158:525–528
Shen L, Buscher U (2012) Solving the serial batching problem in job shop manufacturing systems. Eur J Oper Res 221:14–26
Azizoglu M, Webster S (2001) Scheduling a batch processing machine with incompatible job families. Comput Ind Eng 39:325–335
Chang PC, Wang HM (2004) A heuristic for a batch processing machine scheduled to minimize total completion time with non-identical job sizes. Int J Adv Manuf Technol 24:615–620
Mathirajan M, Sivakumar AI, Chandru V (2004) Scheduling algorithms for heterogeneous batch processors with incompatible job-families. J Intell Manuf 15:787–803
Mönch L, Balasubramanian H, Fowler JW, Pfund ME (2004) Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Comput Oper Res 32:2731–2750
Amin-Naseri MR, Beheshti-Nia MA (2009) Hybrid flow shop scheduling with parallel batching. Int J Prod Econ 117:185–196
Costa A, Cappadonna FA, Fichera S (2013) A dual encoding-based meta-heuristic algorithm for solving a constrained hybrid flow shop scheduling problem. Comput Ind Eng 64(4):937–958
Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor
Rajendran C, Chaundhuri D (1992) A multi-stage parallel processor flowshop problem with minimum flowtime. Eur J Oper Res 57:111–122
Michalewicz Z (1994) Genetic algorithms + data structures = evolution programs, 2nd edn. Springer, Berlin
Davis L (1985) Applying adaptive algorithms to epistatic domains. Proc ninth international joint conference on artificial intelligence. IJCAI-85, Los Angeles, pp 162–164
Reeves CR (1995) A genetic algorithm for flowshop sequencing. Comput Oper Res 22(1):5–13
Montgomery D (2007) Design and analysis of experiments, 5th edn. Wiley, New York
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Costa, A., Cappadonna, F.A. & Fichera, S. A novel genetic algorithm for the hybrid flow shop scheduling with parallel batching and eligibility constraints. Int J Adv Manuf Technol 75, 833–847 (2014). https://doi.org/10.1007/s00170-014-6195-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-014-6195-7