Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling

被引:142
作者
Gao, K. Z. [1 ,2 ]
Suganthan, P. N. [1 ]
Pan, Q. K. [2 ]
Chua, T. J. [3 ]
Cai, T. X. [3 ]
Chong, C. S. [3 ]
机构
[1] Nanyang Technol Univ, Sch Elect & Elect Engn, Singapore 639798, Singapore
[2] Liaocheng Univ, Comp Sch, Liaocheng 252000, Peoples R China
[3] Singapore Inst Mfg Technol, Singapore 638075, Singapore
基金
美国国家科学基金会;
关键词
Flexible job shop scheduling; Harmony search algorithm; Multi-objective optimization; Local search; GENETIC ALGORITHM; OPTIMIZATION ALGORITHM; FLOW-SHOP; SIMULATION;
D O I
10.1016/j.ins.2014.07.039
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This paper proposes a Pareto-based grouping discrete harmony search algorithm (PGDHS) to solve the multi-objective flexible job shop scheduling problem (FJSP). Two objectives, namely the maximum completion time (makespan) and the mean of earliness and tardiness, are considered simultaneously. Firstly, two novel heuristics and several existing heuristics are employed to initialize the harmony memory. Secondly, multiple harmony generation strategies are proposed to improve the performance of harmony search algorithm. The operation sequence in a new harmony is produced based on the encoding method and the characteristics of FJSP. Thirdly, two local search methods based on critical path and due date are embedded to enhance the exploitation capability. Finally, extensive computational experiments are carried out using well-known benchmark instances. Three widely used performance measures, number of non-dominated solutions, diversification metric and quality metric, are employed to test the performance of PGDHS algorithm. Computational results and comparisons show the efficiency and effectiveness of the proposed PGDHS algorithm for solving multi-objective flexible job-shop scheduling problem. (C) 2014 Published by Elsevier Inc.
引用
收藏
页码:76 / 90
页数:15
相关论文
共 49 条
[31]   Tardiness minimization in a flexible job shop: A tabu search approach [J].
Scrich, CR ;
Armentano, VA ;
Laguna, M .
JOURNAL OF INTELLIGENT MANUFACTURING, 2004, 15 (01) :103-115
[32]  
Seyed Habib A, 2012, WORLD ACAD SCI ENG T, V61, P1160
[33]   A tabu search algorithm for solving a multicriteria flexible job shop scheduling problem [J].
Vilcot, Geoffrey ;
Billaut, Jean-Charles .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2011, 49 (23) :6963-6980
[34]   A Pareto-based estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem [J].
Wang, Ling ;
Wang, Shengyao ;
Liu, Min .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2013, 51 (12) :3574-3592
[35]   An enhanced Pareto-based artificial bee colony algorithm for the multi-objective flexible job-shop scheduling [J].
Wang, Ling ;
Zhou, Gang ;
Xu, Ye ;
Liu, Min .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2012, 60 (9-12) :1111-1123
[36]   Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms [J].
Wang, Ling ;
Pan, Quan-Ke ;
Tasgetiren, M. Fatih .
EXPERT SYSTEMS WITH APPLICATIONS, 2010, 37 (12) :7929-7936
[37]   A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem [J].
Wang, Xiaojuan ;
Gao, Liang ;
Zhang, Chaoyong ;
Shao, Xinyu .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2010, 51 (5-8) :757-767
[38]   Multiagent scheduling method with earliness and tardiness objectives in flexible job shops [J].
Wu, ZB ;
Weng, MX .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 2005, 35 (02) :293-301
[39]   An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems [J].
Xia, WJ ;
Wu, ZM .
COMPUTERS & INDUSTRIAL ENGINEERING, 2005, 48 (02) :409-425
[40]   Multi-objective flexible job shop schedule: Design and evaluation by simulation modeling [J].
Xing, Li-Ning ;
Chen, Ying-Wu ;
Yang, Ke-Wei .
APPLIED SOFT COMPUTING, 2009, 9 (01) :362-376