Approximation scheme for scheduling resumable proportionally deteriorating jobs

Wenchang Luo; Lin Chen

doi:10.1007/978-3-642-21204-8_8

Approximation scheme for scheduling resumable proportionally deteriorating jobs

Wenchang Luo, Lin Chen

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 language	English
Title of host publication	Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings
Pages	36-45
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-21204-8_8
State	Published - 2011
Event	5th 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 2011 → May 31 2011

Publication series

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

Conference

Conference	5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011
Country/Territory	China
City	Jinhua
Period	05/28/11 → 05/31/11

Keywords

Complexity
Non-availability
Proportionally deteriorating
Resumable
Scheduling

Access to Document

10.1007/978-3-642-21204-8_8

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

Luo, Wenchang ; Chen, Lin. / Approximation scheme for scheduling resumable proportionally deteriorating jobs. Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings. 2011. pp. 36-45 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7c85fa75433145c380cd47e2f566a4a1,

title = "Approximation scheme for scheduling resumable proportionally deteriorating jobs",

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).",

keywords = "Complexity, Non-availability, Proportionally deteriorating, Resumable, Scheduling",

author = "Wenchang Luo and Lin Chen",

year = "2011",

doi = "10.1007/978-3-642-21204-8_8",

language = "English",

isbn = "9783642212031",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "36--45",

booktitle = "Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings",

note = "null ; Conference date: 28-05-2011 Through 31-05-2011",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6681 LNCS, pp. 36-45, 5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011, Jinhua, China, 05/28/11. https://doi.org/10.1007/978-3-642-21204-8_8

Approximation scheme for scheduling resumable proportionally deteriorating jobs. / Luo, Wenchang; Chen, Lin.

Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings. 2011. p. 36-45 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6681 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Approximation scheme for scheduling resumable proportionally deteriorating jobs

AU - Luo, Wenchang

AU - Chen, Lin

PY - 2011

Y1 - 2011

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

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

KW - Complexity

KW - Non-availability

KW - Proportionally deteriorating

KW - Resumable

KW - Scheduling

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

U2 - 10.1007/978-3-642-21204-8_8

DO - 10.1007/978-3-642-21204-8_8

M3 - Conference contribution

AN - SCOPUS:79957944750

SN - 9783642212031

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 36

EP - 45

BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings

Y2 - 28 May 2011 through 31 May 2011

ER -

Luo W, Chen L. 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. 2011. p. 36-45. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-21204-8_8

Approximation scheme for scheduling resumable proportionally deteriorating jobs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this