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

Research output: Contribution to book or proceedingConference articlepeer-review

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; transportation is by one vehicle with a limited physical capacity, and it takes constant time to deliver a shipment to the distribution center and return back to the machine. We present a 2-approximation algorithm for the problem, and show that the performance ratio is tight.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - 9th International Workshop, FAW 2015, Proceedings
EditorsChee Yap, Jianxin Wang
PublisherSpringer Verlag
Pages104-114
Number of pages11
ISBN (Print)9783319196466
DOIs
StatePublished - 2015
Event9th International Workshop on Frontiers in Algorithmics, FAW 2015 - Guilin, China
Duration: Jul 3 2015Jul 5 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9130
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Workshop on Frontiers in Algorithmics, FAW 2015
Country/TerritoryChina
CityGuilin
Period07/3/1507/5/15

Scopus Subject Areas

  • Theoretical Computer Science
  • General Computer Science

Keywords

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

Fingerprint

Dive into the research topics of 'Machine scheduling with a maintenance interval and job delivery coordination'. Together they form a unique fingerprint.

Cite this