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 proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)


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 languageEnglish
Title of host publicationAlgorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
Number of pages9
Publication statusPublished - 1 Dec 2005
Event16th International Symposium on Algorithms and Computation, ISAAC 2005 - Hainan, China
Duration: 19 Dec 200521 Dec 2005

Publication series

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


Conference16th International Symposium on Algorithms and Computation, ISAAC 2005


  • Fully polynomial approximation scheme
  • Makespan
  • Parallel machines scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Theoretical Computer Science

Cite this