Machine scheduling with a maintenance interval and job delivery coordination

被引：0

作者：

Jueliang Hu

Taibo Luo

Xiaotong Su

Jianming Dong

Weitian Tong

Randy Goebel

Yinfeng Xu

Guohui Lin

机构：

[1] Zhejiang Sci-Tech University,Department of Mathematics

[2] Sichuan University,Business School

[3] University of Alberta,Department of Computing Science

[4] State Key Lab for Manufacturing Systems Engineering,undefined

来源：

Optimization Letters | 2016年 / 10卷

关键词：

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

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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

页数：11

共 19 条

[1]

Chang Y-C(2004)Machine scheduling with job delivery coordination Eur. J. Oper. Res. 158 470-487

[2]

Lee C-Y(1985)A J. Complex. 1 65-106

[3]

Garey MR(2006) theorem for bin-packing Theor. Comput. Sci. 363 257-265

[4]

Johnson DS(2001)Improved algorithms for two single machine scheduling problems J. Sched. 4 3-24

[5]

He Y(1997)Machine scheduling with transportation considerations Ann. Oper. Res. 70 1-41

[6]

Zhong W(2008)Current trends in deterministic scheduling Asia-Pac. J. Oper. Res. 25 1-10

[7]

Gu H(2007)Single machine scheduling with job delivery to minimize makespan Naval Res. Logist. 54 11-20

[8]

Lee C-Y(2007)Machine scheduling with an availability constraint and job delivery coordination Eur. J. Oper. Res. 182 1057-1072

[9]

Chen Z-L(undefined)On the machine scheduling problem with job delivery coordination undefined undefined undefined-undefined

[10]

Lee C-Y(undefined)undefined undefined undefined undefined-undefined

← 1 2 →