基于序贯博弈谈判机制的分布式多项目调度

设计有效的全局资源分配协调机制是解决分布式多项目调度问题的关键.基于多Agcnt系统建立以单项目完工时间为优化目标的局部调度模型,并设计基于正向逆向调度改进的遗传算法求解初始局部调度计划;综合考虑每个项目单位延期成本的差异,建立以多项目总延期成本为优化目标的全局决策模型,设计多回合序贯博弈谈判机制协调全局资源分配,并调整单项目局部进度计划;开展示例分析和不同参数下问题集的实验研究.结果表明:基于正向逆向调度改进的遗传算法求解初始局部调度具有较好的问题规模适应性和较高的求解精度;全局资源冲突越强,造成多项目延期越大且项目延期完工的风险也越大;采用序贯博弈谈判机制相比无博弈随机分配协调机制可以有效地降低多项目的总延期损失成本.

A sequential game-based negotiation approach to distributed multi-project scheduling problem

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.