Abstract
This paper deals with the problem that reflects real-world situations adequately. Several constraints including unrelated machines, limited waiting times between every two successive processing operations and ready time of jobs are studied. These constraints and characteristics affect on some operations in a large number of companies. In recent researches, they have been tackled many times while so far have not been considered simultaneously. The aim of this paper is to model and solve the addressed problem by applying an efficient metaheuristic algorithm, entitled biogeography-based optimization (BBO). To assess the proposed BBO, two experiments are conducted and their results in terms of solutions quality, as well as computation efficiency compared against two popular algorithms, namely imperialist competitive algorithm and population-based simulated annealing. Due to the sensitivity of the values of parameters in the metaheuristic algorithms, a response surface methodology as a strength statistical tool is used to tune the parameters. The computational results show that the proposed BBO algorithm significantly outperforms the other foregoing algorithms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Pinedo M (1995) Scheduling: theory, algorithms, and systems. Prentice-Hall, New Jersey
Behnamian J, Zandieh M (2011) A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties. Expert Syst Appl 38(12):14490–14498
Su LH (2003) A hybrid two-stage flow-shop with limited waiting time constraints. Comput Ind Eng 44:409–424
Lin HT, Liao CJ (2003) A case study in a two-stage hybrid flow shop with setup time and dedicated machines. Int J Prod Econ 86(2):133–143
Low CY, Hsu CJ, Su CT (2008) A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines. Comput Oper Res 35(3):845–853
Bertel S, Billaut JC (2004) Agenetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation. Eur J Oper Res 159(3):651–662
Garey MR, Johnson DS (1979) A guide to the theory of NP-completeness. Computers and intractability. Freeman, San Francisco
Kahraman C, Engin O, Kaya I, Ozturk RE (2010) Multiprocessor task scheduling in multistage hybrid flow-shops: a parallel greedy algorithm approach. Appl Soft Comput 10:1293–1300
Oğuz C, Zinder Y, Do VH, Janiak A, Lichtenstein M (2004) Hybrid flow shop scheduling problems with multiprocessor task systems. Eur J Oper Res 152:115–131
Oğuz C, Ercan MF (2005) A genetic algorithm for hybrid flow shop scheduling with multiprocessor tasks. J Sched 8:323–351
Oğuz C (2006) Data for hybrid flow-shop scheduling with multiprocessor tasks. Available from http://home.ku.edu.tr/~coguz/
Kyparisis GJ, Koulamas C (2006) Flexible flow shop scheduling with uniform parallel machines. Eur J Oper Res 168:985–997
Gholami M, Zandieh M, Alem-Tabriz A (2009) Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. Int J Adv Manuf Technol 42(1):189–201
Allahverdi A, Al-Anzi FS (2006) Scheduling multi-stage parallel-processor services to minimize average response time. J Oper Res Soc 57(1):101–110
Ying KC, Lin SW (2006) Multiprocessor task scheduling in multistage hybrid flowshops: an ant colony system approach. Int J Prod Res 44(16):3161–3317
Verma SK, Dessouky MI (1999) Multistage hybrid flowshop scheduling with identical jobs and uniform parallel machines. J Sched 2:135–150
Tang L, Zhang Y (2005) Heuristic combined artificial neural networks to schedule hybrid flow shop with sequence dependent setup times. Advances in Neural Networks-ISNN 2005, pp. 315–364
Wang X, Tang L (2009) A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers. Comput Oper Res 36:907–918
Kurz ME, Askin RG (2004) Scheduling flexible flow lines with sequence-dependent setup times. Eur J Oper Res 159:66–82
Naderi B, Zandieh M, Shirazi M (2009) Modeling and scheduling a case of flexible flowshops: total weighted tardiness minimization. Comput Oper Res 57:1258–1267
Low CY (2005) Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines. Comput Oper Res 32(8):2013–2025
Ruiz R, Maroto C (2006) A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. Eur J Oper Res 169(3):781–800
Jungwattanakit J, Reodecha M, Chaovalitwongse P, Werner F (2009) A comparison of scheduling algorithms for flexible flowshop problems with unrelated parallel machines, setup times and dual criteria. Comput Oper Res 36:358–378
Tavakkoli-Moghaddam R, Safaei N (2006) Modeling flexible flow lines with blocking and sequence dependent setup time. In: Proceeding of the 5th International Symposium on Intelligent Manufacturing Systems (IMS2006), Sakarya, Turkey, May 29–31, pp. 149–158
Ruiz R, Şerifoğlu FS, Urlings T (2008) Modeling realistic hybrid flexible flowshop scheduling problems. Comput Oper Res 35:1151–1175
Chang J, Ma G, Ma X (2006) A new heuristic for minimal makespan in no-wait hybrid flowshops. Control Conference, 2006. CCC 2006. Chinese, Harbin, China, pp. 1352–1356
Yang DL, Chern MS (1995) A two-machine flowshop scheduling problem with limited waiting time constraints. Comput Ind Eng 28(1):63–70
Yan Li, Tieke Li (2007) Constructive backtracking heuristic for hybrid flowshop scheduling with limited waiting times. In: International Conference on Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007, Shanghai, China, pp. 6671–6674
Chen JS (2006) Model formulations for the machine scheduling problem with limited waiting time constraints. J Inf Optim Sci 27(1):225–240
Liu S, Cui J, Li Y (2008) Heuristic-tabu algorithm for hybrid flowshop scheduling with limited waiting time. In: International Symposium on Computational Intelligence and Design, ISCID ‘08, Wuhan, China, pp. 233–237
Simon D (2008) Biogeography-based optimization. IEEE Trans Evol Comput 12:702–713
Ruiz R, Vázquez-Rodríguez JA (2010) The hybrid flow shop scheduling problem. Eur J Oper Res 205:1–18
Roy PK, Ghoshal SP, Thakur SS (2010) Biogeography-based optimization technique for multi-constrained economic load dispatch problems. Int J Recent Trends Eng Technol 3(3):77–81
Behnamian J, FatemiGhomi SMT (2011) Hybrid flowshop scheduling with machine and resource- dependent processing times. Appl Math Model 35(3):1107–1123
Atashpaz-Gargari E, Lucas C (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialist competitive. In: IEEE Congress on Evolutionary Computation, Singapore, pp. 4661–4667
Attar SF, Mohammadi M, Tavakkoli-Moghaddam R (2011) A novel imperialist competitive algorithm to solve flexible flow shop scheduling problem in order to minimize maximum completion time. Int J Comput Appl 28(10):27–32
Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087–1092
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680
Bagher M, Zandieh M, Farsijani H (2011) Balancing of stochastic U-type assembly lines: an imperialist competitive algorithm. Int J Adv Manuf Technol 54(1):271–285
Forouharfard S, Zandieh M (2010) An imperialist competitive algorithm to schedule of receiving and shipping trucks in cross-docking systems. Int J Adv Manuf Technol 51:1179–1193
Jolai F, Rabiee M, Asefi M (2012) A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times. Int J Prod Res 50(24):7447–7466
Elmi A, Solimanpur M, Topaloglu S, Elmi A (2011) A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts. Comput Ind Eng 61:171–178
Gaafar LK, Masoud SA (2005) Genetic algorithms and simulated annealing for scheduling in agile manufacturing. Int J Prod Res 43(14):3069–3085
Lin SW, Gupta JND, Ying KC, Lee ZJ (2009) Using simulated annealing to schedule a flowshop manufacturing cell with sequence-dependent family setup times. Int J Prod Res 47(12):3205–3217
Mcmullen PR, Gregory FV (2000) A simulated annealing approach to mixed model sequencing with multiple objectives on a just-in-time line. IIE Trans 32(8):679–686
Vahdani B, Zandieh M (2010) Scheduling trucks in cross-docking systems: robust meta-heuristics. Comput Ind Eng 58:12–24
Zhou E, Chen X (2010) A new population-based simulated annealing algorithm. Winter Simulation Conference (WSC). In: Proceedings of the 2010, Baltimore, USA, pp. 1211–1222
Myers WR (2003) Encyclopedia of biopharmaceutical statistics. Marcel Dekker, New York
Ross RJ (1989) Taguchi techniques for quality engineering. McGraw-Hill, New York
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Attar, S.F., Mohammadi, M. & Tavakkoli-Moghaddam, R. Hybrid flexible flowshop scheduling problem with unrelated parallel machines and limited waiting times. Int J Adv Manuf Technol 68, 1583–1599 (2013). https://doi.org/10.1007/s00170-013-4956-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-013-4956-3