Abstract: In order to improve the rationality of the project scheduling optimization process, a new method of scheduling and optimizing the conflict is introduced. Once the conflict occurs in the scheduling scheme, the start time of the project is not redefined. Instead, this paper migrates the time schedules of conflicts to get another feasible schedules, which improves the efficiency of algorithm computation. Then, the active and passive project scheduling problem is formulated as a single comprehensive problem, and the Markov decision process is used to model the above project scheduling optimization problem, and a dynamic programming method based on random graph is designed. The experimental results show the effectiveness of the proposed method in terms of convergence accuracy and computational efficiency, and demonstrate the rationality of the scheduling scheme through Gantt chart.

Key words: resource constraints, random graphs, Markov decision process, Gantt graph, state transfer

摘要： 为提高项目调度优化过程的合理性，引入一种新的项目调度优化应对冲突的方法，一旦冲突发生在调度方案中，不是重新定义项目的开始时间，而是对冲突的时间调度表进行状态的迁移，得到另一个可行的调度时间表，实现了算法计算效率的提升。然后，将主动和被动项目调度问题作为单一的综合问题来制定，并利用Markov决策过程对上述项目调度优化问题进行建模，有针对性地设计了一种基于随机图的动态规划求解方法。实验结果显示了所提方法在收敛精度和计算效率上的有效性，并通过甘特图方式对调度方案的合理性进行了论证。

关键词: 资源约束, 随机图, 马尔可夫决策过程, 甘特图, 状态转移