Skip to main content
SpringerLink
Log in

Evolutionary Clustering Search for Flowtime Minimization in Permutation Flow Shop

  • Conference paper
Hybrid Metaheuristics (HM 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4771))

Included in the following conference series:

Abstract

This paper deals with the Permutation Flow Shop scheduling problem with the objective of minimizing total flow time, and therefore reducing in-process inventory. A new hybrid metaheuristic Genetic Algorithm - Cluster Search is proposed for the scheduling problem solution. The performance of the proposed method is evaluated and results are compared with the best reported in the literature. Experimental tests show the new method superiority for the test problems set, regarding the solution quality.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Garey, M.R., Johnson, D.S., Sethi, R.: The Complexity of flowshop and jobshop scheduling. Mathematics of Operations Research 1, 117–129 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  2. Rinnooy Kan, A.H.G.: Machine Scheduling Problems: Classification, Complexity, and Computations. Nijhoff, The Hahue (1976)

    Google Scholar 

  3. Ahmadi, R.H., Bagchi, U.: Improved lower bounds for minimizing the sum of completion times of n jobs over m machines. European Journal of Operational Research 44, 331–336 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  4. Rajendran, C., Chaudhuri, D.: An efficient heuristic approach to the scheduling of jobs in a flowshop. European Journal of Operational Research 61, 318–325 (1991)

    Article  Google Scholar 

  5. Rajendran, C.: Heuristic algorithm for scheduling in a flowshop to minimise total flowtime. International Journal Production Economics 29, 65–73 (1993)

    Article  Google Scholar 

  6. Ho, J.C.: Flowshop sequencing with mean flowtime objective. European Journal of Operational Research 81, 571–578 (1995)

    Article  MATH  Google Scholar 

  7. Wang, C., Chu, C., Proth, J.M.: Heuristic approaches for n/m/F/ Ci scheduling problems. European Journal of Operational Research 96, 636–644 (1997)

    Article  MATH  Google Scholar 

  8. Woo, D.S., Yim, H.S.: A heuristic algorithm for mean flowtime objective in flowshop scheduling. Computers and Operations Research 25, 175–182 (1998)

    Article  MATH  Google Scholar 

  9. Liu, J., Reeves, C.R.: Constructive and composite heuristic solutions to the P// ∑ C i scheduling problem. European Journal of Operational Research 132, 439–452 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  10. Allahverdi, A., Aldowaisan, T.: New heuristics to minimize total completion time in m-machine flowshops. International Journal of Production Economics 77, 71–83 (2002)

    Article  Google Scholar 

  11. Framinan, J.M., Leisten, R.: An efficient constructive heuristic for flowtime minimisation in permutation flow shop. OMEGA 31, 311–317 (2003)

    Article  Google Scholar 

  12. Framinan, J.M., Leisten, R., Ruiz-Usano, R.: Comparison of heuristics for flowtime minimisation in permutation flowshops. Computer and Operations Research 32, 1237–1254 (2005)

    MATH  Google Scholar 

  13. Li, X., Wang, Q., Wu, C.: Efficient composite heuristics for total flowtime minimization in permutation flow shops. Omega (2006), doi: 10.1016-j.omega.2006.11.003

    Google Scholar 

  14. Nagano, M.S., Moccellin, J.V.: Reducing mean flow time in permutation flow shop. Journal of the Operational Research Society (2007), doi: 10.1057/palgrave.jors.2602395

    Google Scholar 

  15. Rajendran, C., Ziegler, H.: Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research 155, 426–438 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  16. Tasgetiren, M.F., Liang, Y.C., Sevkli, M., Gencyilmaz, G.: A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research 177, 1930–1947 (2007)

    Article  MATH  Google Scholar 

  17. Stutzle, T.: Applying iterated local search to the permutation flowshop problem. Technical Report, AIDA-98-04, Darmstad University of Technology, Computer Science Department, Intelletics Group, Darmstad, Germany (1998)

    Google Scholar 

  18. Merkle, D., Middendorf, M.: An ant algorithm with a new pheromone evaluation rule for total tardiness problems. In: Oates, M.J., Lanzi, P.L., Li, Y., Cagnoni, S., Corne, D.W., Fogarty, T.C., Poli, R., Smith, G.D. (eds.) EvoWorkshops 2000. LNCS, vol. 1803, pp. 287–296. Springer, Heidelberg (2000)

    Google Scholar 

  19. Taillard, E.: Benchmarks for basic scheduling problems. European Journal of Operational Research 64, 278–285 (1993)

    Article  MATH  Google Scholar 

  20. Cotta, C., Fernandez, A.J.: Memetic Algorithms in Planning, Scheduling and Timetabling. Evolutionary Schedulling, pp. 1–30. Springer, Heidelberg (2006)

    Google Scholar 

  21. Kleeman, M.P., Lamont, G.B.: Scheduling of flow-shop, job-shop, and combined scheduling problems using MOEAs with fixed and variable length chromosomes. In: Evolutionary Schedulling, pp. 49–100. Springer, Heidelberg (2006)

    Google Scholar 

  22. Bean, J.C.: Genetic algorithm and random keys for sequencing and optimization. ORSA Journal on Computing 6, 154–160 (1994)

    MATH  Google Scholar 

  23. Watson, J.P., Barbulescu, L., Whitley, L.D., Howe, A.E.: Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance. ORSA Journal of Computing 14, 98–123 (2002)

    MathSciNet  Google Scholar 

  24. Oliveira, A.C.M., Lorena, L.A.N.: Detecting promising areas by evolutionary clustering search. In: Bazzan, A.L.C., Labidi, S. (eds.) Advances in Artificial Intelligence. LNCS (LNAI), pp. 385–394. Springer, Heidelberg (2004)

    Google Scholar 

  25. Oliveira, A.C.M., Lorena, L.A.N.: Hybrid evolutionary algorithms and clustering search. In: Grosan, C., Abraham, A., Ishibuchi, H. (eds.) Hybrid Evolutionary Systems - Studies in Computational Intelligence. SCI Series, vol. 75, pp. 81–102. Springer, Heidelberg (2007)

    Google Scholar 

  26. Nawaz, M., Enscore, E.E., Ham, I.: A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA 11, 91–95 (1983)

    Article  Google Scholar 

  27. Glover, F.: Tabu search and adaptive memory programing: Advances, applications and challenges. In: Interfaces in Computer Science and Operations Research, pp. 1–75. Kluwer Academic Publishers, Dordrecht (1996)

    Google Scholar 

  28. Syswerda, G.: Uniform crossover in genetic algorithms. In: International Conference on Genetic Algorithms (ICGA), Virginia, USA, pp. 2–9 (1989)

    Google Scholar 

  29. Cotta, C., Troya, J.M.: Genetic Forma Recombination in Permutation Flowshop Problems. Evolutionary Computation 6, 25–44 (1998)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculdade Bandeirantes de Educação Superior, R. José Correia Gonçalves, 57, 08675-130, Suzano - SP, Brazil

    Geraldo Ribeiro Filho

  2. Escola de Engenharia de São Carlos - USP, Av. Trabalhador São-Carlense, 400, 13566-590, São Carlos - SP, Brazil

    Marcelo Seido Nagano

  3. Instituto Nacional de Pesquisas Espaciais - INPE/LAC, Av. dos Astronautas, 1758, 12227-010, São José dos Campos - SP, Brazil

    Luiz Antonio Nogueira Lorena

Authors
  1. Geraldo Ribeiro Filho
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marcelo Seido Nagano
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Luiz Antonio Nogueira Lorena
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Thomas Bartz-Beielstein María José Blesa Aguilera Christian Blum Boris Naujoks Andrea Roli Günter Rudolph Michael Sampels

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Filho, G.R., Nagano, M.S., Lorena, L.A.N. (2007). Evolutionary Clustering Search for Flowtime Minimization in Permutation Flow Shop. In: Bartz-Beielstein, T., et al. Hybrid Metaheuristics. HM 2007. Lecture Notes in Computer Science, vol 4771. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75514-2_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-75514-2_6

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-75513-5

  • Online ISBN: 978-3-540-75514-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation