基于拍卖理论的动态多代理同类机调度算法

Yaqiong Liu; Shudong Sun; Gaopan Shen; Xi Vincent Wang; Magnus Wiktorsson; Lihui Wang

doi:10.1016/j.eng.2023.09.024

PDF(2174 KB)

工程（英文） ›› 2024, Vol. 35 ›› Issue (4) : 32-45. DOI: 10.1016/j.eng.2023.09.024

研究论文

Article

基于拍卖理论的动态多代理同类机调度算法

Yaqiong Liu ^a^,^b^,^c ,
Shudong Sun ^a^,^b ,
Gaopan Shen ^a^,^b ,
Xi Vincent Wang ^c ,
Magnus Wiktorsson ^c ,
Lihui Wang ^c^,^*

作者信息 +

An Auction-Based Approach for Multi-Agent Uniform Parallel Machine Scheduling with Dynamic Jobs Arrival

Yaqiong Liu ^a^,^b^,^c ,
Shudong Sun ^a^,^b ,
Gaopan Shen ^a^,^b ,
Xi Vincent Wang ^c ,
Magnus Wiktorsson ^c ,
Lihui Wang ^c^,^*

Author information +

History +

Abstract

This paper addresses a multi-agent scheduling problem with uniform parallel machines owned by a resource agent and competing jobs with dynamic arrival times that belong to different consumer agents. All agents are self-interested and rational with the aim of maximizing their own objectives, resulting in intense resource competition among consumer agents and strategic behaviors of unwillingness to disclose private information. Within the context, a centralized scheduling approach is unfeasible, and a decentralized approach is considered to deal with the targeted problem. This study aims to generate a stable and collaborative solution with high social welfare while simultaneously accommodating consumer agents’ preferences under incomplete information. For this purpose, a dynamic iterative auction-based approach based on a decentralized decision-making procedure is developed. In the proposed approach, a dynamic auction procedure is established for dynamic jobs participating in a real-time auction, and a straightforward and easy-to-implement bidding strategy without price is presented to reduce the complexity of bid determination. In addition, an adaptive Hungarian algorithm is applied to solve the winner determination problem efficiently. A theoretical analysis is conducted to prove that the proposed approach is individually rational and that the myopic bidding strategy is a weakly dominant strategy for consumer agents submitting bids. Extensive computational experiments demonstrate that the developed approach achieves high-quality solutions and exhibits considerable stability on large-scale problems with numerous consumer agents and jobs. A further multi-agent scheduling problem considering multiple resource agents will be studied in future work.

Graphical abstract

Keywords

Multi-agent scheduling / Decentralized scheduling / Auction / Dynamic jobs / Private information

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用

Yaqiong Liu, Shudong Sun, Gaopan Shen. . Engineering. 2024, 35(4): 32-45 https://doi.org/10.1016/j.eng.2023.09.024

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序

