Abstract
This paper considers group scheduling problem in hybrid flexible flow shop with sequence-dependent setup times to minimize makespan. Group scheduling problem consists of two levels, namely scheduling of groups and jobs within each group. In order to solve problems with this context, two new metaheuristics based on simulated annealing (SA) and genetic algorithm (GA) are developed. A design procedure is developed to specify and adjust significant parameters for SA- and GA-based metaheuristics. The proposed procedure is based on the response surface methodology and two types of objective function are considered to develop multiple-objective decision making model. For comparing metaheuristics, makespan and elapsed time to obtain it are considered as two response variables representing effectiveness and efficiency of algorithms. Based on obtained results in the aspect of makespan, GA-based metaheuristic is recommended for solving group scheduling problems in hybrid flexible flow shop in all sizes and for elapsed time SA-based metaheuristic has better results.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Allison JD (1990) Combining Petrov’s heuristic and the CDS heuristic in group scheduling problems. In: Proceedings of the 12th Annual Conference on Computers and Industrial Engineering, Orlando, FL, pp 457–461
Al-Qattan I (1988) Designing GT cells enhanced by group scheduling. In: Proceedings of the IIE Integrated Systems Conference, pp 25–30
Baker KR (1988) Scheduling the production of components at a common facility. IIE Trans 20:32–35 doi:10.1080/07408178808966147
Campbell HG, Dudek RA, Smith ML (1970) A heuristic algorithm for the n job, m machine sequencing problem. Manage Sci 16:B630–B637
Eiben AE, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3(2):124–141 doi:10.1109/4235.771166
Gholami M, Zandieh M, Alem-Tabriz A (2008) Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. Int J Adv Manuf Technol doi:10.1007/s00170-008-1577-3
Grefenstette JJ (1986) Optimisation of control parameters for genetic algorithms. IEEE Trans Syst Man Cybern 16(1):122–128 doi:10.1109/TSMC.1986.289288
Ham I, Hitomi K, Yoshida T (1985) Group technology: applications to production management. Kluwer Academic, Hingham
Heragu S (1997) Facilities design. PWS, Boston
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680 doi:10.1126/science.220.4598.671
Kurz ME, Askin RG (2003) Comparing scheduling rules for flexible flow lines. Int J Prod Econ 85:371–388 doi:10.1016/S0925-5273(03)00123-3
Kurz ME, Askin RG (2004) Scheduling flexible flow lines with sequence-dependent setup times. Eur J Oper Res 159(1):66–82 doi:10.1016/S0377-2217(03)00401-6
Liaee MM, Emmons H (1997) Scheduling families of jobs with setup times. Int J Prod Econ 51:165–176 doi:10.1016/S0925-5273(96)00105-3
Logendran R, Nudtasomboon N (1991) Minimizing the makespan of a group scheduling problem: a new heuristic. Int J Prod Econ 22:217–230 doi:10.1016/0925-5273(91)90098-E
Logendran R, Mai L, Talkington D (1995) Combined heuristics for bi-level group scheduling problems. Int J Prod Econ 38:133–145 doi:10.1016/0925-5273(94)00083-M
Logendran R, Carson S, Hanson E (2005) Group scheduling in flexible flow shops. Int J Prod Econ 96(2):143–155 doi:10.1016/j.ijpe.2004.03.011
Logendran R, deSzoeke P, Barnard F (2006) Sequence-dependent group scheduling problems in flexible flow shops. Int J Prod Econ 102:66–86 doi:10.1016/j.ijpe.2005.02.006
Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculation by east computing machines. J Chem Phys 21:1087–1091 doi:10.1063/1.1699114
Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs, 3rd edn. Springer, Berlin
Michalewicz Z, Schoenauer M (1996) Evolutionary algorithms for constrained parameter optimisation problems. Evol Comput 4(1):1–32 doi:10.1162/evco.1996.4.1.1
Naderi B, Zandieh M, Fatemi Ghomi SMT (2008) Scheduling job shop problems with sequence-dependent setup times. Int J Prod Res doi:10.1080/00207540802165817
Nakamura N, Yoshida T, Hitomi K (1978) Group production scheduling for minimum total tardiness: part I. AIIE Transactions 10:157–162
Norman BA, Bean JC (1999) A genetic algorithm methodology for complex scheduling problems. Nav Res Logistics 46:199–211 doi:10.1002/(SICI)1520-6750(199903)46:2<199::AID-NAV5>3.0.CO;2-L
Ozden M, Egbelu PJ, Iyer AV (1985) Job scheduling in a group technology environment for a single facility. J Comput Ind Eng 9:67–72 doi:10.1016/0360-8352(85)90037-3
Petrov VA (1966) Flow line group production planning. Business Publications, London
Radharamanan R (1986) A heuristic algorithm for group scheduling. In: Proceedings of the International Industrial Engineering Conference, pp 229–236
Reddy V, Narendran TT (2003) Heuristics for scheduling sequence dependent set-up jobs in flow line cells. Int J Prod Res 41(1):193–206 doi:10.1080/00207540210163973
Schaller JE, Gupta JND, Vakharia AJ (2000) Scheduling a flow line manufacturing cell with sequence dependent family setup times. Eur J Oper Res 125:324–339 doi:10.1016/S0377-2217(99)00387-2
Webster S, Baker KR (1995) Scheduling groups of jobs on a single machine. Oper Res 43:692–703
Zandieh M, Fatemi SMT (2003) A framework and a classification scheme for modeling production systems. In: Proceedings of the Second National Industrial Engineering Conference, Yazd University, Yazd, Iran, pp 308–315
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 doi:10.1016/j.amc.2005.11.136
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zandieh, M., Dorri, B. & Khamseh, A.R. Robust metaheuristics for group scheduling with sequence-dependent setup times in hybrid flexible flow shops. Int J Adv Manuf Technol 43, 767–778 (2009). https://doi.org/10.1007/s00170-008-1740-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-008-1740-x