基于两阶段资源分配协调机制的分布式多项目随机调度

Distributed Multi-project Stochastic Scheduling with Two-stage Coordination Mechanism of Resources Allocation

企业趋向于多项目共享全局资源的分布式协同管理。但在多项目实际执行时,全局资源可用量往往由于外部环境的动态变化而存在不确定性,活动中断、资源浪费等现象频发,项目管理变得愈加复杂。本文将不确定的全局资源可用量建模为随机变量,设计两阶段资源分配协调机制,在预分配阶段,考虑项目允许的最大活动中断次数约束,建立各项目调度的马尔可夫动态决策过程模型;预分配结束后,基于活动重要度依次对剩余全局资源进行协调再分配,以提高资源利用率并减少平均项目延期。设计基于全局资源协调分配的Rollout近似动态规划算法进行求解。开展问题库算例实验研究与案例分析,验证协调机制与求解算法的性能;同时,探讨并分析不确定参数对目标结果的影响。

Enterprises tend to manage multiple projects in a distributed manner where the global resources are shared among autonomous projects.In the actual process of multi-projects scheduling,however,the availability of global resources is often uncertain due to some unexpected situations or stochastic factors,resulting in disruption of activities,waste of resources and other consequences.A new level of complexity is therefore added to the traditional project management.The distributed resource-constrained multi-project scheduling problem(DRCMPSP) is studied under uncertain global resource availabilities.A novel two-stage coordination mechanism for global resource allocation and local project scheduling is designed based on a multi-agent system(MAS) involving the interaction between coordination agent(CA) and each project agent(PA).Specifically,in the pre-allocation stage,CA firstly allocates the global resources to each PA according to the proportion of unit delay costs of local projects.A Markov dynamic decision process model for local project scheduling is established for each PA.At each decision point,the PA determines his initial optimal activities to be scheduled at the moment to minimize the local project makespan function.It is noteworthy that the maximum number of activity interruptions caused by infeasibility of global resources allowed by the local project is considered to reduce the cost loss of activity adjustment.After the first stage,the remaining global resources are reallocated by CA to candidate projects coordinately according to the activities’ importance to improve the resource utilization and reduce the average project expected delay(APED).PA reschedules and finally determines the optimal activity set that to be scheduled at the decision point.In order to solve the above DRCMPSP under uncertianty,an approximate dynamic programming algorithm based on Rollout with the global resource coordinated allocation is developed,where heuristics combine different priority rules and serial schedule generation scheme are employed to generate the base strategy for local project scheduling.Based on the DRCMPSP library MPSPLIB,the performance of our proposed coordination mechanism and solution algorithm is evaluated.Four instance sets from MPSPLIB are selected and adopted with contain 20 multi-project instances with different problem sizes and global resource scarcity levels.The uncertain availabilities of global resources are assumed to be random variables that obey different probability distributions.Accroding to the experimental results,the two-stage coordination mechanism can significantly reduce the APED compared to the mechnism without consideration of the coordinated reallocation stage.The proposed algorithm show better perfomance for multi-project instances with relatively sufficient and small distribution fluctuation of global resource availability.A sensitivity analysis is conducted on key parameters,which reveals that the more strict the requirement on the number of activity interruptions,the worse the solution results.Additionally,a small-size case is carried out to provide computational guidance for distibuted multi-project stochastic scheduling problem.It opens the door to further study the DRCMPSP with various realistic(multi-)project objectives and resources types under uncertainties.At the same time,more efficient stochastic scheduling algorithms will be explored to improve the solution quality and efficiency for the study of DRCMPSP extension problems.