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 [J].

Chang, YC ;

Lee, CY .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 158 (02) :470-487

[3] Improved algorithms for two single machine scheduling problems [J].

He, Yong ;

Zhong, Weiya ;

Gu, Huikun .

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 [J].

Lee, CY ;

Lei, L ;

Pinedo, M .

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 [J].

Lu, Lingfa ;

Yuan, Jinjiang .

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2008, 25 (01) :1-10

[10] Machine scheduling with an availability constraint and job delivery coordination [J].

Wang, Xiuli ;

Cheng, T. C. Edwin .

NAVAL RESEARCH LOGISTICS, 2007, 54 (01) :11-20

← 1 2 →