Job Shop Scheduling Using Hybrid Genetic Algorithm

Authors(2) :-Basavaraj Shrikanth Vijapure, Ajay Nadargi

Genetic algorithms are a very popular heuristic which have been successfully applied to many optimization problems within the last 30 years. In this chapter, we give a survey on some genetic algorithms for shop scheduling problems. In a shop scheduling problem, a set of jobs has to be processed on a set of machines such that a specific optimization criterion is satisfied. According to the restrictions on the technological routes of the jobs, we distinguish a flow shop (each job is characterized by the same technological route), a job shop (each job has a specific route) and an open shop (no technological route is imposed on the jobs). We also consider some extensions of shop scheduling problems such as hybrid or flexible shops (at each processing stage, we may have a set of parallel machines) or the inclusion of additional processing constraints such as controllable processing times, release times, setup times or the no-wait condition. After giving an introduction into basic genetic algorithms discussing briefly solution representations, the generation of the initial population, selection principles, the application of genetic operators such as crossover and mutation, and termination criteria, we discuss several genetic algorithms for the particular problem types emphasizing their common features and differences. Here we mainly focus on single-criterion problems (minimization of the makespan or of a particular sum criterion such as total completion time or total tardiness) but mention briefly also some work on multi-criteria problems. We discuss some computational results and compare them with those obtained by other heuristics. In addition, we also summarize the generation of benchmark instances for makespan problems and give a brief introduction into the use of the program package íLiSA - A Library of Scheduling Algorithmsí developed at the Otto-von-Guericke-University Magdeburg for solving shop scheduling problems, which also includes a genetic algorithm.

Authors and Affiliations

Basavaraj Shrikanth Vijapure
Department of Computer Enginnering, Sinhgad Institute of Technology, Savitribhai Phule University, Pune, Maharashtra, India
Ajay Nadargi
Department of Computer Enginnering, Sinhgad Institute of Technology, Savitribhai Phule University, Pune, Maharashtra, India

Job Shop, Scheduling, Genetic Algorithm, Hybird Scheduler

  1. Adams, J.; Balas, E.; and Zawack, D. 1988. The shifting bottleneck procedure for job shop scheduling. Managament Science 34:391-401.
  2. Applegate, D., and Cook, W. 1991. A computational study of the job-shop scheduling problem. ORSA Journal of Computing 3:149-156.
  3. Artigues, C., and Lopez, P. 2000. Extending GifflerThompson algorithm to generate active schedules for jobshops with sequence-dependent setup times. LIA report 129, University of Avignon.
  4. Artigues, C.; Lopez, P.; and Ayache, P. 2005. Schedule generation schemes for the job shop problem with sequence-dependent setup times: Dominance properties and computational analysis. Annals of Operations Research 138:21-52
  5. Artigues, C., and Feillet, D. 2008. A branch and bound method for the job-shop problem with sequence-dependent setup times. Annals of Operations Research 159(1):135-159.
  6. Balas, E., and Vazacopoulos, A. 1998. Guided local search with shifting bottleneck fo job shop scheduling. Management Science 44 (2):262-275

Publication Details

Published in : Volume 4 | Issue 8 | May-June 2018
Date of Publication : 2018-06-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 568-573
Manuscript Number : IJSRSET1848161
Publisher : Technoscience Academy

Print ISSN : 2395-1990, Online ISSN : 2394-4099

Cite This Article :

Basavaraj Shrikanth Vijapure, Ajay Nadargi, " Job Shop Scheduling Using Hybrid Genetic Algorithm, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 4, Issue 8, pp.568-573, May-June-2018.
Journal URL : http://ijsrset.com/IJSRSET1848161

Follow Us

Contact Us