JOB Shop Scheduling using Genetic Algorithm
Abstract
Scheduling is defined as the problem of allocation ofmachines over time to competing jobs. Job shop scheduling involves set of jobs to be processed on finite set of machines with minimum makespan.Job shop scheduling is a NP-complete problem of combinatorial optimization. Genetic Algorithm (GA) is a class of optimization algorithm problems which provides efficient and optimal solution.Genetic algorithm is well suited for solving production scheduling problems. Unlike heuristic methods, genetic algorithm operates on a population of solutions rather than a single solution. In production scheduling this population of solutions consist of many feasible solutions. Initial population of feasible schedules is generated randomly. This population goes through a set of genetic operators such as crossover and mutation to produce new schedules. At each
generation the fitness of the schedule is evaluated to decide whether it can be carried over to the next generation or should be replaced with a better solution.Other methods which can be applied to solve job shop problem converge to the local optima quickly. With genetic algorithm, convergence to local optima is reduced. The result obtained is compared with parameters such as number of generations and crossover rate. It is found that as the number of generations increases better results are achieved.
Keywords
Full Text:
PDFReferences
Mahanim Omar, Adam Baharum, Yahiya Abu Hasan, “A Job Shop Scheduling Problem (JSSP) using genetic algorithm”, 2nd IMT-GT Regional Conference on Mathematics Malaysia 2006.
Nihar Shah and Dr. David Koonce, “Using Distributed Genetic Algorithms for Solving Job Shop Scheduling Problems”, Industrial And Manufacturing System Engineering Ohio university, Athens OH45701.
Takeshi Yamada and Ryohei,”A Genetic Algorithm with Multi-Step Crossover for Job-Shop Scheduling Problems”, NAKANO NTT Communication Science Laboratories 2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02 JAPAN.
Banzhaf W. “Genetic Programming –An Introduction.”, San Francisco: Morgan Kaufmann publishers, 1998.
Bartschi Wall M. A “Genetic Algorithm for Resource-Constrained Scheduling.” PhD thesis. Massachusetts Institute of Technology; 1996.
Grudenic I, Bogunovic N. “Analysis of Scheduling Algorithms for Computer Clusters”, In: Proc. 31th Int'l Convention MIPRO 2008; Opatija, Croatia.
Kolisch R, Hartmann S. “Heuristic algorithms for solving the resource constrained project scheduling problem: Classification and computational analysis”, pp 147–178. Kluwer Academic Publishers; 1999.
Kolisch R, Spracher, “A. PSPLIB — A project scheduling problem library”, European Journal of Operational Research 1997; 96(1):205–216
Koza J. “Genetic Programming”, Cambridge: MIT Press; 1992.
Mendes J, Gonçalves J, Resende M. “A Random Key Based Genetic Algorithm for the Resource Constrained Project Scheduling Problem”, AT&T Labs Research Technical Report TD-6DUK2C; 2003.
Hongze Qiu Wanli Zhou Hailong Wang , ” A Genetic Algorithm-based Approach to Flexible Job-shop Scheduling Problem”, Fifth International Conference on Natural Computation,2009.
Rajiv Kumar, “A comparative analysis of Genetic Algorithm with variable Crossover and Inversion probability for process scheduling problem”, Journal of Global Research in Computer Science December 2010.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.