基于合作博弈协商机制的分布式资源受限多项目调度
|
摘要
分布式资源受限多项目调度问题涉及多个项目的独立调度以及项目之间共享资源的协调分配,因此,解决该问题的关键是设计有效的机制获取协调全局资源所需的调度信息并据此配置全局资源.考虑每个单项目延期的影响程度不同,以最小化多项目总拖期成本为全局目标建立分层决策模型:考虑分布式多项目调度问题的信息不对称性和各单项目决策者的自利性,设计基于合作博弈协商机制的分阶段进化算法对问题求解.以MPSPLIB问题集开展实验研究,结果表明:采用合作博弈协商机制可以有效降低多项目的总延期成本,并且该求解机制对问题规模和资源冲突强度的变化有很好的适应性;自主Agent参与合作博弈并选择诚信策略可获得更高的单项目收益,同时多项目获得高质量的调度方案.
The distributed resource constrained multi-project scheduling problem(DRCMPSP)involves the individual scheduling of multiple projects and the coordination of shared resources among the projects.It is the crux of solving the DRCMPSP that designing an effective mechanism to obtain the necessary projects' information in order to coordinate the global resources.We constructed the hierarchical model with the global objective of optimizing the total delay cost of the multi-projects under the consideration of different unit project.And we designed a cooperative-game based negotiation mechanism to allocate the global resources and the hierarchical model was solved by the proposed phased evolution algorithm under the account of the information asymmetry in DRCMPSP and the self-interested project decision makers.According to the computational results of instances in MPSPLIB,it is effectively to decrease the total delay cost of the multi-projects that using the cooperative-game based negotiation mechanism and the approach is available to various problems with different sizes and utilization factors.In addition,in order to get low delay cost the autonomous agents should participate in the cooperative game and behave honestly and meanwhile a high-quality solution will be obtained.
The distributed resource constrained multi-project scheduling problem(DRCMPSP)involves the individual scheduling of multiple projects and the coordination of shared resources among the projects.It is the crux of solving the DRCMPSP that designing an effective mechanism to obtain the necessary projects' information in order to coordinate the global resources.We constructed the hierarchical model with the global objective of optimizing the total delay cost of the multi-projects under the consideration of different unit project.And we designed a cooperative-game based negotiation mechanism to allocate the global resources and the hierarchical model was solved by the proposed phased evolution algorithm under the account of the information asymmetry in DRCMPSP and the self-interested project decision makers.According to the computational results of instances in MPSPLIB,it is effectively to decrease the total delay cost of the multi-projects that using the cooperative-game based negotiation mechanism and the approach is available to various problems with different sizes and utilization factors.In addition,in order to get low delay cost the autonomous agents should participate in the cooperative game and behave honestly and meanwhile a high-quality solution will be obtained.
引文
[1]Payne J H.Management of multiple simultaneous projects:A state-of-the-art review[J].International Journal of Project Management,1995,13(3):163-168.
[2]Yang K K,Sum C C.A comparison of resource allocation and activity scheduling rules in a dynamic multi-project environment[J].Journal of Operations Management,1993,11(2):207-218.
[3]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.
[4]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.
[5]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.
[6]Arauzo J A,Galan J M,Pajares J,et al.Multi-agent technology for scheduling and control projects in multiproject environments.An Auction based approach[J].Inteligencia Artificial.Revista Iberoamericana de Inteligencia Artificial,2009,13(42):12-20.
[7]Arauzo 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.
[8]应瑛,寿涌毅.基于组合拍卖方法的资源受限多项目调度[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.
[9]王磊,战德臣,聂兰顺.基于市场机制的多项目分散式调度问题[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.
[10]Lau J S K,Huang G Q,Mak K L,et al. Distributed project scheduling with information sharing in supply chains:Part I—An agent-based negotiation model[J].International Journal of Introduction Research,2005,43(22):4813-4838.
[11]Homberger J.A(μ,λ)-coordination mechanism for agent-based multi-project scheduling[J].OR Spectrum,2012,34(1):107-132.
[12]Homberger J,Fink A.Generic negotiation mechanisms with side payments-design,analysis and application for decentralized resource-constrained multi-project scheduling problems[J].European Journal of Operational Research,2017,261(3):1001-1012.
[13]李飞飞,徐哲,于静.基于序贯博弈谈判机制的分布式多项目调度[J].系统工程理论与实践,2018,38(3):696-709.Li F F,Xu Z,Yu J.A sequential game-based negotiation approach to distributed multi-project scheduling problem[J].Systems Engineering—Theory&Practice,2018,38(3):696-709.
[14]李帮义,王玉燕,博弈论与信息经济学[M].北京:科学出版社,2016.Li B Y,Wang Y Y.Game theory and information economics[M].Beijing:Science Press,2016.
[15]Debels D,Vanhoucke M.A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem[J].Operations Research,2007,55(3):457-469.
[16]Mendes J,Goncalves J,Resende M.A random key based genetic algorithm for the resource constrained project scheduling problem[J].Computers&Operations Research,2009,36(1):92-109.
[17]Van Peteghem V,Vanhoucke M.A genetic algorithm for the preemptive and non-preemptive multi-mode resourceconstrained project scheduling problem[J].European Journal of Operational Research,2010,201(2):409-418.
[18]Valls V,Ballestin F,Quintanilla S.A hybrid genetic algorithm for the resource-constrained project scheduling problem[J].European Journal of Operational Research,2008,185(2):495-508.
[2]Yang K K,Sum C C.A comparison of resource allocation and activity scheduling rules in a dynamic multi-project environment[J].Journal of Operations Management,1993,11(2):207-218.
[3]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.
[4]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.
[5]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.
[6]Arauzo J A,Galan J M,Pajares J,et al.Multi-agent technology for scheduling and control projects in multiproject environments.An Auction based approach[J].Inteligencia Artificial.Revista Iberoamericana de Inteligencia Artificial,2009,13(42):12-20.
[7]Arauzo 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.
[8]应瑛,寿涌毅.基于组合拍卖方法的资源受限多项目调度[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.
[9]王磊,战德臣,聂兰顺.基于市场机制的多项目分散式调度问题[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.
[10]Lau J S K,Huang G Q,Mak K L,et al. Distributed project scheduling with information sharing in supply chains:Part I—An agent-based negotiation model[J].International Journal of Introduction Research,2005,43(22):4813-4838.
[11]Homberger J.A(μ,λ)-coordination mechanism for agent-based multi-project scheduling[J].OR Spectrum,2012,34(1):107-132.
[12]Homberger J,Fink A.Generic negotiation mechanisms with side payments-design,analysis and application for decentralized resource-constrained multi-project scheduling problems[J].European Journal of Operational Research,2017,261(3):1001-1012.
[13]李飞飞,徐哲,于静.基于序贯博弈谈判机制的分布式多项目调度[J].系统工程理论与实践,2018,38(3):696-709.Li F F,Xu Z,Yu J.A sequential game-based negotiation approach to distributed multi-project scheduling problem[J].Systems Engineering—Theory&Practice,2018,38(3):696-709.
[14]李帮义,王玉燕,博弈论与信息经济学[M].北京:科学出版社,2016.Li B Y,Wang Y Y.Game theory and information economics[M].Beijing:Science Press,2016.
[15]Debels D,Vanhoucke M.A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem[J].Operations Research,2007,55(3):457-469.
[16]Mendes J,Goncalves J,Resende M.A random key based genetic algorithm for the resource constrained project scheduling problem[J].Computers&Operations Research,2009,36(1):92-109.
[17]Van Peteghem V,Vanhoucke M.A genetic algorithm for the preemptive and non-preemptive multi-mode resourceconstrained project scheduling problem[J].European Journal of Operational Research,2010,201(2):409-418.
[18]Valls V,Ballestin F,Quintanilla S.A hybrid genetic algorithm for the resource-constrained project scheduling problem[J].European Journal of Operational Research,2008,185(2):495-508.