Abstract
In this paper we consider a multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times by minimizing total weighted tardiness and maximum completion time simultaneously. Whereas these kinds of problems are NP-hard, thus we proposed a multi-population genetic algorithm (MPGA) to search Pareto optimal solution for it. This algorithm comprises two stages. First stage applies combined objective of mentioned objectives and second stage uses previous stage’s results as an initial solution. In the second stage sub-population will be generated by re-arrangement of solutions of first stage. To evaluate performance of the proposed MPGA, it is compared with two distinguished benchmarks, multi-objective genetic algorithm (MOGA) and non-dominated sorting genetic algorithm II (NSGA-II), in three sizes of test problems: small, medium and large. The computational results show that this algorithm performs better than them.
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
Allahverdi A., Gupta J. N. D., Aldowaisan T. (1999) A survey of scheduling research involving setup considerations, OMEGA. International Journal of Management Science 27: 219–239
Baker K. R. (1988) Scheduling the production of components at a common facility. IIE Transactions 20: 32–35
Baker K. R. (1990) Scheduling groups of jobs in the two-machine flow shop. Mathematical and Computer Modeling 13: 29–36
Bean J. C. (1994) Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 6: 154–160
Beausoleil R. P. (2006) “MOSS” multiobjective scatter search applied to non-linear multiple criteria optimization. European Journal of Operational Research 169: 426–449
Behnamian J., Zandieh M., Fatemi Ghomi S. M. T. (2009) Due windows group scheduling using an effective hybrid optimization approach. International Journal of Advanced Manufacturing Technology 44(7): 795–808
Burbidge J. L. (1975) The introduction of group technology. Heinemann, London
Cavalieri S., Gaiardelli P. (1998) Hybrid genetic algorithms for a multiple-objective scheduling problem. Journal of intelligent manufacturing 9: 361–367
Cetinkaya F. C., Kayaligil M. S. (1992) Unit sized transfer batch scheduling with setup times. Computers and Industrial Engineering 22: 177–183
Cheng T. C. E., Gupta J. N. D., Wang G. (2000) A review of flowshop scheduling research with setup times. Production and Operations Management 9: 283–302
Cochran, J. K., Horng, S. M., & Fowler, J. W. (2003). A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers and Operations Research, 30, 1087–1102.
Danneberg D., Tautenhahn T., Werner F. (1999) A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size. Mathematical and Computer Modelling 29(9): 101–126
Deb K., Pratap A., Agarwal S., Meyarivan T. (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2): 182–197
Fonseca, C. M., & Fleming, P. J. (1993). Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. In S. Forrest (Ed.), Proceedings of the fifth international conference on genetic algorithms (pp. 416–423). Morgan Kaufman Publishers San Mateo, California University of Illinois at Urbana-Champaign.
Franca P. M., Gupta J. N. D., Mendes A., Moscato P., Veltink K. J. (2005) Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups. Computers and Industrial Engineering 48: 491–506
Gunaraj V., Murugan N. (1999) Application of response surface methodology for predicting weld bead quality in submerged arc welding of pipes. Journal of Materials Processing Technology 88: 266–275
Gupta J. N. D., Darrow W. P. (1985) Approximate schedules for the two-machine flowshop with sequence dependent setup times. Indian Journal of Management and Systems 1: 6–11
Gupta J. N. D., Darrow W. P. (1986) The two-machine sequence dependent flowshop scheduling problem. European Journal of Operational Research 24: 439–446
Ham I., Hitomi K., Yoshida T. (1985) Group technology: Applications to production management. Kluwer, Hingham, MA
Hou T. H., Su C. H., Chang H. Z. (2008) An integrated multi-objective immune algorithm for optimizing the wire bonding process of integrated circuits. Journal of intelligent manufacturing 19: 361–374
Hyun C. J., Kim Y., Kin Y. K. (1998) A genetic algorithm for multiple objective sequencing problems in mixedmodel assembly. Computers & Operations Research 25: 675–690
Janiak A., Kovalyov M. Y., Portmann M. C. (2005) Single machine group scheduling with resource dependent setup and processing times. European Journal of Operational Research 162: 112–121
Kim Y. D. (1993) Heuristics for flowshop scheduling problems minimizing mean tardiness. Journal of Operational Research Society 44: 19–28
Kim Y. D., Lim H. G., Park M. W. (1996) Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process. European Journal of Operational Research 91: 124– 143
Knowles J. D., Corne D. W. (2000) Approximating the nondominated front using the Pareto archived evolution strategy. Evolutionary Computation 8(2): 149–172
Kuo W., Yang D. (2006) Single-machine group scheduling with a time-dependent learning effect. Computers & Operations Research 33: 2099–2112
Kurz M. E., Askin R. G. (2004) Scheduling flexible flow lines with sequence-dependent setup times. European Journal of Operational Research 159: 66–82
Kusiak A. (1987) The generalized group technology concept. International Journal of Production Research 25: 561–569
Leu B. Y., Nazemetz J. W. (1995) Comparative analysis of group scheduling heuristics in a flow shop cellular system. International Journal of Operations & Production Management 15((9): 143–157
Liaee M. M., Emmons H. (1997) Scheduling families of jobs with setup times. International Journal of Production Economics 51: 165–176
Liu Z., Yu W. (1999) Minimizing the number of late jobs under the group technology assumption. Journal of Combinatorial Optimization 3: 5–15
Logendran R., Mai L., Talkington D. (1995) Combined heuristics for bi-level group scheduling problems. International Journal of Production Economics 38: 133–145
Logendran R., Carson S., Hanson E. (2005) Group scheduling in flexible flow shops. International Journal of Production Economics 96(2): 143–155
Logendran R., deSzoeke P., Barnard F. (2006a) Sequence-dependent group scheduling problems in flexible flow shops. International Journal of Production Economics 102: 66–86
Logendran R., Salmasi N., Sriskandarajah C. (2006b) Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups. Computers & Operations Research 33: 158–180
Mansini R., Grazia Speranza M., Tuza Z. (2004) Scheduling groups of tasks with precedence constraints on three dedicated processors. Discrete Applied Mathematics 134: 141–168
Mitrofanov S. P. (1966) Scientific principles of group technology. National Lending Library, London (English Translation Boston Spa)
Murata T., Ishibuchi H., Tanaka H. (1996) Multi-objective genetic algorithm and its application to flowshop scheduling. Computers & Industrial Engineering 30: 957–968
Naderi, B., Zandieh, M., & Fatemi Ghomi, S. M. (2008). A study on integrating sequence dependent setup time flexible flow lines and preventive maintenance scheduling. Journal of intelligent manufacturing. doi:10.1007/s10845-008-0157-6.
Reddy V., Narendran T. T. (2003) Heuristics for scheduling sequence dependent set-up jobs in flow line cells. International Journal of Production Research 41(1): 193–206
Schaffer, J. D. (1985). Multiple objective optimization with vector evaluated genetic algorithms. In Proceedings of the first ICGA (pp. 93–100).
Schaller J. E., Gupta J. N. D., Vakharia A. J. (2000) Scheduling a flowline manufacturing cell with sequence dependent family setup times. European Journal of Operational Research 125: 324–339
Sekiguchi Y. (1983) Optimal schedule in a GT-type flow-shop under series-parallel precedence constraints. Journal of the Operations Research Society of Japan 26: 226–251
Tavakkoli-Moghaddam R., Rahimi-Vahed A. R., Mirzaei A. H. (2008) Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm. International Journal of Advanced Manufacturing Technology 36(9-10): 969–981
Vickson R. G., Alfredsson B. E. (1992) Two- and three-machine flow shop scheduling problems with equal sized transfer batches. International Journal of Production Research 30: 1551–1574
Wilson A. D., King R. E., Hodgson T. J. (2004) Scheduling non-similar groups on a flow line: Multiple group setups. Robotics and Computer-Integrated Manufacturing 20: 505–515
Yang D., Chern M. S. (2000) Two-machine flowshop group scheduling problem. Computers and Operations Research 27: 975–985
Zandieh, M., Dorri, B., & Khamseh, A. R. (2008). Robust metaheuristics for group scheduling with sequence-dependent setup times in hybrid flexible flow shops. International Journal of Advanced Manufacturing Technology. doi:10.1007/s00170-008-1740-x.
Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm. Technical report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zandieh, M., Karimi, N. An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times. J Intell Manuf 22, 979–989 (2011). https://doi.org/10.1007/s10845-009-0374-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-009-0374-7