Flexible open shop scheduling problem to minimize makespan

被引：45

作者：

Bai, Danyu ^{[1
,2
]}

Zhang, Zhi-Hai ^{[2
]}

Zhang, Qiang ^{[3
]}

机构：

[1] Shenyang Univ Chem Technol, Sch Econ & Management, Shenyang 110142, Peoples R China

[2] Tsinghua Univ, Dept Ind Engn, Beijing 100084, Peoples R China

[3] Northeastern Univ, Software Coll, Shenyang 110819, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 2016年 / 67卷

基金：

中国国家自然科学基金;

关键词：

Scheduling; Flexible open shop; Makespan; Asymptotic analysis; Differential evolution algorithm; DIFFERENTIAL EVOLUTION ALGORITHM; MULTIPROCESSOR OPEN SHOP; PARALLEL MACHINES; SETUP TIMES;

D O I：

10.1016/j.cor.2015.10.012

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This study investigates the static and dynamic versions of the flexible open shop scheduling problem with the goal of minimizing makespan. The asymptotic optimality of the general dense scheduling (GDS) algorithm is proven by the boundedness hypothesis. For large-scale problems, the GDS-based heuristic algorithms are presented to accelerate convergence. For moderate-scale problems, the differential evolution algorithm is employed to obtain high-quality solutions. A series of random experiments are conducted to demonstrate the effectiveness of the proposed algorithms. (C) 2015 Elsevier Ltd. All rights reserved.

引用

页码：207 / 215

页数：9

共 33 条

[1] A tabu search approach for proportionate multiprocessor open shop scheduling [J].

Abdelmaguid, Tamer F. ;

Shalaby, Mohamed A. ;

Awwad, Mohamed A. .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2014, 58 (01) :187-203

[2] A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times [J].

Al-Anzi, Fawaz S. ;

Allahverdi, Ali .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 182 (01) :80-94

[3] Open shop scheduling problem to minimize makespan with release dates [J].

Bai, Danyu ;

Tang, Lixin .

APPLIED MATHEMATICAL MODELLING, 2013, 37 (04) :2008-2015

[4]

Barany I., 1982, Szigma, V15, P177

[5] WORST-CASE ANALYSIS OF HEURISTICS FOR OPEN SHOPS WITH PARALLEL MACHINES [J].

CHEN, B ;

STRUSEVICH, VA .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 70 (03) :379-390

[6] Dense open-shop schedules with release times [J].

Chen, Rongjun ;

Huang, Wanzhen ;

Tang, Guochun .

THEORETICAL COMPUTER SCIENCE, 2008, 407 (1-3) :389-399

[7] Preemptive open shop scheduling with multiprocessors: polynomial cases and applications [J].

de Werra, Dominique ;

Kis, Tamas ;

Kubiak, Wieslaw .

JOURNAL OF SCHEDULING, 2008, 11 (01) :75-83

[8] A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion [J].

Deng, Guanlong ;

Gu, Xingsheng .

COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (09) :2152-2160

[9]

Garey M. R., 1977, SIAM Journal on Computing, V6, P416, DOI 10.1137/0206029

[10]

GONZALEZ T, 1976, J ACM, V23, P665, DOI 10.1145/321978.321985

← 1 2 3 4 →