Transportation and Batching Scheduling for Minimizing Total Weighted Completion Time

被引：3

作者：

Wei, Hongjun ^{[1
]}

Yuan, Jinjiang ^{[1
]}

Gao, Yuan ^{[1
]}

机构：

[1] Zhengzhou Univ, Sch Math & Stat, Zhengzhou 450001, Henan, Peoples R China

来源：

MATHEMATICS | 2019年 / 7卷 / 09期

基金：

中国博士后科学基金; 中国国家自然科学基金;

关键词：

Transportation; batching scheduling; total weighted completion time; unary NP-hard; approximation algorithm; 2-MACHINE FLOWSHOP; COORDINATION; MACHINE;

D O I：

10.3390/math7090819

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider the coordination of transportation and batching scheduling with one single vehicle for minimizing total weighted completion time. The computational complexity of the problem with batch capacity of at least 2 was posed as open in the literature. For this problem, we show the unary NP-hardness for every batch capacity at least 3 and present a polynomial-time 3-approximation algorithm when the batch capacity is at least 2.

引用

页数：10

共 11 条

[1] The third comprehensive survey on scheduling problems with setup times/costs [J].

Allahverdi, Ali .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 246 (02) :345-378

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[3] Integrated Production and Outbound Distribution Scheduling: Review and Extensions [J].

Chen, Zhi-Long .

OPERATIONS RESEARCH, 2010, 58 (01) :130-148

[4] Minimizing the total weighted completion time in a two-machine proportionate flow shop with different machine speeds [J].

Choi, BC ;

Yoon, SH ;

Chung, SJ .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2006, 44 (04) :715-728

[5] Speeding up a Rollout algorithm for complex parallel machine scheduling [J].

Ciavotta, Michele ;

Meloni, Carlo ;

Pranzo, Marco .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2016, 54 (16) :4993-5009

[6] The coordination of scheduling and batch deliveries [J].

Hall, NG ;

Potts, CN .

ANNALS OF OPERATIONS RESEARCH, 2005, 135 (01) :41-64

[7] Minimizing total completion time in a two-machine flowshop: Analysis of special cases [J].

Hoogeveen, JA ;

Kawaguchi, T .

MATHEMATICS OF OPERATIONS RESEARCH, 1999, 24 (04) :887-910

[8]

Smith W., 1956, NAV RES LOGIST Q, V3, P59, DOI DOI 10.1002/NAV.3800030106

[9] The coordination of transportation and batching scheduling [J].

Tang, Lixin ;

Gong, Hua .

APPLIED MATHEMATICAL MODELLING, 2009, 33 (10) :3854-3862

[10] Two-machine flow-shop scheduling with equal processing time on the second machine for minimizing total weighted completion time [J].

Wei, Hongjun ;

Yuan, Jinjiang .

OPERATIONS RESEARCH LETTERS, 2019, 47 (01) :41-46

← 1 2 →