Scheduling to minimize makespan with time-dependent processing times

L. Y. Kong; Edwin Tai Chiu Cheng; Chi To Ng; M. Zhao

Scheduling to minimize makespan with time-dependent processing times

L. Y. Kong, Edwin Tai Chiu Cheng, Chi To Ng, M. Zhao

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

2 Citations (Scopus)

Abstract

In this paper we study the scheduling problem of minimizing makespan on identical parallel machines with time-dependent processing times. We first consider the problem with time-dependent processing times on two identical machines to minimize makespan, which is NP-hard. We give a fully polynomial-time approximation scheme for the problem. Furthermore, we generalize the result to the case with m machines.

Original language	English
Title of host publication	Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
Pages	925-933
Number of pages	9
Publication status	Published - 1 Dec 2005
Event	16th International Symposium on Algorithms and Computation, ISAAC 2005 - Hainan, China Duration: 19 Dec 2005 → 21 Dec 2005

Publication series

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

Conference

Conference	16th International Symposium on Algorithms and Computation, ISAAC 2005
Country/Territory	China
City	Hainan
Period	19/12/05 → 21/12/05

Keywords

Fully polynomial approximation scheme
Makespan
Parallel machines scheduling

ASJC Scopus subject areas

General Computer Science
General Biochemistry,Genetics and Molecular Biology
Theoretical Computer Science

Cite this

Kong, L. Y., Cheng, E. T. C., Ng, C. T., & Zhao, M. (2005). Scheduling to minimize makespan with time-dependent processing times. In Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings (pp. 925-933). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS).

@inproceedings{4fa73db26d6d4bf88655a64265c66552,

title = "Scheduling to minimize makespan with time-dependent processing times",

abstract = "In this paper we study the scheduling problem of minimizing makespan on identical parallel machines with time-dependent processing times. We first consider the problem with time-dependent processing times on two identical machines to minimize makespan, which is NP-hard. We give a fully polynomial-time approximation scheme for the problem. Furthermore, we generalize the result to the case with m machines.",

keywords = "Fully polynomial approximation scheme, Makespan, Parallel machines scheduling",

author = "Kong, {L. Y.} and Cheng, {Edwin Tai Chiu} and Ng, {Chi To} and M. Zhao",

year = "2005",

month = dec,

day = "1",

language = "English",

isbn = "3540309357",

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

pages = "925--933",

booktitle = "Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings",

note = "16th International Symposium on Algorithms and Computation, ISAAC 2005 ; Conference date: 19-12-2005 Through 21-12-2005",

}

Kong, LY, Cheng, ETC , Ng, CT & Zhao, M 2005, Scheduling to minimize makespan with time-dependent processing times. in Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3827 LNCS, pp. 925-933, 16th International Symposium on Algorithms and Computation, ISAAC 2005, Hainan, China, 19/12/05.

Scheduling to minimize makespan with time-dependent processing times. / Kong, L. Y.; Cheng, Edwin Tai Chiu ; Ng, Chi To et al.
Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. 2005. p. 925-933 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Scheduling to minimize makespan with time-dependent processing times

AU - Kong, L. Y.

AU - Cheng, Edwin Tai Chiu

AU - Ng, Chi To

AU - Zhao, M.

PY - 2005/12/1

Y1 - 2005/12/1

N2 - In this paper we study the scheduling problem of minimizing makespan on identical parallel machines with time-dependent processing times. We first consider the problem with time-dependent processing times on two identical machines to minimize makespan, which is NP-hard. We give a fully polynomial-time approximation scheme for the problem. Furthermore, we generalize the result to the case with m machines.

AB - In this paper we study the scheduling problem of minimizing makespan on identical parallel machines with time-dependent processing times. We first consider the problem with time-dependent processing times on two identical machines to minimize makespan, which is NP-hard. We give a fully polynomial-time approximation scheme for the problem. Furthermore, we generalize the result to the case with m machines.

KW - Fully polynomial approximation scheme

KW - Makespan

KW - Parallel machines scheduling

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

M3 - Conference article published in proceeding or book

SN - 3540309357

SN - 9783540309352

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

SP - 925

EP - 933

BT - Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings

T2 - 16th International Symposium on Algorithms and Computation, ISAAC 2005

Y2 - 19 December 2005 through 21 December 2005

ER -

Scheduling to minimize makespan with time-dependent processing times

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this