Approximation scheme for scheduling resumable proportionally deteriorating jobs

Wenchang Luo, Lin Chen

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

3 Scopus citations

Abstract

In this paper, we investigate the problem of scheduling resumable proportionally deteriorating jobs on a single machine with a non-availability constraint. The goal is to minimize the total completion time. We show the problem is NP-hard. Furthermore, we present a fully polynomial time approximation scheme (FPTAS).

Original languageEnglish
Title of host publicationFrontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings
Pages36-45
Number of pages10
DOIs
StatePublished - 2011
Event5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011 - Jinhua, China
Duration: May 28 2011May 31 2011

Publication series

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

Conference

Conference5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011
CountryChina
CityJinhua
Period05/28/1105/31/11

Keywords

  • Complexity
  • Non-availability
  • Proportionally deteriorating
  • Resumable
  • Scheduling

Fingerprint Dive into the research topics of 'Approximation scheme for scheduling resumable proportionally deteriorating jobs'. Together they form a unique fingerprint.

  • Cite this

    Luo, W., & Chen, L. (2011). Approximation scheme for scheduling resumable proportionally deteriorating jobs. In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings (pp. 36-45). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6681 LNCS). https://doi.org/10.1007/978-3-642-21204-8_8