An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion

被引：90

作者：

Dong, Xingye ^{[1
]}

Huang, Houkuan ^{[1
]}

Chen, Ping ^{[1
]}

机构：

[1] Beijing Jiaotong Univ, Sch Comp & Informat Technol, Beijing 100044, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 05期

关键词：

Scheduling; Iterated local search; Metaheuristic; Permutation flowshop; Total flowtime; ANT-COLONY ALGORITHMS; HEURISTIC ALGORITHM; M-MACHINE; N-JOB; C-I; MINIMIZATION; MAKESPAN; TIME;

D O I：

10.1016/j.cor.2008.04.001

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

An ILS algorithm is proposed to solve the permutation flowshop sequencing problem with total flowtime criterion. The effects of different initial permutations and different perturbation strengths are studied. Comparisons are carried out with three constructive heuristics, three ant-colony algorithms and a particle swarm optimization algorithm. Experiments on benchmarks and a set of random instances show that the proposed algorithm is more effective. The presented ILS improves the best known permutations by a significant margin. Crown Copyright (C) 2008 Published by Elsevier Ltd. All rights reserved.

引用

页码：1664 / 1669

页数：6

共 40 条

[21] Combining simulated annealing with local search heuristics [J].

Martin, OC ;

Otto, SW .

ANNALS OF OPERATIONS RESEARCH, 1996, 63 :57-75

[22] ANALYSIS FOR MINIMIZING WEIGHTED MEAN FLOW-TIME IN FLOWSHOP SCHEDULING [J].

MIYAZAKI, S ;

NISHIYAMA, N .

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 1980, 23 (02) :118-132

[23] ADJACENT PAIRWISE APPROACH TO MEAN FLOW-TIME SCHEDULING PROBLEM [J].

MIYAZAKI, S ;

NISHIYAMA, N ;

HASHIMOTO, F .

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 1978, 21 (02) :287-301

[24] A HEURISTIC ALGORITHM FOR THE M-MACHINE, N-JOB FLOWSHOP SEQUENCING PROBLEM [J].

NAWAZ, M ;

ENSCORE, EE ;

HAM, I .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1983, 11 (01) :91-95

[25]

Pinedo M., 2001, SCHEDULING THEORY AL, V2nd

[26] An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs [J].

Rajendran, C ;

Ziegler, H .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 103 (01) :129-138

[27] Two ant-colony algorithms for minimizing total flowtime in permutation flowshops [J].

Rajendran, C ;

Ziegler, H .

COMPUTERS & INDUSTRIAL ENGINEERING, 2005, 48 (04) :789-797

[28] HEURISTIC ALGORITHM FOR SCHEDULING IN A FLOWSHOP TO MINIMIZE TOTAL FLOWTIME [J].

RAJENDRAN, C .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 1993, 29 (01) :65-73

[29] Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs [J].

Rajendran, C ;

Ziegler, H .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 155 (02) :426-438

[30] AN EFFICIENT HEURISTIC APPROACH TO THE SCHEDULING OF JOBS IN A FLOWSHOP [J].

RAJENDRAN, C ;

CHAUDHURI, D .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 61 (03) :318-325

← 1 2 3 4 →