A Coordination Mechanism for a Scheduling Game with Uniform-Batching Machines

Guoqiang Fan and Qingqin Nong
Additional contact information
Guoqiang Fan: School of Mechanical Engineering, Northwestern Polytechnical University, Xi’an, Shaanxi 710072, P. R. China2Department of Mathematics, Ocean University of China, Qingdao, Shandong 266071, P. R. China
Qingqin Nong: Department of Mathematics, Ocean University of China, Qingdao, Shandong 266071, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2018, vol. 35, issue 05, 1-15

Abstract: In this paper, we consider a scheduling problem with m uniform parallel-batching machines {M1,M2,…,Mm} under game situation. There are n jobs, each of which is associated with a load. Each machine Mi(1 ≤ i ≤ m) has a speed si and can handle up to b jobs simultaneously as a batch. The load of a batch is the load of the longest job in the batch. All the jobs in a batch start and complete at the same time. Each job is owned by an agent and its individual cost is the completion time of the job. The social cost is the largest completion time over all jobs, i.e., the makespan. We design a coordination mechanism for the scheduling game problem. We discuss the existence of Nash Equilibrium and offer an upper bound on the price of anarchy (POA) of the coordination mechanism. We present a greedy algorithm and show that: (i) under the coordination mechanism, any instance of the scheduling game problem has a unique Nash Equilibrium and it is precisely the schedule returned by the greedy algorithm; (ii) the mechanism has a POA no more than 1 + smax s̄ 1 − 1 max{m,b} + δ, where smax =max{s1,s2,…,sm}, s̄ = (s1 + s2 + ⋯ + sm)/m, and δ is a small positive number that tends to 0.

Keywords: Scheduling; game; coordination mechanism; Nash Equilibrium; price of anarchy (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595918500331
Access to full text is restricted to subscribers

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:wsi:apjorx:v:35:y:2018:i:05:n:s0217595918500331

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595918500331

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().