Parallel-machine scheduling with simple linear deterioration to minimize total completion time

Research output: Journal article publicationJournal articleAcademic researchpeer-review

70 Citations (Scopus)


We consider the parallel-machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the total completion time. We give a fully polynomial-time approximation scheme (FPTAS) for the case with m identical machines, where m is fixed. This study solves an open problem that has been posed in the literature for ten years.
Original languageEnglish
Pages (from-to)342-347
Number of pages6
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - 16 Jul 2008


  • Deteriorating jobs
  • Parallel-machine scheduling

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this