Coordination mechanisms with hybrid local policies

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

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


We study coordination mechanisms for scheduling n jobs on m parallel machines where agents representing the jobs interact to generate a schedule. Each agent acts selfishly to minimize the completion time of his/her own job, without considering the overall system performance that is measured by a central objective. The performance deterioration due to the lack of a central coordination, the so-called price of anarchy, is determined by the maximum ratio of the central objective function value of an equilibrium schedule divided by the optimal value. In the first part of the paper, we consider a mixed local policy with some machines using the SPT rule and other machines using the LPT rule. We obtain the exact price of anarchy for the problem of minimizing the makespan and some bounds for the problem of minimizing the total completion time. In the second part of the paper, we consider parallel machine scheduling subject to eligibility constraints. We devise new local policies based on the flexibilities and the processing times of the jobs. We show that the newly devised local policies outperform both the SPT and the LPT rules.

Original languageEnglish (US)
Pages (from-to)513-524
Number of pages12
JournalDiscrete Optimization
Issue number4
StatePublished - Nov 2011

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics


  • Coordination mechanism
  • Eligibility constraints
  • Makespan
  • Mixed local policy
  • Price of anarchy
  • Total completion time


Dive into the research topics of 'Coordination mechanisms with hybrid local policies'. Together they form a unique fingerprint.

Cite this