Approximation algorithms for scheduling with a variable machine maintenance

Wenchang Luo, Lin Chen, Guochuan Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

In this paper, we investigate the problem of scheduling weighted jobs on a single machine with a maintenance whose starting time is prior to a given deadline and whose duration is a nondecreasing function of the starting time. We are asked not only to schedule the jobs but also the maintenance such that the total weighted job completion time is minimum. The problem is shown to be weakly NP-hard. In the case that the duration of the maintenance is a concave (and nondecreasing) function of its starting time, we provide two approximation algorithms with approximation ratio of 2 and at most 1 + √ 2/2 + , respectively.

Original languageEnglish
Title of host publicationAlgorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings
Pages209-219
Number of pages11
DOIs
StatePublished - 2010
Event6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010 - Weihai, China
Duration: Jul 19 2010Jul 21 2010

Publication series

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

Conference

Conference6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010
CountryChina
CityWeihai
Period07/19/1007/21/10

Keywords

  • Approximation algorithms
  • Scheduling with maintenance
  • Total weighted completion time

Fingerprint Dive into the research topics of 'Approximation algorithms for scheduling with a variable machine maintenance'. Together they form a unique fingerprint.

  • Cite this

    Luo, W., Chen, L., & Zhang, G. (2010). Approximation algorithms for scheduling with a variable machine maintenance. In Algorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings (pp. 209-219). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6124 LNCS). https://doi.org/10.1007/978-3-642-14355-7_22