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

Advertisement

Springer Nature Link
Log in

Bi-objective scheduling of flexible flow lines: a gradual transition tabu search approach

  • Production Management
  • Published:
Production Engineering Aims and scope Submit manuscript

Abstract

This paper deals with flexible flow line scheduling problem. Studied researches of the literature assumed that either no setup has to be performed or that setup times are sequence-independent, chiefly. Besides, they are mostly conducted in single objective environment. Therefore, in this study, these two real world concepts are mimicked in the flow line model. The considered objectives of the proposed model are minimizing makespan and total tardiness. Due to the hard solvability of the problem, this research proposes a new multi-objective algorithm based on the single objective tabu search, called gradual transition tabu search (GTTS). GTTS is implemented in two phases and in each phase it tries to gradually modify one objective to the other objective. The neighborhood search efficiency is also improved by defining new candidate list strategies and implementing new dynamic tabu tenure. In addition, the results of the proposed algorithm are compared with two popular existing algorithms, called fast non-dominated sort genetic algorithm (NSGA-II) and multi-objective genetic algorithm, on a number of randomly generated test problems. The suitability of GTTS is demonstrated through different multi-objective evaluation metrics.

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
Fig. 7

Similar content being viewed by others

References

  1. Adler L, Fraiman N, Kobacker E, Pinedo M, Plotnicoff TP, Wu TP (1993) BPSS: a scheduling support system for the packaging industry. Oper Res 41(4):641–648

    Article  Google Scholar 

  2. Affenzeller M (2002) New generic hybrids based upon genetic algorithms. Lect Notes Comput Sci 2527:329–339

    Article  MATH  Google Scholar 

  3. Agnetis A, Pacifici A, Rossi F, Lucertini M, Nicoletti S, Nicolo F, Oriolo G, Pacciarelli D, Pesaro E (1997) Scheduling of flexible flow lines in an automobile assembly plant. Eur J Oper Res 97:348–362

    Article  MATH  Google Scholar 

  4. Arroyo JEC, Armentano VA (2005) Genetic local search for multi-objective flow shop scheduling problems. Eur J Oper Res 167:717–738

    Article  MathSciNet  MATH  Google Scholar 

  5. 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

    Article  MATH  Google Scholar 

  6. Bilge U, Kirac F, Kurtulan M, Pekgün P (2004) A tabu search algorithm for parallel machine total tardiness problem. Comput Oper Res 31:397–414

    Article  MATH  Google Scholar 

  7. Chang P-C, Chen S-H, Lin K-L (2005) Two-phase sub population genetic algorithm for parallel machine-scheduling problem. Expert Syst Appl 29(3):705–712

    Article  Google Scholar 

  8. Chang P-C, Chen S-H, Hsieh J-Ch (2006) A global archive sub-population genetic algorithm with adaptive strategy in multi-objective parallel-machine scheduling problem. Lect Notes Comput Sci 4221:730–739

    Article  Google Scholar 

  9. 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

    Article  MathSciNet  MATH  Google Scholar 

  10. Costamagna E, Fanni A, Giacinto G (1998) A tabu search algorithm for the optimization of telecommunication networks. Eur J Oper Res 106:357–372

    Article  MATH  Google Scholar 

  11. Deb K, Amrit Pratap SA, Meyarivan T (2000) A fast and elitist multi objective genetic algorithm-NSGA-II. In: Proceedings of the parallel problem solving from nature VI conference. Paris, France, September 2000, 849–858

  12. Ding FY, Kittichartphayak D (1994) Heuristics for scheduling flexible flow lines. Comput Ind Eng 26:27–34

    Article  Google Scholar 

  13. Du J, Leung JYT (1990) Minimizing total tardiness on one machine is NP-hard. Math Oper Res 15:483–495

    Article  MathSciNet  MATH  Google Scholar 

  14. Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1(2):117–129

    Article  MathSciNet  MATH  Google Scholar 

  15. Glover F (1989) Tabu search: part I. ORSA J Comput 1:190–206

    Article  MathSciNet  MATH  Google Scholar 

  16. Glover F (1990) Tabu search: part II. ORSA J Comput 2:4–32

    Article  MATH  Google Scholar 

  17. Guinet AGP, Solomon M (1996) Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time. Int J Prod Res 34(6):1643–1654

    Article  MATH  Google Scholar 

  18. Hu J, Goodman E, Seo K, Fan Z, Rosenberg R (2005) The hierarchical fair competition framework for sustainable evolutionary algorithms. Evol Comput 13(2):241–277

    Article  Google Scholar 

  19. Hübscher R, Glover F (1994) Applying tabu search with influential diversification to multiprocessor scheduling. Comput Oper Res 21(8):877–884

    Article  MATH  Google Scholar 

  20. Hung TSL, Ching JL (2003) A case study in a two-stage hybrid flow shop with setup time and dedicated machines. Int J Prod Econ 86:133–143

    Article  Google Scholar 

  21. James RJW, Buchanan JT (1998) Performance enhancements to tabu search for the early/tardy scheduling problem. Eur J Oper Res 106:254–265

    Article  MATH  Google Scholar 

  22. Kim S, Choi H, Lee D (2006) Tabu search heuristics for parallel machine scheduling with sequence-dependent setup and ready times. Lect Notes Comput Sci 3982:728–737

    Article  MATH  Google Scholar 

  23. Kis T, Pesch E (2005) A review of exact solution methods for the non-preemptive multiprocessor flowshop problem. Eur J Oper Res 164(3):592–608

    Article  MathSciNet  MATH  Google Scholar 

  24. Kochhar S, Morris RJ (1987) Heuristic methods for flexible flow line scheduling. J Manuf Syst 6(4):299–314

    Article  Google Scholar 

  25. Kurz ME, Askin RG (2003) Comparing scheduling rules for flexible flow lines. Int J Prod Econ 85:371–388

    Article  Google Scholar 

  26. Kurz ME, Askin RG (2004) Scheduling flexible flow lines with sequence-dependent setup times. Eur J Oper Res 159:66–82

    Article  MathSciNet  MATH  Google Scholar 

  27. Laguna M, Barnes JW, Glover F (1991) Tabu search methods for a single machine scheduling problem. J Intell Manuf 2:63–74

    Article  Google Scholar 

  28. Lee C-Y, Vairaktarakis GL (1993) Complexity of single machine hierarchical scheduling: a survey. In: Pardalos PM (ed) Complexity in numerical optimization. WorldScientific Publishing, Singapore, pp 269–298

    Chapter  Google Scholar 

  29. Leon VJ, Ramamoorthy B (1997) An adaptable problem-space based search method for flexible flow line scheduling. IIE Trans 29:115–125

    Google Scholar 

  30. Liaw C-F (1999) A tabu search algorithm for the open shop scheduling problem. Comput Oper Res 26:109–126

    Article  MathSciNet  MATH  Google Scholar 

  31. Montgomery DC (2000) Design and analysis of experiments, 5th edn. Wiley, New York

    Google Scholar 

  32. Mostaghim S, Teich J (2004) Covering Pareto-optimal fronts by subswarms in multiobjective particle swarm optimization. Evol Comput 2:1404–1411

    Google Scholar 

  33. Moursli O, Pochet Y (2000) A branch-and-bound algorithm for the hybrid flowshop. Int J Prod Econ 64:113–125

    Article  Google Scholar 

  34. Murata T, Ishibuchi H, Tanaka H (1996) Multi-objective genetic algorithm and its application to flow shop scheduling. Comput Ind Eng 30:957–968

    Article  Google Scholar 

  35. Norman BA, Bean JC (1999) A genetic algorithm methodology for complex scheduling problems. Nav Res Logist 46:199–211

    Article  MathSciNet  MATH  Google Scholar 

  36. Nowicki E, Smutnicki C (1998) The flow shop with parallel machines: a tabu search approach. Eur J Oper Res 106:226–253

    Article  MATH  Google Scholar 

  37. Park M-W, Kim Y-D (1997) Search heuristics for a parallel machine scheduling problem with ready times and due dates. Comput Ind Eng 33:793–796

    Article  Google Scholar 

  38. 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

    Article  Google Scholar 

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

    MATH  Google Scholar 

  40. Riane F (1998) Scheduling hybrid flowshops: algorithms and applications. Ph.D. Thesis, Faculte’s Universitaires Catholiquesde Mons

  41. Quadt D, Kuhn H (2005) A conceptual framework for lotsizing and scheduling of flexible flow lines. Int J Prod Res 43(11):2291–2308

    Article  MATH  Google Scholar 

  42. Rios-Mercado RZ, Bard JF (1998) Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups. Comput Oper Res 25(5):351–366

    Article  MATH  Google Scholar 

  43. Salvador MS (1973) A solution to a special class of flow shop scheduling problems. In: Elmaghraby SE (ed) Symposium on the theory of scheduling and its applications. Springer, Berlin, pp 83–91

    Chapter  Google Scholar 

  44. Sawik TJ (1993) A scheduling algorithm for flexible flow lines with limited intermediate buffers. Appl Stoch Models Data Anal 9(2):127–138

    Article  Google Scholar 

  45. Sawik TJ (1994) New algorithms for scheduling flexible flow lines. In: Proceedings of Japan–USA symposium on flexible automation, Kobe 3, 1091–1096

  46. Sawik TJ (1995) Scheduling flexible flow lines with no in-process buffers. Int J Prod Res 33(5):1357–1367

    Article  MATH  Google Scholar 

  47. Schaffer JD (1985) Multiple objective optimization with vector evaluated genetic algorithms. In: Proceedings of first international conference on genetic algorithms and their applications. Carnegie-Mellon University, Pittsburgh, PA, USA, 93–100

  48. Srikar BN, Ghosh S (1986) A MILP model for the N-job, M-stage flowshop with sequence dependent set-up times. Int J Prod Res 24(6):1459–1474

    Article  MATH  Google Scholar 

  49. Srinivas N, Deb K (1994) Multi-objective optimization using non-dominated sorting in genetic algorithms. Evol Comput 2(3):221–248

    Article  Google Scholar 

  50. Torabi SA, Fatemi Ghomi SMT, Karimi B (2005) A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling in supply chains. Eur J Oper Res 173:173–189

    Article  MathSciNet  MATH  Google Scholar 

  51. Veldhuizen DAV, Lamont GB (1998) Evolutionary computation and convergence to a Pareto front. In: Koza JR (edr) Late breaking papers at the genetic programming 1998 conference, Stanford University, California, July 1998. Stanford University Bookstore, 221–228

  52. Wittrock RJ (1988) An adaptable scheduling algorithm for flexible flow lines. Oper Res 36(4):445–453

    Article  MATH  Google Scholar 

  53. Zandieh M, Fatemi Ghomi SMT, Moattar Husseini SM (2006) An immune algorithm approach to hybrid flowshops scheduling with sequence-dependent setup times. Appl Math Comput 180:111–127

    MathSciNet  MATH  Google Scholar 

  54. Zitzler E, Laumanns M, Bleuler S (2004) A tutorial on evolutionary multiobjective optimization. In: Proceedings of the workshop on multiple objective meta-heuristics (MOMH 2002). Springer, Paris, France, June 2002, 3–38

Download references

Author information

Authors and Affiliations

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

    M. Zandieh

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

    M. B. Abiri

  3. Department of Industrial and Mechanical Engineering, Qazvin Islamic Azad University, Qazvin, Iran

    Seyed Habib A. Rahmati

Authors
  1. M. Zandieh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. B. Abiri
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Seyed Habib A. Rahmati
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Zandieh.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zandieh, M., Abiri, M.B. & Rahmati, S.H.A. Bi-objective scheduling of flexible flow lines: a gradual transition tabu search approach. Prod. Eng. Res. Devel. 10, 477–488 (2016). https://doi.org/10.1007/s11740-016-0679-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11740-016-0679-2

Keywords

Search

Navigation