Machine scheduling with a maintenance interval and job delivery coordination

被引：5

作者：

Hu, Jueliang ^{[1
]}

Luo, Taibo ^{[2
,3
]}

Su, Xiaotong ^{[1
]}

Dong, Jianming ^{[1
]}

Tong, Weitian ^{[3
]}

Goebel, Randy ^{[3
]}

Xu, Yinfeng ^{[2
,4
]}

Lin, Guohui ^{[1
,3
]}

机构：

[1] Zhejiang Sci Tech Univ, Dept Math, Hangzhou 310018, Zhejiang, Peoples R China

[2] Sichuan Univ, Sch Business, Chengdu 610065, Sichuan, Peoples R China

[3] Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada

[4] State Key Lab Mfg Syst Engn, Xian 710049, Shaanxi, Peoples R China

来源：

OPTIMIZATION LETTERS | 2016年 / 10卷 / 08期

基金：

加拿大自然科学与工程研究理事会; 中国国家自然科学基金;

关键词：

Scheduling; Machine maintenance; Job delivery; Bin-packing; Approximation algorithm; Worst-case performance analysis;

D O I：

10.1007/s11590-015-0939-7

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We investigate a scheduling problem with job delivery coordination in which the machine has a maintenance time interval. The goal is to minimize the makespan. In the problem, each job needs to be processed on the machine non-preemptively for a certain time, and then transported to a distribution center, by one vehicle with a limited physical capacity. We present a 2-approximation algorithm for the problem, and show that the performance ratio is tight.

引用

页码：1645 / 1656

页数：12

共 11 条

[1] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[2] Machine scheduling with job delivery coordination
Chang, YC
Lee, CY
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 158 (02) : 470 - 487
[3] Improved algorithms for two single machine scheduling problems
He, Yong
Zhong, Weiya
Gu, Huikun
[J]. THEORETICAL COMPUTER SCIENCE, 2006, 363 (03) : 257 - 265
[4] Johnson D. S., 1985, Journal of Complexity, V1, P65, DOI 10.1016/0885-064X(85)90022-6
[5] Johnson David S, 1973, THESIS
[6] Current trends in deterministic scheduling
Lee, CY
Lei, L
Pinedo, M
[J]. ANNALS OF OPERATIONS RESEARCH, 1997, 70 (0) : 1 - 41
[7] Lee CY, 2001, J SCHED, V4, P3, DOI 10.1002/1099-1425(200101/02)4:1<3::AID-JOS57>3.0.CO
[8] 2-D
[9] Single machine scheduling with job delivery to minimize makespan
Lu, Lingfa
Yuan, Jinjiang
[J]. ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2008, 25 (01) : 1 - 10
[10] Machine scheduling with an availability constraint and job delivery coordination
Wang, Xiuli
Cheng, T. C. Edwin
[J]. NAVAL RESEARCH LOGISTICS, 2007, 54 (01) : 11 - 20

← 1 2 →