본문 바로가기
  • Home
Basic Search

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 Studies > Interdisciplinary Research
  • Published : October 31, 2012

KIM JUNWOO 1,  Sung Ho Ha 2

1동아대학교
2경북대학교

Accredited

ABSTRACT

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.

Statistics

  • 413 Viewed
  • 133 Downloaded

Tools

Issue List

Citation status

* References for papers published after 2023 are currently being built.

Basic Search Advanced Search