带有活动重叠的随机调度问题建模与算法研究

Model and Algorithm on Stochastic Scheduling Problem with Activity Overlapping

活动重叠不仅可以有效缩短项目研发周期,而且可以通过上下游活动之间信息的提前交流及时发现问题,降低研发失败的风险。在带有活动重叠的项目调度问题中,活动工期的不确定性会导致上下游活动重叠时刻和重叠时间的不确定,以及下游活动返工时间的不确定,该问题也是一类NP-hard问题。首先,建立了多阶段决策过程模型,用以描述活动工期不确定情形下带有活动重叠的随机调度过程;然后,设计了开环和闭环相结合的两阶段GA-Rollout算法:在GA算法中以独特的染色体编码和解码机制筛选出有效的重叠活动对,同时获得初始解作为Rollout过程的基础策略,再利用Rollout方法进行进一步优化;最后,通过大规模算例的实验研究和算法求解质量的对比分析,验证了本文两阶段GA-Rollout算法求解带有活动重叠的随机调度问题具有良好的求解质量。

Overlapping can not only effectively reduce the duration of R&D projects,but also decline the risk of R&D failure owe to finding the existing problems in time through the early exchange of information between upstream and downstream activities.In the project scheduling problem with activity overlapping,the uncertainty of activity duration will lead to uncertain overlapping time,uncertain overlapping amount,and uncertain rework time of downstream activities.The stochastic project scheduling is studied with activity overlapping which is NP-hard.Firstly,a multistage decision process model is established to describe the stochastic scheduling process with activities executing in overlapping way and uncertain activity durations.Then,a two-stage GA-rollout algorithm combining open-loop and close-loop policy is designed.A unique chromosome coding and decoding approach is embedded in the GA algorithm to select effective overlapping activities.And the initial solution obtained by GA is used as base policy,and then further optimized by rollout strategy.Finally,through the large-scale experimental study and the comparative analysis of the solution quality of different algorithms,the good performance of our GA-Rollout algorithm is verified.