A Parallel Genetic Algorithm for the Job Shop Scheduling Problem

被引：0

作者：

Nguyen Huu Mui ^{[1
]}

Vu Dinh Hoa ^{[1
]}

Luc Tri Tuyen ^{[2
]}

机构：

[1] Hanoi Univ Educ, Dept Informat Technol, Hanoi 010000, Vietnam

[2] Vietnam Acad Sci & Technol, Inst Informat Technol, Hanoi 010000, Vietnam

来源：

2012 IEEE INTERNATIONAL SYMPOSIUM ON SIGNAL PROCESSING AND INFORMATION TECHNOLOGY (ISSPIT) | 2012年

关键词：

job shop scheduling; parallel genetic algorithm;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents a parallel genetic algorithm for the job shop scheduling problem (JSP). There are following innovations in this new algorithm: active schedules are created by the priority rules of Giffler and Thompson [1]; the mutation uses neighborhood searching techniques; the crossover uses GT algorithm and is performed on 3 parents. We illustrate this new method on the parameters of Muth and Thompson's benchmark problems. it can produce optimal solutions at a high percentage of accuracy. Our proposed method is preeminent in comparison with other methods on both the calculation time and the speed of finding optimal solutions.

引用

页码：19 / 24

页数：6

共 10 条

[1] A NON-NUMERICAL APPROACH TO PRODUCTION SCHEDULING PROBLEMS
AKERS, SB
FRIEDMAN, J
[J]. JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF AMERICA, 1955, 3 (04): : 429 - 442
[2] ALGORITHMS FOR SOLVING PRODUCTION-SCHEDULING PROBLEMS
GIFFLER, B
THOMPSON, GL
[J]. OPERATIONS RESEARCH, 1960, 8 (04) : 487 - 503
[3] Hybrid Rollout Approaches for the Job Shop Scheduling Problem
Guerriero, F.
[J]. JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2008, 139 (02) : 419 - 438
[4] Holland J.H., 1992, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence
[5] kano R.a., 1991, Proceedings of the 4th International Conference on Genetic Algorithms, P474
[6] Muth J., 1963, Industrial Scheduling
[7] Peng LH, 2006, MATEMATIKA, V22, P91
[8] NP-HARDNESS OF SHOP-SCHEDULING PROBLEMS WITH 3 JOBS
SOTSKOV, YN
SHAKHLEVICH, NV
[J]. DISCRETE APPLIED MATHEMATICS, 1995, 59 (03) : 237 - 266
[9] Yamada T., 2003, STUDIES METAHEURISTI
[10] A hybrid approach to large-scale job shop scheduling
Zhang, Rui
Wu, Cheng
[J]. APPLIED INTELLIGENCE, 2010, 32 (01) : 47 - 59

← 1 →