Two-agent single-machine scheduling with deteriorating jobs

Yunqiang Yin, Edwin Tai Chiu Cheng, Long Wan, Chin Chia Wu, Jun Liu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

38 Citations (Scopus)


We consider several two-agent single-machine scheduling problems with deteriorating jobs. By deteriorating jobs we mean that the actual processing time of any job of the two agents is an increasing linear function of its starting time. Each agent wants to minimize a certain objective function, which depends on the completion times of its jobs only. The goal is to schedule the jobs such that the performance of the schedule is satisfactory with respect to the objective functions of both agents. We consider six scheduling problems associated with different combinations of the two agents' objective functions, which include the maximum cost, total weighted completion time, discounted total weighted completion time, maximum earliness cost, total earliness, and total weighted earliness. We examine different scenarios depending on the trade-off between the two agents. Under each scenario, we address the computational complexity and solvability issues of various problems that seek to find the optimal solution for one agent, subject to an upper bound on the maximum (earliness) cost of the other agent.
Original languageEnglish
Pages (from-to)177-185
Number of pages9
JournalComputers and Industrial Engineering
Publication statusPublished - 1 Jan 2015


  • Deteriorating jobs
  • Scheduling
  • Single machine
  • Two agents

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)


Dive into the research topics of 'Two-agent single-machine scheduling with deteriorating jobs'. Together they form a unique fingerprint.

Cite this