关键词: 反应式项目调度, 随机项目调度, 资源约束项目调度问题, 查找表方法

Abstract:

Under the uncertain environment， the actual practice of project scheduling is to generate a baseline schedule before the project starts. Then， in the execution process， the project is dynamically scheduled according to the baseline schedule under the interference of uncertain factors. In most cases with high uncertainty， project scheduling is run according to the iteration of “making baseline scheduling→executing→adjusting scheduling→executing→adjusting scheduling…” until the project is completed. However， so far， the mainstream uncertainty project scheduling problems， such as proactive scheduling， reactive scheduling， and stochastic scheduling， cannot be applied independently to this situation， thus limiting the application of uncertainty project scheduling theory research results in practical project management. To accommodate such project scheduling iterations due to uncertainty in the practical application scenario， a new resource-constrained dynamic reactive project scheduling method is proposed by fusing two uncertain project scheduling problems， reactive project scheduling and stochastic project scheduling. Before the actual scheduling， a heuristic algorithm based on priority rules is applied to generate a baseline schedule. In the actual scheduling process， all the decisions are made with the goal of minimizing the cost of adjustment to the baseline schedule. Firstly， a discrete-time Markov decision process （DT-MDP） model is built to describe the dynamic reactive scheduling process. The stochastic reactive resource-constrained project scheduling problem is first modeled by a discrete-time Markov decision process （DT-MDP）， in which decision points， state space， decision sets， state transfer equations， and the cost function are defined. Then， a look-up table algorithm is proposed based on the reinforcement learning theory to solve the problem， where the active durations are determined by Monte Carlo simulation and the projects are scheduled based on heuristic algorithms based on several priority rules. Finally， computation experiments are conducted based on the benchmark instances in PSPLIB to test the presented algorithm. The results show that the proposed method in this paper has obvious advantages compared with the existing stochastic scheduling methods. The method proposed in this paper not only remedies the deficiency of reactive scheduling in adjusting the plan without considering the randomness of subsequent activities， but also solves the problem of stochastic scheduling in the absence of a baseline scheduling plan. Since the method is closer to the actual uncertain project scheduling problem， it provides a new solution to various different project management practical application scenarios and offers a new idea for the integration and development of various uncertain project scheduling problems.

Key words: reactive project scheduling, stochastic project scheduling, resource constrained project scheduling problem, look-up table method