Abstract
This paper deals with the problem of hybrid flow shop scheduling. In this investigation, we considered group scheduling within the area of sequence-dependent family setup times and two objectives of minimizing makespan and total tardiness are taken into consideration simultaneously. Due to the computational complexity in solving these set of problems with multiple objectives, metaheuristics has a high priority, because these algorithms are capable of solving combinatorial problems in a reasonable time. This study focuses on three multi-objective algorithms, multi-objective genetic algorithm, sub-population genetic algorithm-II and non-dominated sorting genetic algorithm-II, to solve the mentioned problem. In order to investigate the effectiveness and efficiency of applying the noted metaheuristics for such an NP-hard problem, we evaluate non-dominated solution sets obtained via each algorithm through some evaluation metrics.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Gupta J.N.D., Tunc E.A.: Schedules for a two-stage hybrid flowshop with parallel machines at the second stage. Int. J. Prod. Res. 29, 1489–1502 (1991)
Gupta J.N.D., Tunc E.A.: Scheduling a two-stage hybrid flowshop with separable setup and removal times. Eur. J. Oper. Res. 77, 415–428 (1994)
Gupta J.N.D., Hariri A.M.A., Potss C.N.: Scheduling a two-stage hybrid flow shop with parallel machines at first stage. Ann. Oper. Res. 69, 171–191 (1997)
Gupta J.N.D., Tunc E.A.: Minimizing tardy jobs in a two-stage hybrid flow shop. Int. J. Prod. Res. 36(9), 2397–2417 (1998)
Brah S.A., Hunsucker J.L.: Branch and bound algorithm for the flow shop with multiple processors. Eur. J. Oper. Res. 51, 88–99 (1991)
Portmann M.C., Vignier A., Dardilhac D., Dezalay D.: Branch and bound crossed with GA to solve hybrid flowshops. Eur. J. Oper. Res. 107(2), 389–400 (1998)
Moursli O., Pochet Y.: A branch-and-bound algorithm for the hybrid flowshop. Int. J. Prod. Econ. 64, 113–125 (2000)
Botta-Genoulaz V.: Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness. Int. J. Prod. Econ. 64, 101–111 (2000)
Engin O., Doyen A.: A new approach to solve hybrid flow shop scheduling problem by artificial immune system. Future Gen. Comput. Syst. 20, 1083–1095 (2004)
Janiak A., Kozan E., Lichtensein M., Oguz C.: Metaheuristics approaches to the hybrid flow shop scheduling problem with a cost-related criterion. Int. J. Prod. Econ. 105(2), 407–424 (2007)
Gupta J.N.D., Kruger K., Lauff V., Warner F., Sotskov Y.N.: Heuristics for hybrid flow shop with controllable processing times and assignable due dates. Comput. Oper. Res. 29(10), 1417–1439 (2002)
Allaoui H., Artiba A.: Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints. Comput. Ind. Eng. 47, 431–450 (2004)
Jungwattanakit, J.; Reodecha, M.; Chaovalitwongse, P.; Werner, F.: An evaluation of sequencing heuristics for flexible flowshop scheduling problem with unrelated parallel machines and dual criteria. Otto-von-Guericke-Universitat Magdeburg, Preprint 28/05, pp. 1–23 (2005)
Mitrofanov, S.P.: The Scientific Principles of Group Technology. National Lending Library, Boston Spa(1966)
Ham, I.; Hitmoi, K.; Yoshida, T.: Group technology: applications to production management. Hinghama: Kluwer (1985)
Kurz M.E., Askin R.G.: Scheduling flexible flow lines with sequence-dependent setup times. Eur. J. Oper. Res. 159, 66–82 (2004)
Zandieh M., Fatemi Ghomi S.M.T., Moattar Husseini S.M.: An immune algorithm approach to hybrid flowshops scheduling with sequence-dependent setup times. Appl. Math. Comput. 180, 111–127 (2006)
Hendizadeh S.H., Faramarzi H., Mansouri S.A., Gupta J.N.D., Elmekkawy T.Y.: Meta-heuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times. Int. J. Prod. Econ. 111, 593–605 (2008)
Franca P.M., Gupta J.N.D., Mendes A.S., Moscato P., Veltink K.: Evolutionary algorithm for scheduling a flowshop manufacturing cell with sequence dependent family setups. Comput. Ind. Eng. 48, 491–506 (2005)
Logendran R., Salmasi N., Sriskandarajah C.: Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups. Comput. Oper. Res. 33, 158–180 (2006)
Zolfaghari S., Liang M.: Jointly solving the group scheduling and machining speed selection problems: a hybrid tabu search and simulated annealing approach. Int. J. Prod. Res. 37, 2377–2397 (1999)
Mukerjee A., Biswas R., Deb K., Mathur A.P.: Multi-objective evolutionary algorithm for the risk-return trade-off in bank loan management. Int. Trans. Oper. Res. 9(5), 583–597 (2002)
Schaffer, J.D.: Multiple objective optimization with vector evaluated genetic algorithms. In: Proceedings of the First International Conference on Genetic Algorithms and Their Applications, pp. 93–100. Carnegie-Mellon University, Pittsburg (1985)
Murata T., Ishibuchi H., Tanaka H.: Multi-objective genetic algorithm and its application to flow shop scheduling. Comput. Ind. Eng. 30(4), 957–968 (1996)
Zitzler E., Thiele L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999)
Zitzler, E.; Laumanns, M.; Thiele, L.: Spea2: improving the strength Pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Network Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Switzerland (2001)
Chang P.C., Chen S.H., Lin K.L.: Two-phase sub population genetic algorithm for parallel machine scheduling problem. Expert Syst. Appl. 29(3), 705–712 (2005)
Chang P.C., Chen S.H.: The development of a sub-population genetic algorithm-II (SPGA-II) for multi-objective combinatorial problems. Appl. Soft Comput. 9(1), 173–181 (2009)
Deb K., Pratap A., Agarwal S., Meyarivan T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
Tamaki, H.; Kita, H.; Kobayashi, S.: Multi-objective optimization by genetic algorithms: a review. In: Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, pp. 517–522. IEEE Service Center, Piscataway (1996)
Bean J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6(2), 154–160 (1994)
Norman B.A., Bean J.C.A.: A genetic algorithm methodology for complex scheduling problems. Nav. Res. Logist. 46, 199–211 (1999)
Goldberg E.D.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, Reading (1989)
Sirnivas N., Deb K.: Multi-objective function optimization using non-dominated sorting genetic algorithms. Evol. Comput. 2(3), 221–248 (1995)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fadaei, M., Zandieh, M. Scheduling a Bi-Objective Hybrid Flow Shop with Sequence-Dependent Family Setup Times Using Metaheuristics. Arab J Sci Eng 38, 2233–2244 (2013). https://doi.org/10.1007/s13369-013-0611-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13369-013-0611-4