Study on proportionate flowshop scheduling with due-date assignment and position-dependent weights

被引：22

作者：

Lv, Dan-Yang ^{[1
]}

Wang, Ji-Bo ^{[1
]}

机构：

[1] Shenyang Aerosp Univ, Sch Sci, Shenyang, Peoples R China

来源：

OPTIMIZATION LETTERS | 2021年 / 15卷 / 06期

关键词：

Scheduling; Proportionate flowshop; Due-date assignment; Optimal solution algorithm; Algorithm complexity;

D O I：

10.1007/s11590-020-01670-4

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In a recent paper, Jiang et al. (EngOptim 52(1):37-52, 2020) considered proportionate flowshop scheduling with position-dependent weights. For common and slack due-date assignment problems, they proved that both of these two problems can be solved in O(n(2) log n) time, where n is the number of jobs. The contribution of this paper is that we show that these two problems can be optimally solved by a lower-order algorithm, i.e., in O(n log n) time.

引用

页码：2311 / 2319

页数：9

共 17 条

[1]

Brucker P., 1995, Scheduling Algorithms, P225, DOI [DOI 10.1007/978-3-662-04550-3_7, 10.1007/978-3-662-04550-3, DOI 10.1007/978-3-662-04550-3]

[2] Proportionate flow shop games [J].

Estevez-Fernandez, Arantza ;

Mosquera, Manuel A. ;

Borm, Peter ;

Hamers, Herbert .

JOURNAL OF SCHEDULING, 2008, 11 (06) :433-447

[3] Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect [J].

Geng, Xin-Na ;

Wang, Ji-Bo ;

Bai, Danyu .

ENGINEERING OPTIMIZATION, 2019, 51 (08) :1301-1323

[4]

Graham R. L., 1979, Discrete Optimisation, P287

[5]

Hardy G.H., 1967, INEQUALITIES, V2nd ed

[6] Proportionate flowshop scheduling with position-dependent weights [J].

Jiang, Chong ;

Zou, Dexin ;

Bai, Danyu ;

Wang, Ji-Bo .

ENGINEERING OPTIMIZATION, 2020, 52 (01) :37-52

[7] Single machine scheduling with slack due dates assignment [J].

Liu, Weiguo ;

Hu, Xiangpei ;

Wang, Xuyin .

ENGINEERING OPTIMIZATION, 2017, 49 (04) :709-717

[8] Due-date assignment scheduling involving job-dependent learning effects and convex resource allocation [J].

Liu, Weiwei ;

Jiang, Chong .

ENGINEERING OPTIMIZATION, 2020, 52 (01) :74-89

[9] Optimal due-date assignment problem with learning effect and resource-dependent processing times [J].

Lu, Yuan-Yuan ;

Li, Gang ;

Wu, Yu-Bin ;

Ji, Ping .

OPTIMIZATION LETTERS, 2014, 8 (01) :113-127

[10] On Equivalence Between the Proportionate Flow Shop and Single-Machine Scheduling Problems [J].

Panwalkar, S. S. ;

Koulamas, Christos .

NAVAL RESEARCH LOGISTICS, 2015, 62 (07) :595-603

← 1 2 →