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 [J].

AKERS, SB ;

FRIEDMAN, J .

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF AMERICA, 1955, 3 (04) :429-442

[2] ALGORITHMS FOR SOLVING PRODUCTION-SCHEDULING PROBLEMS [J].

GIFFLER, B ;

THOMPSON, GL .

OPERATIONS RESEARCH, 1960, 8 (04) :487-503

[3] Hybrid Rollout Approaches for the Job Shop Scheduling Problem [J].

Guerriero, F. .

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 [J].

SOTSKOV, YN ;

SHAKHLEVICH, NV .

DISCRETE APPLIED MATHEMATICS, 1995, 59 (03) :237-266

[9]

Yamada T., 2003, STUDIES METAHEURISTI

[10] A hybrid approach to large-scale job shop scheduling [J].

Zhang, Rui ;

Wu, Cheng .

APPLIED INTELLIGENCE, 2010, 32 (01) :47-59

← 1 →