Iterated reference greedy algorithm for solving distributed no-idle permutation flowshop scheduling problems

被引：78

作者：

Yine, Kuo-Ching ^{[1
]}

Lin, Shih-Wei ^{[2
,3
]}

Cheng, Chen-Yang ^{[1
]}

He, Cheng-Ding ^{[1
]}

机构：

[1] Natl Taipei Univ Technol, Dept Ind Engn & Management, Taipei, Taiwan

[2] Chang Gung Univ, Dept Informat Management, Taoyuan, Taiwan

[3] Linkou Chang Gung Mem Hosp, Dept Neurol, Taoyuan, Taiwan

来源：

COMPUTERS & INDUSTRIAL ENGINEERING | 2017年 / 110卷

关键词：

Scheduling; Distributed permutation flowshop; No-idle; Iterated reference greedy algorithm; TABU SEARCH ALGORITHM; MINIMIZING MAKESPAN; DIFFERENTIAL EVOLUTION; HEURISTICS; CLASSIFICATION; SHOPS; TIMES;

D O I：

10.1016/j.cie.2017.06.025

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper investigates the Distributed No-idle Permutation Flowshop Scheduling Problem (DNIPFSP) with the objective of minimizing the makespan, which has not been discussed in any previous study. This study presents an Iterated Reference Greedy (IRG) algorithm for effectively solving this problem. The performance of the proposed IRG algorithm is compared with a state-of-the-art iterated greedy (IG) algorithm, as well as the Mixed Integer Linear Programming (MILP) model on two well-known benchmark problem sets. Computational results show that the proposed IRG algorithm outperforms the IG algorithm. Given the NP-Complete nature of the DNIPFSP problem, this paper is the first study to contribute a feasible approach for solving it effectively. (C) 2017 Elsevier Ltd. All rights reserved.

引用

页码：413 / 423

页数：11

共 40 条

[1] FLOWSHOP NO-IDLE OR NO-WAIT SCHEDULING TO MINIMIZE THE SUM OF COMPLETION TIMES
ADIRI, I
POHORYLES, D
[J]. NAVAL RESEARCH LOGISTICS, 1982, 29 (03) : 495 - 504
[2] [Anonymous], 1997, INTEGRATED PRODUCT P
[3] A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion
Deng, Guanlong
Gu, Xingsheng
[J]. COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (09) : 2152 - 2160
[4] A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem
Fernandez-Viagas, Victor
Framinan, Jose M.
[J]. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2015, 53 (04) : 1111 - 1123
[5] A review and classification of heuristics for permutation flow-shop scheduling with makespan objective
Framinan, JM
Gupta, JND
Leisten, R
[J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2004, 55 (12) : 1243 - 1255
[6] An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem
Gao, Jian
Chen, Rong
Deng, Wu
[J]. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2013, 51 (03) : 641 - 651
[7] Gao J, 2011, INT J COMPUT INT SYS, V4, P497
[8] Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
[9] A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion
Grabowski, J
Wodecki, M
[J]. COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (11) : 1891 - 1909
[10] Graham R. L., 1979, Discrete Optimisation, P287

← 1 2 3 4 →