Home > Explore Content > All Issues > Article View
Semi-active Schedule based Genetic Algorithm for Job Shop Scheduling
Journal of Knowledge Information Technology and Systems
Abbr :
JKITS
2012, 7(5), pp.1-10
Publisher : Korea Knowledge Information Technology Society
Research Area : Interdisciplinary Research
2012, 7(5), pp.1-10
Publisher : Korea Knowledge Information Technology Society
Research Area : Interdisciplinary Research
-
Job Shop scheduling problem is one of the most well-known NP-hard combinatorial optimization problems, and it is hard to obtain the optimal solution via numerical methods. Accordingly, probabilistic search methods such as genetic algorithm, simulated annealing and tabu search have been widely applied for solving Job Shop scheduling problems. In general, geneticalgorithms for Job Shop scheduling are designed to maintain a population consisted of active schedules, because the optimal schedules are included in the active ones. However, methods for generating active schedules such as Giffler and Thompson algorithm can be inefficient in that they are often computationally intensive. Instead, this paper proposes a semi active schedule based genetic algorithm called sa-GA. In sa-GA, a solution is represented as a natural permutation of operations, which is easily transformed into a semi active schedule. In addition, the genetic operations can be performed more quickly, and these aspects make sa-GA more efficient than the traditional active schedule based genetic algorithms. The experiment results show that sa-GA also concentrates on the active schedules in the population, and the optimal schedules can be obtained quickly.
184 Viewed
Print this page
Download PDF