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

Skip to main content

A Genetic Algorithm for Scheduling of Jobs on Lines of Press Machines

  • Conference paper
Large-Scale Scientific Computing (LSSC 2005)

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

Included in the following conference series:

Abstract

This paper introduces a Genetic Algorithm (GA) based solution technique for press machines scheduling problem of a car manufacturing factory. Firstly, the problem at hand, and the application of the GA in terms of coding, chromosome evaluation, crossover and mutation operators, are described in detail. After that, the GA is experimentally evaluated through some test problems. As the objective of the problem is the minimization of the completion time of the jobs, the GA based solution is compared with the Longest Processing Time (LPT) rule, and it is observed that the GA always produces better schedules than the LPT rule in a reasonably short amount of CPU time.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.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.

Similar content being viewed by others

References

  1. Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Weglarz, J.: Scheduling Computer and Manufacturing Processes. Springer, Berlin (1996)

    MATH  Google Scholar 

  2. Blazewicz, J., Cellary, W., Slowinski, R., Weglarz, J.: Scheduling Under Resource Constraints: Deterministic Models. Annals of Operations Research 7, 11–93 (1986)

    Google Scholar 

  3. Cheng, R., Gen, M.: Parallel Machine Scheduling Problems Using Memetic Algorithms. Comp. Ind. Eng. 33, 761–764 (1997)

    Article  Google Scholar 

  4. Cochran, J.K., Horng, S.M., Fowler, J.W.: A Multi-Population Genetic Algorithm to Solve Multi-Objective Scheduling Problems for Parallel Machines. Computers & Operations Research 30, 1087–1102 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  5. Emel, E., Tasci, H.B.E.: An Optimization Approach for Scheduling of Jobs on Lines of Press Machines. In: The 6th Industrial Eng. Research Conference, Florida (1997)

    Google Scholar 

  6. Garey, M.R., Graham, R.L., Johnson, D.S.: Performance Guarantees for Scheduling Algorithms. Operations Research 26, 3–21 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  7. Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, Reading (1989)

    Google Scholar 

  8. Holland, J.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975); MIT Press, Cambridge (1992)

    Google Scholar 

  9. Lenstra, J.K.: Sequencing by Enumerative Methods. Mathematical Centre Tracts 69, 18–39 (1985)

    Google Scholar 

  10. Lenstra, J.K., Rinnooy Kan, A.H.G.: Complexity of Scheduling Under Precedence Constraints. Operations Research 26, 22–35 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  11. Michalewicz, Z.: Genetic Algorithm+Data Structure=Evolution Programs, 3rd edn. Springer, New York (1996)

    Google Scholar 

  12. Min, L., Cheng, W.: A Genetic Algorithm for Minimizing the Makespan in the Case of Scheduling Identical Parallel Machines. Artif. Intel. Eng. 13, 399–403 (1999)

    Article  Google Scholar 

  13. Ozalp, S.A.: Modeling and Scheduling of Jobs on Lines of Press Machines: A Heuristic Approach. In: 5th EUROSIM Congress on Modeling and Simulation, ESIEE, Paris (2004)

    Google Scholar 

  14. Ozel, S.A.: Programming of Production Scheduling Algorithms. MSc Thesis, Uludag University, Industrial Engineering Department, Bursa (1999)

    Google Scholar 

  15. Peng, J., Liu, B.: Parallel Machine Scheduling Models with Fuzzy Processing Times. Information Sciences 166, 49–66 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  16. Pinedo, M.: Scheduling: Theory, Algorithms and Systems. Prentice Hall, New Jersey (1995)

    MATH  Google Scholar 

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

    Google Scholar 

  18. Sethi, R.: On the Complexity of Mean Flow Time Scheduling. Mathematics of Operations Research 2, 320–330 (1977)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ozalp, S.A. (2006). A Genetic Algorithm for Scheduling of Jobs on Lines of Press Machines. In: Lirkov, I., Margenov, S., Waśniewski, J. (eds) Large-Scale Scientific Computing. LSSC 2005. Lecture Notes in Computer Science, vol 3743. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11666806_61

Download citation

  • DOI: https://doi.org/10.1007/11666806_61

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-31994-8

  • Online ISBN: 978-3-540-31995-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics