An elitist quantum-inspired evolutionary algorithm for the flexible job-shop scheduling problem

被引:88
作者
Wu, Xiuli [1 ]
Wu, Shaomin [2 ]
机构
[1] Univ Sci & Technol Beijing, Sch Mech Engn, Beijing 100083, Peoples R China
[2] Univ Kent, Kent Business Sch, Canterbury CT2 7PE, Kent, England
基金
中国国家自然科学基金;
关键词
Flexible job shop scheduling problem; Quantum-inspired evolutionary algorithm; Convergence speed; Local search; GENETIC ALGORITHM; OPTIMIZATION; MODEL;
D O I
10.1007/s10845-015-1060-6
中图分类号
TP18 [人工智能理论];
学科分类号
140502 [人工智能];
摘要
The flexible job shop scheduling problem (FJSP) is vital to manufacturers especially in today's constantly changing environment. It is a strongly NP-hard problem and therefore metaheuristics or heuristics are usually pursued to solve it. Most of the existing metaheuristics and heuristics, however, have low efficiency in convergence speed. To overcome this drawback, this paper develops an elitist quantum-inspired evolutionary algorithm. The algorithm aims to minimise the maximum completion time (makespan). It performs a global search with the quantum-inspired evolutionary algorithm and a local search with a method that is inspired by the motion mechanism of the electrons around atomic nucleuses. Three novel algorithms are proposed and their effect on the whole search is discussed. The elitist strategy is adopted to prevent the optimal solution from being destroyed during the evolutionary process. The results show that the proposed algorithm outperforms the best-known algorithms for FJSPs on most of the FJSP benchmarks.
引用
收藏
页码:1441 / 1457
页数:17
相关论文
共 37 条
[1]
[Anonymous], 2013, AUTOMATED SCHEDULING
[2]
[Anonymous], PARALLEL PROBLEM SOL
[3]
[Anonymous], 1996, TECHNICAL REPORT SER
[4]
Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems [J].
Baykasoglu, A ;
Özbakir, L ;
Sönmez, AI .
JOURNAL OF INTELLIGENT MANUFACTURING, 2004, 15 (06) :777-785
[5]
Discrepancy search for the flexible job shop scheduling problem [J].
Ben Hmida, Abir ;
Haouari, Mohamed ;
Huguet, Marie-Jose ;
Lopez, Pierre .
COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (12) :2192-2201
[6]
Brandimarte P., 1993, Annals of Operations Research, V41, P157, DOI 10.1007/BF02023073
[7]
JOB-SHOP SCHEDULING WITH MULTIPURPOSE MACHINES [J].
BRUCKER, P ;
SCHLIE, R .
COMPUTING, 1990, 45 (04) :369-375
[8]
Chen HX, 1999, ICRA '99: IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOLS 1-4, PROCEEDINGS, P1120, DOI 10.1109/ROBOT.1999.772512
[9]
Flexible job shop scheduling with parallel machines using Genetic Algorithm and Grouping Genetic Algorithm [J].
Chen, James C. ;
Wu, Cheng-Chun ;
Chen, Chia-Wen ;
Chen, Kou-Huang .
EXPERT SYSTEMS WITH APPLICATIONS, 2012, 39 (11) :10016-10021
[10]
A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling [J].
Chiang, Tsung-Che ;
Lin, Hsiao-Jou .
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2013, 141 (01) :87-98