IDEAS home Printed from https://ideas.repec.org/a/wsi/apjorx/v35y2018i05ns0217595918500331.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Guoqiang Fan & Qingqin Nong, 2018. "A Coordination Mechanism for a Scheduling Game with Uniform-Batching Machines," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(05), pages 1-15, October.
    • Handle: RePEc:wsi:apjorx:v:35:y:2018:i:05:n:s0217595918500331
    DOI: 10.1142/S0217595918500331
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0217595918500331
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0217595918500331?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Petra Schuurman & Tjark Vredeveld, 2007. "Performance Guarantees of Local Search for Multiprocessor Scheduling," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 52-63, February.
    2. Rohde, K.I.M., 2005. "A reason for sophisticated investors not to seize arbitrage opportunities in markets without frictions," Research Memorandum 054, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    3. Chung-Yee Lee & Reha Uzsoy & Louis A. Martin-Vega, 1992. "Efficient Algorithms for Scheduling Semiconductor Burn-In Operations," Operations Research, INFORMS, vol. 40(4), pages 764-775, August.
    4. Schuurman, P. & Vredeveld, T., 2005. "Performance guarantees of local search for multiprocessor scheduling," Research Memorandum 055, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Q. Q. Nong & G. Q. Fan & Q. Z. Fang, 2017. "A coordination mechanism for a scheduling game with parallel-batching machines," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 567-579, February.
    2. Cole, Richard & Correa, Jose & Gkatzelis, Vasillis & Mirrokni, Vahab & Olver, Neil, 2015. "Decentralized utilitarian mechanisms for scheduling games," LSE Research Online Documents on Economics 103081, London School of Economics and Political Science, LSE Library.
    3. Francisco Castillo-Zunino & Pinar Keskinocak, 2021. "Bi-criteria multiple knapsack problem with grouped items," Journal of Heuristics, Springer, vol. 27(5), pages 747-789, October.
    4. Cong Chen & Yinfeng Xu, 0. "Coordination mechanisms for scheduling selfish jobs with favorite machines," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-33.
    5. Cong Chen & Yinfeng Xu, 2020. "Coordination mechanisms for scheduling selfish jobs with favorite machines," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 333-365, August.
    6. Petra Schuurman & Tjark Vredeveld, 2007. "Performance Guarantees of Local Search for Multiprocessor Scheduling," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 52-63, February.
    7. Yossi Azar & Lisa Fleischer & Kamal Jain & Vahab Mirrokni & Zoya Svitkina, 2015. "Optimal Coordination Mechanisms for Unrelated Machine Scheduling," Operations Research, INFORMS, vol. 63(3), pages 489-500, June.
    8. Dung-Ying Lin & Tzu-Yun Huang, 2021. "A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling Problem," Mathematics, MDPI, vol. 9(7), pages 1-20, April.
    9. Jianxin Fang & Brenda Cheang & Andrew Lim, 2023. "Problems and Solution Methods of Machine Scheduling in Semiconductor Manufacturing Operations: A Survey," Sustainability, MDPI, vol. 15(17), pages 1-44, August.
    10. Yang Fang & Peihai Liu & Xiwen Lu, 2011. "Optimal on-line algorithms for one batch machine with grouped processing times," Journal of Combinatorial Optimization, Springer, vol. 22(4), pages 509-516, November.
    11. Melouk, Sharif & Damodaran, Purushothaman & Chang, Ping-Yu, 2004. "Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing," International Journal of Production Economics, Elsevier, vol. 87(2), pages 141-147, January.
    12. Guochuan Zhang & Xiaoqiang Cai & C.‐Y Lee & C.K Wong, 2001. "Minimizing makespan on a single batch processing machine with nonidentical job sizes," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(3), pages 226-240, April.
    13. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    14. Li, Dongni & Jiang, Yuzhou & Zhang, Jinhui & Cui, Zihua & Yin, Yong, 2023. "An on-line seru scheduling algorithm with proactive waiting considering resource conflicts," European Journal of Operational Research, Elsevier, vol. 309(2), pages 506-515.
    15. Ruyan Fu & Ji Tian & Shisheng Li & Jinjiang Yuan, 2017. "An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities," Journal of Combinatorial Optimization, Springer, vol. 34(4), pages 1187-1197, November.
    16. Xu, Jun & Wang, Jun-Qiang & Liu, Zhixin, 2022. "Parallel batch scheduling: Impact of increasing machine capacity," Omega, Elsevier, vol. 108(C).
    17. Tobias Brueggemann & Johann L. Hurink & Tjark Vredeveld & Gerhard J. Woeginger, 2011. "Exponential size neighborhoods for makespan minimization scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(8), pages 795-803, December.
    18. Zhichao Geng & Jiayu Liu, 0. "Single machine batch scheduling with two non-disjoint agents and splitable jobs," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-22.
    19. Gregory Dobson & Ramakrishnan S. Nambimadom, 2001. "The Batch Loading and Scheduling Problem," Operations Research, INFORMS, vol. 49(1), pages 52-65, February.
    20. Zhou, Shengchao & Liu, Ming & Chen, Huaping & Li, Xueping, 2016. "An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes," International Journal of Production Economics, Elsevier, vol. 179(C), pages 1-11.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wsi:apjorx:v:35:y:2018:i:05:n:s0217595918500331. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/apjor/apjor.shtml .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.