A game mechanism for single machine sequencing with zero risk

Mikhail Y. Kovalyov and Erwin Pesch

Omega, 2014, vol. 44, issue C, 104-110

Abstract: A problem is studied in which several non-cooperating clients compete for earlier execution of their jobs in a processing sequence of a single service provider in order to minimize job completion time costs. The clients can move their jobs earlier in a given sequence. They are assumed not to take a risky decision that can decrease their utility function. A game mechanism is suggested such that each client has no incentive to claim false cost and a social criterion is addressed, which is the minimum total cost of all clients. Algorithmic aspects of this mechanism are analyzed such as relations between the values of game equilibria and the social optimum, the computational complexity of finding a game equilibrium and the values of the price of anarchy and the price of stability.

Keywords: Scheduling; Logistics; Game theory; Algorithmic mechanism design (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048313001126
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:44:y:2014:i:c:p:104-110

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2013.11.001

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().