[1]	B. Wang, F. Tao, X. Fang, C. Liu, Y. Liu, T. Freiheit. Smart manufacturing and intelligent manufacturing: a comparative review. Engineering, 7 (6) (2021), pp. 738-757.
[2]	T. Yang, X. Yi, S. Lu, K.H. Johansson, T. Chai. Intelligent manufacturing for the process industry driven by industrial artificial intelligence. Engineering, 7 (9) (2021), pp. 1224-1230.
[3]	E.B. Edis, C. Oguz, I. Ozkarahan. Parallel machine scheduling with additional resources: notation, classification, models and solution methods. Eur J Oper Res, 230 (3) (2013), pp. 449-463.
[4]	D. Wang, Y. Yu, Y. Yin, T.C.E. Cheng. Multi-agent scheduling problems under multitasking. Int J Prod Res, 59 (12) (2021), pp. 3633-3663.
[5]	A. Agnetis, D. Pacciarelli, A. Pacifici. CCombinatorial models for multi-agent scheduling problems. E. Levner (Ed.), Multiprocessor scheduling: theory and applications, IntechOpen, London (2007), pp. 21-46.
[6]	M.L. Pinedo. Scheduling: theory, algorithms and systems. (4th ed.), Springer, New York (2012).
[7]	Y. Liu, S. Sun, X.V. Wang, L. Wang. An iterative combinatorial auction mechanism for multi-agent parallel machine scheduling. Int J Prod Res, 60 (1) (2022), pp. 361-380.
[8]	J. Pei, J. Wei, B. Liao, X. Liu, P.M. Pardalos. Two-agent scheduling on bounded parallel-batching machines with an aging effect of job-position-dependent. Ann Oper Res, 294 (2020), pp. 191-223.
[9]	F. Yu, P. Wen, S. Yi. A multi-agent scheduling problem for two identical parallel machines to minimize total tardiness time and makespan. Adv Mech Eng, 10 (2) (2018), pp. 1-14.
[10]	L. Mönch, L. Shen. Parallel machine scheduling with the total weighted delivery time performance measure in distributed manufacturing. Comput Oper Res, 127 (2021), 105126.
[11]	Abdel-Jabbar MAH, Kacem I, Martin S. Unrelated parallel machines with precedence constraints:application to cloud computing. In:Proceedings of 2014 IEEE 3rd International Conference on Cloud Networking (CloudNet); 2014 Oct 8-10; Luxembourg, Luxembourg. Piscataway: IEEE; 2014. p. 438-42.
[12]	Y. Zhou, R. Kumar, S. Tang. Incentive-based distributed scheduling of electric vehicle charging under uncertainty. IEEE Trans Power Syst, 34 (1) (2019), pp. 3-11.
[13]	N.N. Alimin, N.A.A. Rahmin, G. Ibragimov, M.A. Nazihah. Multi-start local search for online scheduling in parallel operating theatre. Adv Math Sci J, 9 (12) (2020), pp. 10915-10927.
[14]	A. Lieder, R. Stolletz. Scheduling aircraft take-offs and landings on interdependent and heterogeneous runways. Transp Res Part E, 88 (2016), pp. 167-188.
[15]	J. Yuan, C.T. Ng, T. Cheng. Scheduling with release dates and preemption to minimize multiple max-form objective functions. Eur J Oper Res, 280 (3) (2020), pp. 860-875.
[16]	T. Kugler, E.E. Kausel, M.G. Kocher. Are groups more rational than individuals? A review of interactive decision making in groups. WIREs Cogn Sci, 3 (4) (2012), pp. 471-482.
[17]	M. Klein, P. Faratin, H. Sayama, Y. Bar-Yam. Negotiating complex contracts. Group Decis Negot, 12 (2) (2003), pp. 111-125.
[18]	C. Schneeweiss. Distributed decision making. Springer, Berlin (2003).
[19]	Y. Lu, L. Yang, K. Yang, Z. Gao, H. Zhou, F. Meng, et al. A distributionally robust optimization method for passenger flow control strategy and train scheduling on an urban rail transit line. Engineering, 12 (2022), pp. 202-220.
[20]	P. Renna. Multi-agent based scheduling in manufacturing cells in a dynamic environment. Int J Prod Res, 49 (5) (2011), pp. 1285-1301.
[21]	Arrow KJ, Sen A, Suzumura K. Handbook of social choice and welfare. Volume 2. London:Elsevier; 2011.
[22]	G. Deconinck, K. De Craemer, B. Claessens. Combining market-based control with distribution grid constraints when coordinating electric vehicle charging. Engineering, 1 (4) (2015), pp. 453-465.
[23]	J. Tang, C. Zeng, Z. Pan. Auction-based cooperation mechanism to parts scheduling for flexible job shop with inter-cells. Appl Soft Comput, 49 (2016), pp. 590-602.
[24]	Q. Zhu, X. Wang. Auction-based capacity allocation in two parallel machines with inclusive processing set restrictions. Math Probl Eng, 2022 (2022), pp. 1-11.
[25]	N.G. Hall, Z. Liu. Market good flexibility in capacity auctions. Prod Oper Manag, 22 (2) (2013), pp. 459-472.
[26]	W. Song, D. Kang, J. Zhang, H. Xi. A multi-unit combinatorial auction based approach for decentralized multi-project scheduling. Auton Agent Multi-Agent Syst, 31 (6) (2017), pp. 1548-1577.
[27]	A. Daoud, F. Balbo, P. Gianessi, G. Picard. ORNInA: a decentralized, auction-based multi-agent coordination in ODT systems. AI Commun, 34 (1) (2021), pp. 37-53.
[28]	M. Zade, S.D. Lumpp, P. Tzscheutschler, U. Wagner. Satisfying user preferences in community-based local energy markets—auction-based clearing approaches. Appl Energy, 306 (2022), 118004.
[29]	E. Kutanoglu, S.D. Wu. On combinatorial auction and Lagrangean relaxation for distributed resource scheduling. IIE Trans, 31 (9) (1999), pp. 813-826.
[30]	C. Zeng, J. Tang, Z. Fan, C. Yan. Auction-based approach for a flexible job-shop scheduling problem with multiple process plans. Eng Optim, 51 (11) (2019), pp. 1902-1919.
[31]	C. Zeng, G. Qi, Z. Liu, J. Tang, Z.P. Fan, C. Yan. Auction-based approach with improved disjunctive graph model for job shop scheduling problem with parallel batch processing. Eng Appl Artif Intell, 110 (2022), 104735.
[32]	W. Kong, Y. Lei, J. Ma. Virtual machine resource scheduling algorithm for cloud computing based on auction mechanism. Optik, 127 (12) (2016), pp. 5099-5104.
[33]	P. Dewan, S. Joshi. Auction-based distributed scheduling in a dynamic job shop environment. Int J Prod Res, 40 (5) (2002), pp. 1173-1191.
[34]	P. Dewan, S. Joshi. Implementation of an auction-based distributed scheduling model for a dynamic job shop environment. Int J Comput Integr Manuf, 14 (5) (2001), pp. 446-456.
[35]	M. Masin, M.O. Pasaogullari, S. Joshi. Dynamic scheduling of production-assembly networks in a distributed environment. IIE Trans, 39 (4) (2007), pp. 395-409.
[36]	J.A. Araúzo, J. Pajares, A. Lopez-Paredes. Simulating the dynamic scheduling of project portfolios. Simul Model Pract Theory, 18 (10) (2010), pp. 1428-1441.
[37]	L. Tosselli, V. Bogado, E. Martínez. A repeated-negotiation game approach to distributed (re)scheduling of multiple projects using decoupled learning. Simul Model Pract Theory, 98 (2020), 101980.
[38]	Vishalatchi M, Krishnamoorthy N, Sangeetha S. Optimised scheduling in cloud computing. In:Proceedings of 2017 International Conference on Algorithms, Methodology, Models and Applications in Emerging Technologies (ICAMMAET); 2017 Feb 16-18; Chennai, India. Piscataway: IEEE; 2017. p. 1-6.
[39]	Mukherjee P, Goswami S, Paul B, Chanda CK. Scheduling of generation and loads through market clearing auction in a dynamic power market. In:Proceedings of 2022 4th International Conference on Energy, Power and Environment (ICEPE); 2022 Apr 29-May 1; Shillong,India. Piscataway: IEEE; 2022. p. 1-6.
[40]	M.P. Wellman, W.E. Walsh, P.R. Wurman, J.K. MacKie-Mason. Auction protocols for decentralized scheduling. Games Econ Behav, 35 (1-2) (2001), pp. 271-303.
[41]	Pan H, Gao H, Ma W, Liu J. Dynamic bidding strategy for electricity retailers considering multi-type demand response. In:Proceedings of 2020 IEEE Sustainable Power and Energy Conference (iSPEC); 2020 Nov 23-25; Chengdu, China; Piscataway: IEEE; 2020. p. 1127-32.
[42]	F.S. Hsieh. Combinatorial reverse auction based on revelation of Lagrangian multipliers. Decis Support Syst, 48 (2) (2010), pp. 323-330.
[43]	B. Mansouri, E. Hassini. A Lagrangian approach to the winner determination problem in iterative combinatorial reverse auctions. Eur J Oper Res, 244 (2) (2015), pp. 565-575.
[44]	T. Pennanen. Efficient allocations in double auction markets. Math Oper Res, 47 (2) (2022), pp. 1648-1663.
[45]	C. Wang, F. Dargahi, M.F.H. Bhuiyan. On the tradeoff between privacy and efficiency: a bidding mechanism for scheduling non-commercial services. Comput Ind, 63 (6) (2012), pp. 610-618.
[46]	L. Liu, C. Wang, J. Wang. A combinatorial auction mechanism for surgical scheduling considering surgeon’s private availability information. J Comb Optim, 37 (1) (2019), pp. 405-417.
[47]	Merz F, Schwindt C, Westphal S, Zimmermann J. An auction-based mechanism for the formation and scheduling of heterogeneous human-machine teams. In:Proceedings of 2021 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM); 2021 Dec 13-16; Singapore. Piscataway: IEEE; 2021. p. 863-8.
[48]	A. Ebrahimi, H.W. Jeon, S. Lee, C. Wang. Minimizing total energy cost and tardiness penalty for a scheduling-layout problem in a flexible job shop system: a comparison of four metaheuristic algorithms. Comput Ind Eng, 141 (2020), 106295.
[49]	Y.F. Hung, J.S. Bao, Y.E. Cheng. Minimizing earliness and tardiness costs in scheduling jobs with time windows. Comput Ind Eng, 113 (2017), pp. 871-890.
[50]	Y. He, Y. Li, T. Wu, J.W. Sutherland. An energy-responsive optimization method for machine tool selection and operation sequence in flexible machining job shops. J Clean Prod, 87 (2015), pp. 245-254.
[51]	M.L. Pinedo. Deterministic models: preliminaries. M.L. Pinedo (Ed.), Scheduling, Springer, Cham (2016), pp. 13-32.
[52]	N.T. Nguyen, T.T. Nguyen, M. Roos, J. Rothe. Computational complexity and approximability of social welfare optimization in multiagent resource allocation. Auton Agent Multi-Agent Syst, 28 (2) (2014), pp. 256-289.
[53]	K.T. Fang, B.M.T. Lin. Parallel-machine scheduling to minimize tardiness penalty and power cost. Comput Ind Eng, 64 (1) (2013), pp. 224-234.
[54]	F.M. Menezes, P.K. Monteiro. An introduction to auction theory. Oxford University Press, Oxford (2004).
[55]	N. Nisan. Bidding languages for combinatorial auctions. P. Cramton, Y. Shoham, R. Steinberg (Eds.), Combinatorial auctions, MIT Press Scholarship Online, Cambridge (2005), pp. 215-232.
[56]	L.M. Ausubel, P. Milgrom. Ascending proxy auctions. P. Cramton, Y. Shoham, R. Steinberg (Eds.), Combinatorial auctions, MIT Press Scholarship Online, Cambridg (2005), pp. 79-98.
[57]	Pikovsky A. Pricing and bidding strategies in iterative combinatorial auctions. Munich: Technische Universität München; 2008.
[58]	Z. Wang, Z. Feng, P. Zhang. An iterative Hungarian algorithm based coordinated spectrum sensing strategy. IEEE Commun Lett, 15 (1) (2011), pp. 49-51.
[59]	G. Rabadi, R.J. Moraga, A. Al-Salem. Heuristics for the unrelated parallel machine scheduling problem with setup times. J Intell Manuf, 17 (1) (2006), pp. 85-97.
[60]	Y. Liu, L. Wang, Y. Wang, X.V. Wang, L. Zhang. Multi-agent-based scheduling in cloud manufacturing with dynamic task arrivals. Procedia CIRP, 72 (2018), pp. 953-960.
[61]	M. Ðurasević, D. Jakobović. A survey of dispatching rules for the dynamic unrelated machines environment. Expert Syst Appl, 113 (2018), pp. 555-569.
[62]	J.H. Lee, Y. Kim, Y.B. Kim, B.H. Kim, G.H. Jung, H.J. Kim. A sequential search method of dispatching rules for scheduling of LCD manufacturing systems. IEEE Trans Semicond Manuf, 33 (4) (2020), pp. 496-503.
[63]	R. Liu, R. Piplani, C. Toro. Deep reinforcement learning for dynamic scheduling of a flexible job shop. Int J Prod Res, 60 (13) (2022), pp. 4049-4069.
[64]	C.Y. Cheng, L.W. Huang. Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control. J Manuf Syst, 42 (2017), pp. 1-10.