Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling with learning effect and setup times

  • Original Paper
  • Published:
Operational Research Aims and scope Submit manuscript

Abstract

This paper deals with a bi-objective hybrid flow shop scheduling problem minimizing the maximum completion time (makespan) and total tardiness, in which we consider re-entrant lines, setup times and position-dependent learning effects. The solution method based on genetic algorithm is proposed to solve the problem approximately, which belongs to non-deterministic polynomial-time (NP)-hard class. The solution procedure is categorized through methods where various solutions are found and then, the decision-makers select the most adequate (a posteriori approach). Taguchi method is applied to set the parameters of proposed algorithm. To demonstrate the validation of proposed algorithm, the full enumeration algorithm is used to find the Pareto-optimal front for special small problems. To show the efficiency and effectiveness of the proposed algorithm in comparison with other efficient algorithm in the literature (namely MLPGA) on our problem, the experiments were conducted on three dimensions of problems: small, medium and large. Computational results are expressed in terms of standard multi-objective metrics. The results show that the proposed algorithm is able to obtain more diversified and competitive Pareto sets than the MLPGA.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  • Allahverdi A, Gupta JND, Aldowaisan T (1999) A review of scheduling research involving setup considerations. OMEGA Int J Manag Sci 27(2):219–239

    Article  Google Scholar 

  • Allahverdi A, Ng CT, Cheng TCE, Kovalyov MY (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3):985–1032

    Article  Google Scholar 

  • Andrés C, Albarracín JM, Tormo G, Vicens E, García-Sabater JP (2005) Group technology in a hybrid flowshop environment: a case study. Eur J Oper Res 167:272–281

    Article  Google Scholar 

  • Arthanary TS, Ramaswamy KG (1971) An extension of two machine sequencing problems. Oper Res 8(1):10–22

    Google Scholar 

  • Attar SF, Mohammadi M, Tavakkoli-Moghaddam R, Yaghoubi S (2014) Solving a new multi-objective hybrid flexible flowshop problem with limited waiting times and machine-sequence-dependent set-up time constraints. Int J Comput Integr Manuf 27(5):450–469

    Article  Google Scholar 

  • Bagchi TP (1999) Multi-objective scheduling by genetic algorithms. Kluwer, Boston

    Book  Google Scholar 

  • Behnamian J, Zandieh M (2013) Earliness and tardiness minimizing on a realistic hybrid flowshop scheduling with learning effect by advanced metaheuristic. Arab J Sci Eng 38:1229–1242

    Article  Google Scholar 

  • 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:11057–11069

    Article  Google Scholar 

  • Biskup DA (1999) Single machine scheduling with learning considerations. Eur J Oper Res 115(1):173–178

    Article  Google Scholar 

  • Biskup DA (2008) A state-of-the-art review on scheduling with learning effects. Eur J Oper Res 188:315–329

    Article  Google Scholar 

  • Chang PC, Hsieh JC, Wang YW (2003) Genetic algorithms applied in BOPP film scheduling problems: minimizing total absolute deviation and setup times. Appl Soft Comput 3:139–148

    Article  Google Scholar 

  • Cho H-M, Bae S-J, Kim J, Jeong I-J (2011) Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm. Comput Ind Eng 61:529–541

    Article  Google Scholar 

  • Corne DW, Knowles JD, Oates MJ (2000) The Pareto envelope based selection algorithm for multi-objective optimization. In: Proceedings of the parallel problem solving from nature VI conference, Springer Lecture Notes in Computer Science, vol 1917/2000, pp 839–848

  • Corne DW, Jerram NR, Knowles JD, Oates MJ (2001) PESA-II: region-based selection in evolutionary multiobjective optimization. In: Proceedings of the genetic and evolutionary computation conference, (GECCO-2001). Morgan Kaufmann, San Francisco, CA, pp 283–290

  • Davoudpour H, Ashrafi M (2009) Solving multi-objective SDST flexible flow shop using GRASP algorithm. Int J Adv Manuf Technol 44(7–8):737–747

    Article  Google Scholar 

  • Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multi-objective genetic algorithm: NSGA II. IEEE Trans Evolut Comput 6(2):182–197

    Article  Google Scholar 

  • Dugardin F, Yalaoui F, Amodeo L (2010) New multi-objective method to solve reentrant hybrid flow shop scheduling problem. Eur J Oper Res 203:22–31

    Article  Google Scholar 

  • Fadaei M, Zandieh M (2013) Scheduling a bi-objective hybrid flow shop with sequence-dependent family setup times using metaheuristics. Arab J Sci Eng 38:2233–2244

    Article  Google Scholar 

  • Fonseca CM, Fleming PJ (1993) Genetic algorithms for multi-objective optimization: formulation, discussion and generalization. In: Proceedings of the fifth international conference on genetic algorithms, July 1993. Morgan Kaufmann, San Mateo, pp 416–423

  • Gupta JND (1988) Two-stage, hybrid flowshop scheduling problem. J Oper Res Soc 39(4):359–364

    Article  Google Scholar 

  • Hakimzadeh Abyaneh S, Zandieh M (2012) Bi-objective hybrid flow shop scheduling with sequence-dependent setup times and limited buffers. Int J Adv Manuf Technol 58:309–325

    Article  Google Scholar 

  • Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan, Ann Arbor

    Google Scholar 

  • Horn J, Nafpliotis N, Goldberg DE (1994) A niched Pareto genetic algorithm for multi-objective optimization. In: Proceedings of the 1st IEEE-ICEC conference, computational computation, 27–29 June 1994, Orlando, FL, vol 1, pp 82–87

  • Hyun CJ, Kim Y, Kim YK (1998) A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines. Comput Oper Res 25(7–8):675–690

    Article  Google Scholar 

  • Ishibuchi H, Murata T (1998) A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans Syst Manuf Cybern 28(3):392–403

    Article  Google Scholar 

  • Jolai F, Asefi H, Rabiee M, Ramezani P (2013) Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem. Sci Iran E 20(3):861–872

    Google Scholar 

  • 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(3–4):354–370

    Article  Google Scholar 

  • Jungwattanakit J, Reodecha M, Chaovalitwongse P, Werner F (2009) A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Comput Oper Res 36(2):358–378

    Article  Google Scholar 

  • Karimi N, Zandieh M, Karamooz HR (2010) Bi-objective group scheduling in hybrid flexible flowshop: a multi-phase approach. Expert Syst Appl 37(6):4024–4032

    Article  Google Scholar 

  • Knowles JD, Corne DW (1999) The Pareto archived evolution strategy: a new baseline algorithm for multiobjective optimization. In: Proceedings of the 1999 congress on evolutionary computation, 6–9 July, IEEE Service Center, Washington, DC, pp 98–105

  • Lin D, Lee CKM (2011) A review of the research methodology for the re-entrant scheduling problem. Int J Prod Res 49(8):2221–2242

    Article  Google Scholar 

  • Mousavi SM, Zandieh M, Amiri M (2011a) An efficient bi-objective heuristic for scheduling of hybrid flow shops. Int J Adv Manuf Technol 54(1–4):287–307

    Article  Google Scholar 

  • Mousavi SM, Zandieh M, Amiri M (2011b) Comparisons of bi-objective genetic algorithms for the hybrid flowshop scheduling with sequence-dependent setup times. Int J Prod Res 50(10):2570–2591

    Article  Google Scholar 

  • Mousavi SM, Mousakhani M, Zandieh M (2012a) Bi-objective hybrid flow shop scheduling: a new local search. Int J Adv Manuf Technol 64(5–8):933–950

    Google Scholar 

  • Mousavi SM, Zandieh M, Yazdani M (2012b) A simulated annealing/local search to minimize the makespan and total tardiness on a hybrid flowshop. Int J Adv Manuf Technol 64(1–4):369–388

    Google Scholar 

  • Naderi B, Zandieh M, Balagh AKG, Roshanaei V (2009a) An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Syst Appl 36(6):9625–9633

    Article  Google Scholar 

  • Naderi B, Zandieh M, Roshanaei V (2009b) Scheduling hybrid flowshops with sequence-dependent setup times to minimize makespan and maximum tardiness. Int J Adv Manuf Technol 41:1186–1198

    Article  Google Scholar 

  • Pargar F, Zandieh M (2012) Bi-criteria SDST hybrid flow shop scheduling with learning effect of setup times: water flow-like algorithm approach. Int J Prod Res 50(10):2609–2623

    Article  Google Scholar 

  • Pasupathy T, Rajendran C, Suresh RK (2007) A multi-objective genetic algorithm for scheduling in flowshops to minimize the makespan and total flow time of jobs. Int J Adv Manuf Technol 27(7–8):804–815

    Google Scholar 

  • Pinedo ML (1995) Scheduling theory, algorithms, and systems. Prentice-Hall, Englewood Cliffs

    Google Scholar 

  • Pinedo ML (2008) Theory, algorithms, and systems, 3rd edn. Springer Science + Business Media, New York

    Google Scholar 

  • Rashidi E, Jahandar M, Zandieh M (2010) 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

    Article  Google Scholar 

  • Ruiz R, Vázquez-Rodríguez JA (2010) The hybrid flow shop scheduling problem. Eur J Oper Res 205:1–18

    Article  Google Scholar 

  • Ruiz-Torres AJ, Lopez FJ (2004) Using the FDH formulation of DEA to evaluate a multi-criteria problem in parallel machine scheduling. Comput Ind Eng 47:107–121

    Article  Google Scholar 

  • Schaffer JD (1985) Multi-objective optimization with vector evaluated genetic algorithms. In: Grefenstette J (ed) Proceedings of the international conference on genetic algorithms and their applications. Lawrence Erlbaum, Hillsdale, pp 93–100

  • Srinivas N, Deb K (1995) Multi-objective function optimization using non-dominated sorting genetic algorithms. IEEE Trans Evol Comput 2(3):221–248

    Google Scholar 

  • Wang S, Liu M (2014) Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabu search method. Int J Prod Res 52(5):1495–1508

    Article  Google Scholar 

  • Wang MY, Sethi SP, Van de Velde SL (1997) Minimizing makespan in a class of reentrant shops. Oper Res 45(5):702–712

    Article  Google Scholar 

  • Ying KC, Lin SW, Wan SY (2014) Bi-objective reentrant hybrid flowshop scheduling: an iterated Pareto greedy algorithm. Int J Prod Res. doi:10.1080/00207543.2014.910627

    Google Scholar 

  • Zitzler E, Thiele L (1999) Multi-objective evolutionary algorithm: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):251–257

    Article  Google Scholar 

  • Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength Pareto evolutionary algorithm. Report 103. Computer Engineering and Networks Laboratory (TIK), Zurich

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran

    S. M. Mousavi, I. Mahdavi & J. Rezaeian

  2. Department of Industrial Management, Management and Accounting Faculty, Shahid Beheshti University, G. C., Tehran, Iran

    M. Zandieh

Authors
  1. S. M. Mousavi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. I. Mahdavi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J. Rezaeian
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. M. Zandieh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. M. Mousavi.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mousavi, S.M., Mahdavi, I., Rezaeian, J. et al. An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling with learning effect and setup times. Oper Res Int J 18, 123–158 (2018). https://doi.org/10.1007/s12351-016-0257-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12351-016-0257-6

Keywords

Search

Navigation