Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint

Research output: Journal article publicationJournal articleAcademic researchpeer-review

65 Citations (Scopus)


This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series-parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.
Original languageEnglish
Pages (from-to)2684-2693
Number of pages10
JournalComputers and Operations Research
Issue number8
Publication statusPublished - 1 Aug 2008


  • Deteriorating jobs
  • Makespan
  • Scheduling
  • Series-parallel graph
  • Single machine
  • Total weighted completion time

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this