New block properties for flowshop scheduling with blocking and their application in an iterated greedy algorithm

被引：24

作者：

Ding, Jian-Ya ^{[1
]}

Song, Shiji ^{[1
]}

Gupta, Jatinder N. D. ^{[2
]}

Wang, Cheng ^{[1
]}

Zhang, Rui ^{[3
]}

Wu, Cheng ^{[1
]}

机构：

[1] Tsinghua Univ, Dept Automat, Beijing, Peoples R China

[2] Univ Alabama, Coll Business Adm, Huntsville, AL 35899 USA

[3] Nanchang Univ, Sch Econ & Management, Nanchang, Peoples R China

来源：

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH | 2016年 / 54卷 / 16期

基金：

中国国家自然科学基金;

关键词：

scheduling; flowshop with blocking; block properties; pruning procedure; iterated greedy algorithm; TABU SEARCH ALGORITHM; SIMULATED ANNEALING ALGORITHM; PERMUTATION FLOWSHOP; SHOP PROBLEM; LIMITED BUFFERS; RELEASE DATES; IN-PROCESS; MAKESPAN; MINIMIZE; STORAGE;

D O I：

10.1080/00207543.2015.1076941

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

This paper proposes new block properties for the flowshop scheduling problem with blocking to minimise makespan. A pruning procedure based on these proposed properties is used in the construction phase of an iterated greedy algorithm to decrease the total number of solutions to be examined to find an optimal schedule. Computational results using Taillard's benchmark problem instances show that the new block properties help to eliminate more unpromising' solutions than the classic properties. In addition, the effectiveness of the proposed algorithm is verified by comparison with some high-performing algorithms for the considered problem.

引用

页码：4759 / 4772

页数：14

共 41 条

[1] Block approach - tabu search algorithm for single machine total weighted tardiness problern [J].

Bozejko, Wojciech ;

Grabowski, Jozef ;

Wodecki, Mieczyslaw .

COMPUTERS & INDUSTRIAL ENGINEERING, 2006, 50 (1-2) :1-14

[2] Parallel path relinking method for the single machine total weighted tardiness problem with sequence-dependent setups [J].

Bozejko, Wojciech .

JOURNAL OF INTELLIGENT MANUFACTURING, 2010, 21 (06) :777-785

[3] Accelerated methods for total tardiness minimisation in no-wait flowshops [J].

Ding, Jianya ;

Song, Shiji ;

Zhang, Rui ;

Gupta, Jatinder N. D. ;

Wu, Cheng .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2015, 53 (04) :1002-1018

[4]

Gao Shou-wei, 2007, Journal of Shanghai Jiaotong University (English Edition), VE12, P47

[5] Sequencing of jobs in some production system [J].

Grabowski, J ;

Pempera, J .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 125 (03) :535-550

[6] A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion [J].

Grabowski, J ;

Wodecki, M .

COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (11) :1891-1909

[7] New block properties for the permutation flow shop problem with application in tabu search [J].

Grabowski, J ;

Pempera, J .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2001, 52 (02) :210-220

[8] A BLOCK APPROACH FOR SINGLE-MACHINE SCHEDULING WITH RELEASE DATES AND DUE DATES [J].

GRABOWSKI, J ;

NOWICKI, E ;

ZDRZALKA, S .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1986, 26 (02) :278-285

[9] The permutation flow shop problem with blocking. A tabu search approach [J].

Grabowski, Jozef ;

Pempera, Jaroslaw .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2007, 35 (03) :302-311

[10]

Gupta J.N. D., 1979, Disaggregation, DOI [DOI 10.1007/978-94-015-7636-9_23, 10.1007/978-94-015-7636-9_23]

← 1 2 3 4 5 →