[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

A new genetic algorithm for lot-streaming flow shop scheduling with limited capacity buffers

  • Published:
Journal of Intelligent Manufacturing Aims and scope Submit manuscript

Abstract

Lot-streaming is the process of splitting a job (lot) into a number of smaller sublots to allow the overlapping of operations between successive machines in a multi-stage production system. The use of sublots usually results in substantially shorter job completion times for the corresponding schedule. A new genetic algorithm (NGA) is proposed for an n-job, m-machine, lot-streaming flow shop scheduling problem with equal size sublots and limited capacity buffers with blocking in which the objective is to minimize total earliness and tardiness penalties. NGA replaces the selection and mating operators of genetic algorithms (GAs), which often lead to premature convergence, by new operators (marriage and pregnancy operators) and also adopts the idea of inter-chromosomal dominance and individuals’ similarities. Extensive computational experiments have been conducted to compare the performance of NGA with that of GA. The results show that, on the average, NGA outperforms GA by 9.86 % in terms of objective function value for medium to large-scale lot-streaming flow-shop scheduling problems.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Balakrishnan P. V., Jacob V. S. (1996) Genetic algorithms for product design. Management Science 42(8): 1105–1117

    Article  Google Scholar 

  • Benjaafar S. (1996) On production batches, transfer batches, and lead times. IIE Transactions 28(5): 357–362

    Article  Google Scholar 

  • Bonabeau E., Dorigo M., Theraulaz G. (1999) Swarm intelligence: From natural to artificial systems. Oxford University Press, New York

    Google Scholar 

  • Buscher U., Shen L. (2009) An integrated Tabu search algorithm for the lot streaming problem in job-shops. European Journal of Operational Research 199(1): 385–399

    Article  Google Scholar 

  • Cetinkaya F. C., Duman M. (2010) Lot streaming in a two-machine mixed shop. International Journal of Advanced Manufacturing Technology 49: 1161–1173

    Article  Google Scholar 

  • Chan F. T. S., Wong T. C., Chan L.Y. (2009) The application of genetic algorithms to lot streaming in a job-shop scheduling problem. International Journal of Production Research 47(12): 3387–3412

    Article  Google Scholar 

  • Chang J. H., Chiu H. N. (2005) A comprehensive review of lot streaming. International Journal of Production Research 43(8): 1515–1536

    Article  Google Scholar 

  • Chen J., Steiner G. (1996) Lot streaming with detached setups in three-machine flow-shops. European Journal of Operational Research 96(3): 591–611

    Article  Google Scholar 

  • Choudhary A. K., Harding J. A., Tiwari M. K. (2009) Data mining in manufacturing: a review based on the kind of knowledge. Journal of Intelligent Manufacturing 20: 501–521

    Article  Google Scholar 

  • Dauzère-Pérès S., Lasserre J.-B. (1997) Lot streaming in job-shop scheduling. Operations Research 45(4): 584–595

    Article  Google Scholar 

  • Edis R. S., Ornek M. A. (2009) A Tabu search-based heuristic for single-product lot streaming problems in flow shops. International Journal of Advanced Manufacturing Technology 43: 1202–1213

    Article  Google Scholar 

  • Elbaum R., Sidi M. (1996) Topological design of local area networks using genetic algorithms. IEEE/ACM Transactions on Networking 4(5): 766–778

    Article  Google Scholar 

  • Gen M., Cheng R. (2000) Genetic algorithms and engineering optimization. Wiley, Hoboken, NJ

    Google Scholar 

  • Gendreau, M., Potvin, J.-Y. (eds) (2010) Handbook of metaheuristics (2nd ed.). Springer, Berlin

    Google Scholar 

  • Glass C. A., Potts C. N. (1998) Structural properties of lot streaming in a flow-shop. Mathematics of Operations Research 23(3): 624–639

    Article  Google Scholar 

  • Glover, F. W., Kochenberger, G. A. (eds) (2003) Handbook of metaheuristics. Kluwer, Norwell, MA

    Google Scholar 

  • Goldberg D. E. (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, New York

    Google Scholar 

  • Goldberg, D. E., & Lingle, R. (1985). Alleles, loci, and the traveling salesman problem. In J. J. Grefenstette (Ed.), Proceedings of the 1st international conference on genetic algorithms and their applications, July 24–26, 1985, Pittsburgh, PA (pp. 154–159). Hillsdale, NJ: Lawrence Erlbaum.

  • Goren H. G., Tunali S., Jans R. (2010) A review of applications of genetic algorithms in lot sizing. Journal of Intelligent Manufacturing 21: 575–590

    Article  Google Scholar 

  • Hall N. G., Laporte G., Selvarajah E., Sriskandrajah C. (2003) Scheduling and lot streaming in flow-shops with no-wait in process. Journal of Scheduling 6: 339–354

    Article  Google Scholar 

  • Hall N. G., Posner M. E. (2001) Generating experimental data for computational testing with machine scheduling applications. Operations Research 49(6): 854–865

    Article  Google Scholar 

  • Kalir A. A., Sarin S. C. (2000) Evaluation of the potential benefits of lot streaming in flow-shop systems. International Journal of Production Economics 66(2): 131–142

    Article  Google Scholar 

  • Kalir A. A., Sarin S. C. (2003) Constructing near optimal schedules for the flow-shop lot streaming problem with sublot-attached setups. Journal of Combinatorial Optimization 7(1): 23–44

    Article  Google Scholar 

  • Liepins G. E., Hilliard M. R. (1989) Genetic algorithms: Foundation and applications. Annals of Operations Research 21(1–4): 31–58

    Article  Google Scholar 

  • Marimuthu S., Ponnambalam S. G., Jawahar N. (2008) Evolutionary algorithms for scheduling m-machine flow shop with lot streaming. Robotics and Computer-Integrated Manufacturing 24(1): 125–139

    Article  Google Scholar 

  • Meeran, S., & Morshed, M. S. (2011). A hybrid genetic Tabu search algorithm for solving job shop scheduling problems: A case study. Journal of Intelligent Manufacturing, published online: March 8, 2011.

  • Moily J. P. (1986) Optimal and heuristic procedures for component lot-splitting in multi-stage manufacturing systems. Management Science 32(1): 113–125

    Article  Google Scholar 

  • Morad N., Zalzala A. (1999) Genetic algorithms in integrated process planning and scheduling. Journal of Intelligent Manufacturing 10: 169–179

    Article  Google Scholar 

  • Potts C. N., Van Wassenhove L. N. (1992) Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. Journal of the Operational Research Society 43(5): 395–406

    Google Scholar 

  • Reeves, C. R. (ed) (1993) Modern heuristic techniques for combinatorial problems. Halsted Press, New York

    Google Scholar 

  • Şen A., Topaloğlu E., Benli Ö.S. (1998) Optimal streaming of a single job in a two-stage flow-shop. European Journal of Operational Research 110(1): 42–62

    Article  Google Scholar 

  • Srinivas M., Patnaik L. M. (1994) Genetic algorithms: A survey. Computer 27(6): 17–26

    Article  Google Scholar 

  • Sriskandarajah C., Wagneur E. (1999) Lot streaming and scheduling multiple products in two-machine no-wait flow-shops. IIE Transactions 31(8): 695–707

    Google Scholar 

  • Talbi E.-G. (2009) Metaheuristics: From design to implementation. Wiley, Hoboken, NJ

    Google Scholar 

  • Trietsch D., Baker K. R. (1993) Basic techniques for lot streaming. Operations Research 41(6): 1065–1076

    Article  Google Scholar 

  • Truscott W. G. (1985) Scheduling production activities in multi-stage batch manufacturing systems. International Journal of Production Research 23(2): 315–328

    Article  Google Scholar 

  • Tseng C.-T., Liao C.-J. (2008) A discrete particle swarm optimization for lot-streaming flow-shop scheduling problem. European Journal of Operational Research 191(1): 360–373

    Article  Google Scholar 

  • Yoon S.-H., Ventura J.A. (2002) An application of genetic algorithms to lot-streaming flow-shop scheduling. IIE Transactions 34(9): 779–787

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Harold and Inge Marcus Department of Industrial and Manufacturing Engineering, The Pennsylvania State University, University Park, PA, 16802, USA

    José A. Ventura

  2. Department of Industrial and Information Systems Engineering, Soongsil University, Dongjak-Gu, Seoul, 156-743, Korea

    Suk-Hun Yoon

Authors
  1. José A. Ventura
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Suk-Hun Yoon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to José A. Ventura.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ventura, J.A., Yoon, SH. A new genetic algorithm for lot-streaming flow shop scheduling with limited capacity buffers. J Intell Manuf 24, 1185–1196 (2013). https://doi.org/10.1007/s10845-012-0650-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10845-012-0650-9

Keywords

Search

Navigation