Abstract
In this paper, we address the hybrid flow shop scheduling problems with unrelated parallel machines, sequence-dependent setup times and processor blocking to minimize the makespan and maximum tardiness criteria. Since the problem is strongly NP-hard, we propose an effective algorithm consisting of independent parallel genetic algorithms by dividing the whole population into multiple subpopulations. Each subpopulation will be assigned with different weights to search for optimal solutions in different directions. To further cover the Pareto solutions, each algorithm is combined with a novel local search step and a new helpful procedure called Redirect. The proposed Redirect procedure tries to help the algorithm to overcome the local optimums and to further search the solution space. When a population stalls over a local optimum, at first, the algorithm tries to achieve a better solution by implementing the local search step based on elite chromosomes. As implementing the local search step is time-consuming, we propose a method to speed up the searching procedure and to further increase its efficiency. If the local search step failed to work, then the Redirect procedure changes the direction and refreshes the population. Computational experiments indicate that our proposed improving procedures are thriving in achieving better solutions. We have chosen two measures to evaluate the performance of our proposed algorithms. The obtained results clearly reveal the prosperity of our proposed algorithm considering both measures we have chosen.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Pinedo M (2001) Scheduling: theory, algorithms, and systems, 2nd edn. Prentice-Hall, Englewood Cliffs
Thornton HW, Hunsucker JL (2004) A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage. Eur J Oper Res 152:96–114
Wang L, Liang Z, Da-Zhong Z (2006) An effective hybrid genetic algorithm for flow shop scheduling with limited buffers. Comput Oper Res 33:2960–2971
Sawik T (2000) Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers. Math Comput Model 31(13):39–52
Tavakkoli-Moghaddam R, Safaei N, Sasani F (2009) A memetic algorithm for the flexible flow line scheduling problem with processor blocking. Comput Oper Res 36(2):402–414
Quadt D, Kuhn H (2007) A taxonomy of flexible flow line scheduling procedures. Eur J Oper Res 178:686–698
Jungwattanakit J, Reodecha M, Chaovalitwongse P, Werner F (2008) Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Int J Adv Manuf Technol 37:354–370
Behnamian J, Fatemi Ghomi SMT, Zandieh M (2009) A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic. Expert Syst Appl 36(8):11057–11069. doi:10.1016/j.eswa.2009.02.080
Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei AH (2007) A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness. Inform Sciences 177(22):5072–5090
Pasupathy T, Rajendran C, Suresh RK (2006) A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs. Int J Adv Manuf Technol 27:804–815. doi:10.1007/s00170-004-2249-6
Varadharajan TK, Rajendran C (2005) A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. Eur J Oper Res 167(3):772–795
Chang PC, Chen SH, Lin KL (2005) Two phase subpopulation genetic algorithm for parallel machine scheduling problem. Expert Syst Appl 29(3):705–712
Chang PC, Chen SH, Liu CH (2007) Sub-population genetic algorithm with mining gene structures for multiobjective flowshop scheduling problems. Expert Syst Appl 33(3):762–771
Nagar A, Haddock J, Haragu S (1995) Multiple and bi-criteria scheduling: a literature review. Eur J Oper Res 81(1):88–104
Allahverdi A (2004) A new heuristic for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness. Comput Oper Res 31(2):157–180
Gupta JND, Krüger K, Lauff V, Werner F, Sotskov YN (2002) Heuristics for hybrid flow shops with controllable processing times and assignable due dates. Comput Oper Res 29(10):1417–1439
Alisantoso D, Khoo LP, Jiang PY (2003) An immune algorithm approach to the scheduling of a flexible PCB flow shop. Int J Adv Manuf Technol 22(11–12):819–827
Lin H-T, Liao C-J (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
Wang W, Hunsucker JL (2003) An evaluation of the CDS heuristic in flow shops with multiple processors. J Chin Inst Ind Eng 20(3):295–304
Deb K, Amrit P, Sameer A, Meyarivan T (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE T Evolut Comput 6(2):182–197
Zitzler E, Laumanns M, Bleuler S (2004) A tutorial on evolutionary multiobjective optimization. Proceedings of the Workshop on Multiple Objective Metaheuristics
Affenzeller M (2002) New generic hybrids based upon genetic algorithms. Lect Notes Comp Sci 2527:329–339
Lis J, Eiben AE (1997) A multi-sexual genetic algorithm for multicriteria optimization. Proceedings of the 4th IEEE Conference on Evolutionary Computation, pp 59–64
Cochran JK, Horng SM, Fowler JW (2003) A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Comput Oper Res 30:1087–1102
Hu J, Goodman E, Seo K, Fan Z, Rosenberg R (2005) The hierarchical fair competition framework for sustainable evolutionary algorithms. Evolu Comput 13(2):241–277
Coello CA, Pulido GT, Lechuga MS (2004) Handling multiple objectives with particle swarm optimization. IEEE Trans Evol Comput 8(3):256–279
Mostaghim S, Teich J (2004) Covering Pareto-optimal fronts by subswarms in multi-objective particle swarm optimization. Evol Comput 2:1404–1411
Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength Pareto evolutionary algorithm. Techni Rep Comp Eng Net Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland
Kurz ME, Askin RG (2004) Scheduling flexible flow lines with sequence-dependent setup times. Eur J Oper Res 159(1):66–82
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
Gholami M, Zandieh M, Alem-Tabriz A (2008) Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. Int JAdv Manu Tech 42(1–2):189–201. doi:10.1007/s00170-008-1577-3
Naderi B, Zandieh M, Roshanaei V (2008) Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness. Int J Adv Manu Tech 41(11–12):1186–1198. doi:10.1007/s00170-008-1569-3
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Rashidi, E., Jahandar, M. & Zandieh, M. An improved hybrid multi-objective parallel genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines. Int J Adv Manuf Technol 49, 1129–1139 (2010). https://doi.org/10.1007/s00170-009-2475-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-009-2475-z