Coordination mechanisms for parallel machine scheduling

Kangbok Lee, Joseph Y.T. Leung, Michael L. Pinedo

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


We consider coordination mechanisms for the distributed scheduling of n jobs on m parallel machines, where each agent holding a job selects a machine to process his/her own job. Without a central authority to construct a schedule, each agent acts selfishly to minimize his/her own disutility, which is either the completion time of the job or the congestion time (defined as the load of the machine on which the job is scheduled). However, the overall system performance is measured by a central objective which is quite different from the agents' objective. In the literature, makespan is often considered as the central objective. We, however, investigate problems with other central objectives that minimize the total congestion time, the total completion time, the maximum tardiness, the total tardiness, and the number of tardy jobs. The performance deterioration of the central objective by a lack of central coordination, referred to as the price of anarchy, is typically measured by the maximum ratio of the objective function value of a Nash equilibrium schedule versus that of an optimal, coordinated schedule. In this paper we give bounds for the price of anarchy for the above objectives. For problems with due date related objectives, the price of anarchy may not be defined since the optimal value may be zero. In this case, we consider the maximum difference between the objective function value of an equilibrium schedule and the optimal value. We refer to this metric as the absolute price of anarchy and analyze its lower and upper bounds.

Original languageEnglish (US)
Pages (from-to)305-313
Number of pages9
JournalEuropean Journal of Operational Research
Issue number2
StatePublished - Jul 16 2012

All Science Journal Classification (ASJC) codes

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


  • Absolute price of anarchy
  • Coordination mechanisms
  • Game
  • Parallel machine scheduling
  • Price of anarchy


Dive into the research topics of 'Coordination mechanisms for parallel machine scheduling'. Together they form a unique fingerprint.

Cite this