随机多模式资源受限项目调度  

Stochastic Multi-mode Resource-constrained Project Scheduling

作　　者：谢芳 李洪波[2] 柏庆国[3] XIE Fang;LI Hong-bo;BAI Qing-guo(School of Economics and Management,Yantai University,Yantai 264005,China;School of Management,Shanghai University,Shanghai 200444,China;School of Management,Qufu Normal University,Rizhao 276826,China)

机构地区：[1]烟台大学经济管理学院,山东烟台264005 [2]上海大学管理学院,上海200444 [3]曲阜师范大学管理学院,山东日照276826

出　　处：《中国管理科学》2022年第10期155-164,共10页Chinese Journal of Management Science

基　　金：教育部人文社会科学青年基金资助项目(17YJC630177);国家自然科学基金资助项目(71602106,71771138,71671117);山东省泰山学者工程资助项目(tsqn201812061);上海市软科学重点项目(20692192400)。

摘　　要：项目调度是实现项目资源优化配置的重要手段。项目执行时往往面临大量不确定因素,并呈现出典型的多模式特性,给项目调度带来了很大挑战。鉴于此,本文研究活动工期不确定条件下的多模式资源受限项目调度问题,建立了该问题的马尔科夫决策过程模型。为了高效求解上述模型,设计了基于Rollout的近似动态规划算法。该算法可以在项目执行过程中根据最新的项目状态动态给出调度方案,从而有效优化项目期望工期。在所提算法中,利用“活动—模式”列表与并行调度机制相结合的启发式算法构建基准策略,并设计了基于离散时间马尔科夫链的动态仿真,以进一步提升算法性能。基于公开的项目调度问题库PSPLIB,通过大规模计算实验分析了本文算法的性能,探讨了多种因素对调度效果的影响。In project management, project scheduling is an important method to achieve optimal resource allocation. Projects are often faced with many uncertain factors. The baseline schedules obtained under the deterministic assumption can hardly be executed as planned. Additionally, in practice, projects tend to have the characteristic of multiple modes. The above situations pose a great challenge to the effectiveness of project scheduling. In view of this, the multi-mode resource-constrained project scheduling problem is studied under uncertain activity durations and it aims to construct effective dynamic scheduling policies.For the above problem, a Markov decision process model is first proposed which consists of five parts: stages, states, decisions, transition process and cost function. In the proposed model, the activity completion time corresponds to the decision stage. At each decision stage, the state space is composed of the completed activity set, the active activity set, the activity execution mode vector, the executed activity duration vector and the activities’ starting time vector. The decision space is a set of vectors representing the activities that can be scheduled and their corresponding feasible modes. The state transition function describes how the next state is reached after each decision is made. Every optimal decision should minimize the cost function, i.e., the expected sum of makespan increase from the current stage to the completion of the project.In order to efficiently solve the above model, an approximate dynamic programming algorithm based on Rollout is developed, which can dynamically make a scheduling decision according to the latest status during project execution, and thereby effectively optimizing the expected project makespan. In the proposed algorithm, a heuristic combined with an “activity-mode” list and a parallel schedule generation scheme is used to generate the base strategy. A discrete-time Markov chain simulation is further designed to improve the algorithm.Based on the p

关 键 词：项目调度 工期不确定 多模式 马尔科夫决策过程 ROLLOUT算法 动态策略 

分 类 号：N945[自然科学总论—系统科学] O223[理学—运筹学与控制论]