资源可用量不确定和活动多模式情形下的随机项目调度问题

Stochastic scheduling of projects with uncertain resource availabilities and multiple modes

可更新资源可用量的不确定是项目调度中普遍面临的问题,本文在随机资源可用量和活动多模式的约束下,考虑到活动可中断的情形,基于马尔可夫决策过程理论构建以最小化项目期望工期为目标的随机调度模型,针对问题特征设计以动态活动-模式优先规则和串行调度生成机制相结合的启发式算法作为基准策略的Rollout算法,并针对PSLIB的J30算例集展开实验研究。研究发现:随着资源可用量变化波动的增大,项目工期、活动中断次数以及问题的求解难度也随之增加;虽然考虑活动中断的优先规则在解决确定型问题时的表现优于不考虑活动中断的优先规则,但对于随机问题的效果却相反;本文提出的算法对于资源需求小或资源供应充足的情形求解效果更佳。本研究可以有效利用项目进度信息为项目管理者提供高质量的动态决策依据。

The multi-mode resource-constrained project scheduling problem(MRCPSP)has a strong application in construction engineering and software projects.It gives full consideration of the availabilities and optimization configuration of renewable resources.Solving the problem helps to provide decision support of schedule for the project manager before the start of project.The defect of MRCPSP is that various uncertainties in actual project scheduling have not been taken into consideration,such as the uncertain resource availabilities due to the maintenance of machines,employees′vacations,and the closure of work sites due to emergencies.Against this background,this paper discusses the stochastic scheduling of MRCPSP under uncertain resource availabilities with the objective of minimizing the expected project makespan.In the studied problem,we assume that the availabilities of uncertain renewable resources are stochastic variables.Under the constraints of precedence relationships among activities,the selection of activity modes,stochastic resource availabilities and activities′preemption,the starting activities together with their execution modes are dynamically decided until all activities are completed.Then a high-quality solution is obtained.Using the project data which is generated continuously,our paper aims to give a dynamic decision-making basis for project scheduling under the uncertain environment,which is of great significance for guiding project practice.Based on the problem description,a Markov decision process(MDP)model is established in the first part according to the problem characteristics.It consists of five parts:decision stage,state space,decision space,state transition function and objective function.The moment when some renewable resource is not sufficient or the unoccupied availability of some resource increases(including the moments when an activity is completed and the actual availability of some resource increases)is the decision time.At each decision time,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 realized resource availability matrix.The decision space is a set of binary vectors composed of the activities which can be scheduled and their corresponding feasible modes.The state transition function satisfies the Markov property,the next decision state is related to the current state,the current decision,and the resource availability matrix realized between two decision points,and has nothing with the previous decisions.At each decision stage,the optimal decision minimizes the expectation of the sum of makespan increase from the current stage to the ending of project.Large-scale MDP models will face with high-dimensional states and decision spaces.The resulting“dimensionality disaster”makes it difficult for traditional stochastic dynamic programming algorithms to obtain exact solutions.Therefore,based on the problem characteristics,some dedicated approximate algorithm should be designed for seeking high-quality near-optimal solutions.Rollout is an approximate optimization method originated from dynamic programming.It is essentially a forward iteration process of the base strategy.It has advantages of efficiency and easy operation,and has been successfully used to solve various stochastic scheduling problems.Hence,the Rollout algorithm is designed in the second part.The base strategy is a heuristic combining dynamic activity-mode priority rules and the improved serial scheduling generation scheme.It is used to solve the sub-problem at each decision-making stage,that is,the MRCPSP with activity preemption under the deterministic resource availabilities sample.The resource availabilities in each period can be determined by the Monte Carlo simulation of stochastic resource availabilities variables.After a comprehensive evaluation,the optimal activities set and their execution modes can be finally obtained.Through experimental computations,the effectiveness of our model and algorithm is verified in the third part.After the adaption of the J30 MRCPSP instances in the PSLIB,the experiments are carried out.They are the largest scale instances comparing with the other uncertain MRCPSP scheduling researches.Meanwhile,the T-test of paired samples together with a linear regression analysis is organized,the influences of problem parameters related to resources,the uncertain parameters of stochastic resource availabilities,and different priority rules on the problem and the quality and efficiency of Rollout algorithm are systematically analyzed.The findings show that a large fluctuation of stochastic resource availability will lead to increases of project makespan,the interruption number of activities and the difficulty of solving problems.Although priority rules considering the activity interruption perform better on solving deterministic problems than the ones ignoring the interruption priority value,there is an opposite effect on stochastic problems.Our proposed algorithm works better for the condition with low resource demand or sufficient resource supply.