Semi-active Schedule based Genetic Algorithm for Job Shop Scheduling

KIM JUNWOO; Sung Ho Ha

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.

Citation status

KCI Citation Counts (0)
REFERENCES (23)
열림/닫힘 버튼
* 2021년 이후 발행 논문의 참고문헌은 현재 구축 중입니다.

[journal] 이승정 / 2011 / Platform development of adaptive production planning to improve efficiency in manufacturing system / 한국산업정보학회논문지 / 한국산업정보학회 16(2) : 73~83

[journal] 배상윤 / 2006 / The Information of Dispatching Rules for Improving Job Shop Performance / 산업경영시스템학회지 / 한국산업경영시스템학회 29(4) : 107~112

[journal] Cheng, R. / 1996 / A Tutorial Survey of Job-shop Scheduling Problems using Genetic Algorithms - I. Representation / Computers and Industrial Engineering 30(4) : 983~997

[confproc] Qing-dao-er-ji / 2010 / An Improved Genetic Algorithm for Job Shop Scheduling Problem / Proceedings of the 2010 International Conference on Computational Intelligence and Security

[confproc] 정종백 / 2000 / A Development of Hybrid Genetic Algorithms for Classical Job Shop Scheduling / 대한산업공학회/한국경영과학회 2000 춘 계공동학술대회 논문집

[journal] 박병주 / 2001 / A Hybrid Genetic Algorithm for Job Shop Scheduling / 한국경영과학회지 26(2)

[book] 김여근 / 1997 / Meta Heuristic / 영지문화사

[journal] Holland, J. H. / 1992 / Genetic Algorithm / Scientific American 266 : 44~50

[journal] Li, Y. / 2010 / A Genetic Algorithm for Job-Shop Scheduling / Journal of Software 5(3)

[journal] 박병주 / 2003 / A Genetic Algorithm-based Scheduling Method for Job Shop Scheduling Problem / 경영과학 / 한국경영과학회 20(1) : 51~64

[journal] Yamada, T. / 1992 / A Genetic Algorithm Applicable to Large-scale Job-Shop Problems / Parallel Problem Solving from Nature 2 : 281~290

[journal] Giffler, B. / 1960 / Algorithms for Solving Production-Scheduling Problems / Operations Research 8(4) : 487~503

[journal] Lee, H.P. / 2006 / A Modified Giffler and Thompson Genetic Algorithm on the Job Shop Scheduling Problem / MATEMATIKA 22(2) : 91~107

[journal] Poon, P.W. / 1995 / Genetic Algorithm Crossover Operators for Ordering Applications / Computers and Operations Research 22(1) : 135~147

[journal] Cheng, R. / 1999 / A Tutorial Survey of Job-shop Scheduling Problems using Genetic Algorithms, Part II: Hybrid Genetic Search Strategies / Computers and Industrial Engineering 36(2) : 343~364

[journal] Abdelmaguid, T.F. / 2010 / Representations in Genetic Algorithm for the Job Shop Scheduling Problem: A Computational Study / Journal of Software Engineering and Applications 3(12) : 155~1162

[journal] Lestan, Z. / 2009 / Solving the Job-shop Scheduling Problem with a Simple Genetic Algorithm / International Journal of Simulation Modelling 8(4) : 197~205

[confproc] Chen, Y. / 2010 / The Improved Genetic Algorithm for the Complex Job-shop Scheduling / Proceedings of the 2010 IEEE 17th International Conference on Industrial Engineering and Engineering Management : 609~614

[journal] Zhang, G. / 2011 / An Effective Genetic Algorithm for the Flexible Job-shop Scheduling Problem / Expert Systems with Applications 38(4) : 3563~3573

[confproc] Nakano, R. / 1991 / Conventional Genetic Algorithms for Job Shop Problems / Proceedings of the 4th International Conference on Genetic Algorithms : 474~479

[journal] Bierwirth, C. / 1995 / A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms / OR-Spektrum 17(213) : 87~92

[confproc] 이건명 / 1998 / A Genetic Algorithm for General Machine Scheduling Problems / KES : 60~66

[journal] 이혜리 / 2004 / A comparative study of precedence-preserving genetic operators in sequential ordering problems and job shop scheduling problem / 한국지능시스템학회 논문지 / 한국지능시스템학회 14(5) : 563~570

KJC Korea
Journal Central

Statistics

Tools

Sharing

Issue List

Citation status