A sequential game-based negotiation approach to distributed multi-project scheduling problem
LI Feifei1, XU Zhe1, YU Jing2
1. School of Economics and Management, Beihang University, Beijing 100191, China; 2. School of Management, Tianjin University of Technology, Tianjin 300383, China
Abstract：It is the key to solve the distributed resource constrained multi-project scheduling problem by designing effective coordination mechanism to allocate global resources. Based on multi-agent system (MAS), the local scheduling model is established to optimize the project completion time. Initial local scheduling can be solved by the improved genetic algorithm based on forward-backward scheduling method. Given the different unit tardiness cost of each project, global coordination decision model is developed to optimize the multi-project total tardiness cost. Global resources are allocated reasonably after several rounds of sequential game-based negotiation and then the local scheduling of each project is modified. An instance and problem sets with different parameters are studied. The results show that:the proposed improved genetic algorithm based on forward-backward scheduling method has better problem scale adaptability and higher accuracy on solving the initial local scheduling problem; the stronger the global resources conflict, the more the multi-project delays and the greater the risk of project delay completion is; by comparing the results obtained by non-game distributed randomly coordination mechanism, it demonstrates that the sequential game-based negotiation approach can reduce the total tardiness cost for multi-project effectively.
[1] Turner J R. The handbook of project-based management[M]. New York:McGraw-Hill, 2008. [2] Hartmann S, Briskorn D. A survey of variants and extensions of the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 2010, 207(1):1-14. [3] Kurtulus I, Davis E W. Multi-project scheduling:Categorization of heuristic rules performance[J]. Management Science, 1982, 28(2):161-172. [4] Goncalves J F, Mendes J J M, Resende M G C. A genetic algorithm for the resource constrained multi-project scheduling problem[J]. European Journal of Operational Research, 2008, 189(3):1171-1190. [5] Beşikci U, Bilge Ü, Ulusoy G. Resource dedication problem in a multi-project environment[J]. Flexible Services and Manufacturing Journal, 2013, 25(1-2):206-229. [6] Confessore G, Giordani S, Rismondo S. A market-based multi-agent system model for decentralized multi-project scheduling[J]. Annals of Operations Research, 2007, 150(1):115-135. [7] Lee Y H, Kumara S R T, Chatterjee K. Multiagent based dynamic resource scheduling for distributed multiple projects using a market mechanism[J]. Journal of Intelligent Manufacturing, 2003, 14(5):471-484. [8] Homberger J. A multi-agent system for the decentralized resource-constrained multi-project scheduling problem[J]. International Transactions in Operational Research, 2007, 6(14):565-589. [9] Homberger J. A (μ, λ)-coordination mechanism for agent-based multi-project scheduling[J]. OR Spectrum, 2012, 34(1):107-132. [10] Agnetis A, Briand C, Billaut J C, et al. Nash equilibria for the multi-agent project scheduling problem with controllable processing times[J]. Journal of Scheduling, 2015, 18(1):15-27. [11] 应瑛, 寿涌毅. 基于组合拍卖方法的资源受限多项目调度[J]. 计算机集成制造系统, 2009, 15(11):2160-2165.Ying Y, Shou Y Y. Resource-constrained multi-project scheduling based on combinatorial auction method[J]. Computer Integrated Manufacturing Systems, 2009, 15(11):2160-2165. [12] 王磊, 战德臣, 聂兰顺. 基于市场机制的多项目分散式调度问题[J]. 计算机集成制造系统, 2014, 20(8):1969-1979.Wang L, Zhan D C, Nie L S. Multi-project decentralized scheduling problem solving by market mechanism[J]. Computer Integrated Manufacturing Systems, 2014, 20(8):1969-1979. [13] Araúo J A, Pajares J, Lopez-Paredes A. Simulating the dynamic scheduling of project portfolios[J]. Simulation Modelling Practice and Theory, 2010, 18(10):1428-1441. [14] Adhau S, Mittal M L. A multi-agent based approach for dynamic multi-project scheduling[J]. International Journal of Advanced Operations Management, 2011, 3(3/4):230-238. [15] Adhau S, Mittal M L, Mittal A. A multi-agent system for decentralized multi-project scheduling with resource transfers[J]. International Journal of Production Economics, 2013, 146(2):646-661. [16] Zheng Z, Guo Z, Zhu Y, et al. A critical chains based distributed multi-project scheduling approach[J]. Neurocomputing, 2014, 143(16):282-293. [17] Wauters T, Verbeeck K, De Causmaecker P, et al. A learning-based optimization approach to multi-project scheduling[J]. Journal of Scheduling, 2015, 18(1):61-74. [18] Wauters T, Verbeeck K, Berghe G V, et al. A game theoretic approach to decentralized multi-project scheduling (Extended abstract)[C]//Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, 2010:1415-1416. [19] Hsu C Y, Kao B R, Lai K R. Agent-based fuzzy constraint-directed negotiation mechanism for distributed job shop scheduling[J]. Engineering Applications of Artificial Intelligence, 2016, 53:140-154. [20] Tang J, Zeng C, Pan Z. Auction-based cooperation mechanism to parts scheduling for flexible job shop with inter-cells[J]. Applied Soft Computing, 2016, 49:590-602. [21] Lang F, Fink A, Brandt T. Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling[J]. European Journal of Operational Research, 2016, 248(1):192-203. [22] 杨树, 黄国全, 梁樑. 基于竞标的供应链分布式项目调度方法[J]. 管理工程学报, 2008, 22(2):41-45.Yang S, Huang G Q, Liang L. Auction based distributed supply chain project scheduling[J]. Journal of Industrial Engineering and Engineering Management, 2008, 22(2):41-45. [23] Rao C J, Xiao X P, Goh M, et al. Compound mechanism design of supplier selection based on multi-attribute auction and risk management of supply chain[J]. Computers & Industrial Engineering, 2017, 105:63-75. [24] Lova A, Tormos P. Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling[J]. Annals of Operations Research, 2011, 102(1):263-286. [25] Hartmann S, Kolisch R. Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 2000, 127(2):394-407. [26] 李洪波, 徐哲, 于静. 基于DSM的研发项目流程多目标仿真优化[J]. 系统工程理论与实践, 2015, 35(1):142-149.Li H B, Xu Z, Yu J. Multi-objective simulation optimization for the process of R&D projects based on DSM[J]. Systems Engineering-Theory & Practice, 2015, 35(1):142-149. [27] 于静, 徐哲, 李洪波. 带有活动重叠的资源受限项目调度问题建模与求解[J]. 系统工程理论与实践, 2015, 35(5):1236-1245.Yu J, Xu Z, Li H B. Modeling and solving the resource-constrained project scheduling problem with activities overlapping[J]. Systems Engineering-Theory & Practice, 2015, 35(5):1236-1245. [28] Willis R J, Li K Y. An iterative scheduling technique for resource-constrained project scheduling[J]. European Journal of Operational Research, 1992, 56(3):370-379. [29] 谢芳, 徐哲, 于静. 柔性资源约束下的项目调度问题双目标优化[J]. 系统工程理论与实践, 2016, 36(3):674-683.Xie F, Xu Z, Yu J. Bi-objective optimization for the project scheduling problem with variable resource availability[J]. Systems Engineering-Theory & Practice, 2016, 36(3):674-683. [30] 张维迎. 博弈论与信息经济学[M]. 上海:上海人民出版社, 2004.Zhang W Y. Game theory and information economics[M]. Shanghai:Shanghai People's Publishing House, 2004. [31] Deng M T, Chiu H N. Two heuristics for scheduling multiple projects with resource constraints[J]. Construction Management and Economics, 1996, 14(4):325-340. [32] Sonmez R, Uysal F. Backward-forward hybrid genetic algorithm for resource-constrained multiproject scheduling problem[J]. Journal of Computing in Civil Engineering, 2015, 29(5):04014072. [33] Deblaere F, Demeulemeester E, Herroelen W. RESCON:Educational project scheduling software[J]. Computer Applications in Engineering Education, 2011, 19(2):327-336. [34] 张静文, 徐渝, 何正文, 等. 项目调度中的时间-费用权衡问题研究综述[J]. 管理工程学报, 2007, 21(1):92-97.Zhang J W, Xu Y, He Z W, et al. A review on the time/cost trade-offs problem in project scheduling[J]. Journal of Industrial Engineering and Engineering Management, 2007, 21(1):92-97. [35] Aminbakhsh S, Sonmez R. Pareto front particle swarm optimizer for discrete time-cost trade-off problem[J]. Journal of Computing in Civil Engineering, 2016, 31(1):04016040.
2018, Vol. 38 
