Two-agent scheduling of time-dependent jobs

Cheng He, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


We consider the problem of scheduling deteriorating jobs or shortening jobs with two agents A and B. We are interested in generating all Pareto-optimal schedules for the two criteria: (1) the total completion time of the jobs in A and the maximum cost of the jobs in B, and (2) the maximum cost of the jobs in A and the maximum cost of the jobs in B. We show that all Pareto-optimal schedules for both problems can be generated in polynomial time, whether the jobs are deteriorating or shortening.

Original languageEnglish (US)
Pages (from-to)362-377
Number of pages16
JournalJournal of Combinatorial Optimization
Issue number2
StatePublished - Aug 1 2017

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Deteriorating jobs
  • Maximum cost
  • Scheduling
  • Shortening jobs
  • Total completion time
  • Two agents


Dive into the research topics of 'Two-agent scheduling of time-dependent jobs'. Together they form a unique fingerprint.

Cite this