Unrelated parallel-machine scheduling with deteriorating maintenance activities

Edwin Tai Chiu Cheng, Chou Jung Hsu, Dar Li Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

53 Citations (Scopus)


We study the problem of unrelated parallel-machine scheduling with deteriorating maintenance activities. Each machine has at most one maintenance activity, which can be performed at any time throughout the planning horizon. The length of the maintenance activity increases linearly with its starting time. The objective is to minimize the total completion time or the total machine load. We show that both versions of the problem can be optimally solved in polynomial time.
Original languageEnglish
Pages (from-to)602-605
Number of pages4
JournalComputers and Industrial Engineering
Issue number4
Publication statusPublished - 1 May 2011


  • Assignment problem
  • Deteriorating maintenance activity
  • Scheduling
  • Total completion time
  • Total machine load

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this