Machine scheduling with a maintenance interval and job delivery coordination

Jueliang Hu; Taibo Luo; Xiaotong Su; Jianming Dong; Weitian Tong; Randy Goebel; Yinfeng Xu; Guohui Lin

doi:10.1007/s11590-015-0939-7

Machine scheduling with a maintenance interval and job delivery coordination

Jueliang Hu, Taibo Luo, Xiaotong Su, Jianming Dong, Weitian Tong, Randy Goebel, Yinfeng Xu, Guohui Lin

Computer Science

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	1645-1656
Number of pages	12
Journal	Optimization Letters
Volume	10
Issue number	8
DOIs	https://doi.org/10.1007/s11590-015-0939-7
State	Published - Dec 1 2016

Keywords

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

Access to Document

10.1007/s11590-015-0939-7

Cite this

@article{b6f37a92072643e6a586eca16e7b1979,

title = "Machine scheduling with a maintenance interval and job delivery coordination",

abstract = "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.",

keywords = "Approximation algorithm, Bin-packing, Job delivery, Machine maintenance, Scheduling, Worst-case performance analysis",

author = "Jueliang Hu and Taibo Luo and Xiaotong Su and Jianming Dong and Weitian Tong and Randy Goebel and Yinfeng Xu and Guohui Lin",

note = "Publisher Copyright: {\textcopyright} 2015, Springer-Verlag Berlin Heidelberg.",

year = "2016",

month = dec,

day = "1",

doi = "10.1007/s11590-015-0939-7",

language = "English",

volume = "10",

pages = "1645--1656",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "8",

}

TY - JOUR

T1 - Machine scheduling with a maintenance interval and job delivery coordination

AU - Hu, Jueliang

AU - Luo, Taibo

AU - Su, Xiaotong

AU - Dong, Jianming

AU - Tong, Weitian

AU - Goebel, Randy

AU - Xu, Yinfeng

AU - Lin, Guohui

PY - 2016/12/1

Y1 - 2016/12/1

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - Bin-packing

KW - Job delivery

KW - Machine maintenance

KW - Scheduling

KW - Worst-case performance analysis

UR - http://www.scopus.com/inward/record.url?scp=84940706033&partnerID=8YFLogxK

U2 - 10.1007/s11590-015-0939-7

DO - 10.1007/s11590-015-0939-7

M3 - Article

AN - SCOPUS:84940706033

SN - 1862-4472

VL - 10

SP - 1645

EP - 1656

JO - Optimization Letters

JF - Optimization Letters

IS - 8

ER -

Machine scheduling with a maintenance interval and job delivery coordination

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this