Solving job-shop scheduling problems by genetic algorithm
Authors:
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, 1577-1582
Abstract
Job-shop scheduling problem (JSP) is one of extremely hard problems because it requires very large combinatorial search space and the precedence constraint between machines. The traditional algorithm used to solve the problem is the branch-and-bound method, which takes considerable computing time when the size of problem is large. We propose a new method for solving JSP using genetic algorithm (GA) and demonstrate its efficiency by the standard benchmark of job-shop scheduling problems. Some important points of GA are how to represent the schedules as an individuals and to design the genetic operators for the representation in order to produce better results.Keywords
This publication has 5 references indexed in Scilit:
- Genetic Algorithms + Data Structures = Evolution Programs1992
- An Algorithm for Solving the Job-Shop ProblemManagement Science, 1989
- Scheduling the General Job-ShopManagement Science, 1985
- On Scheduling with Ready Times and Due Dates to Minimize Maximum LatenessOperations Research, 1975
- Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration AlgorithmOperations Research, 1969