Scheduling two agents with controllable processing times

Guohua Wan, Sudheer R. Vakati, Joseph Y.T. Leung, Michael Pinedo

Research output: Contribution to journalArticlepeer-review

88 Scopus citations


We consider several two-agent scheduling problems with controllable job processing times, where agents A and B have to share either a single machine or two identical machines in parallel while processing their jobs. The processing times of the jobs of agent A are compressible at additional cost. The objective function for agent B is always the same, namely a regular function fmax. Several different objective functions are considered for agent A, including the total completion time plus compression cost, the maximum tardiness plus compression cost, the maximum lateness plus compression cost and the total compression cost subject to deadline constraints (the imprecise computation model). All problems are to minimize the objective function of agent A subject to a given upper bound on the objective function of agent B. These problems have various applications in computer systems as well as in operations management. We provide NP-hardness proofs for the more general problems and polynomial-time algorithms for several special cases of the problems.

Original languageEnglish (US)
Pages (from-to)528-539
Number of pages12
JournalEuropean Journal of Operational Research
Issue number3
StatePublished - Sep 16 2010

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


  • Agent scheduling
  • Availability constraints
  • Controllable processing times
  • Imprecise computation
  • Maximum lateness
  • Maximum tardiness
  • Total completion time


Dive into the research topics of 'Scheduling two agents with controllable processing times'. Together they form a unique fingerprint.

Cite this