Competitive two-agent scheduling and its applications

Joseph Y.T. Leung, Michael Pinedo, Guohua Wan

Research output: Contribution to journalArticlepeer-review

173 Scopus citations


We consider a scheduling environment with m (m≥ 1) identical machines in parallel and two agents. Agent A is responsible for n1 jobs and has a given objective function with regard to these jobs; agent B is responsible for n 2 jobs and has an objective function that may be either the same or different from the one of agent A. The problem is to find a schedule for the n1 + n2 jobs that minimizes the objective of agent A (with regard to his n 1 jobs) while keeping the objective of agent B (with regard to his n2 jobs) below or at a fixed level Q. The special case with a single machine has recently been considered in the literature, and a variety of results have been obtained for two-agent models with objectives such as f max, ∑wjCj , and ∑Uj . In this paper, we generalize these results and solve one of the problems that had remained open. Furthermore, we enlarge the framework for the two-agent scheduling problem by including the total tardiness objective, allowing for preemptions, and considering jobs with different release dates; we consider also identical machines in parallel. We furthermore establish the relationships between two-agent scheduling problems and other areas within the scheduling field, namely rescheduling and scheduling subject to availability constraints.

Original languageEnglish (US)
Pages (from-to)458-469
Number of pages12
JournalOperations Research
Issue number2
StatePublished - Mar 2010

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research


  • Games/group decisions: cooperative sequencing
  • Parallel machines
  • Production/scheduling: multiagent deterministic sequencing
  • Single machine


Dive into the research topics of 'Competitive two-agent scheduling and its applications'. Together they form a unique fingerprint.

Cite this