摘要
实际项目进程中因不确定因素导致活动执行被迫中断的情况时有发生,该研究针对允许活动在任意单位时间节点被中断的抢占型资源约束项目调度问题,设计了一种启发式算法。算法首先通过网络图的转化规则将活动进行拆分,然后结合深度优先和广度优先搜索设计了一类基于时间窗延迟方案的调度生成机制。通过调用PSPLIB数据库,设置不同参数,设计多组实验进行分析,结果表明,相较于非抢占模式,该算法在求解允许抢占模式的项目调度问题时表现出更优的结果,尤其对于大规模项目,验证了算法的有效性。同时与基本精确算法对比,该算法表现出更好求解速率,该求解结果为实际项目调度提供了决策参考。
With the development of economy,the projects of enterprises are generally large,diversified and complicated.And there are many uncertainties accompanying the project execution process.In many actual projects,the execution of activities is often interrupted due to uncertainties.Activity interruption can change the state of resources,execution duration of the activity and the logical relationship between activities,and how to schedule the project after activity interruption has become a new topic,gradually forming a preemptive resource constrained project scheduling problem,namely PRCPSP.However,most of the existing studies on PRCPSP are based on the assumption that the number of preemptions is one or more at fixed nodes,which is not entirely consistent with the realistic background.With the changing complexity of the environment,the execution of projects is becoming increasingly complex,especially for large and emergency projects,where there are more uncertain factors.Random multiple preemptions have become an effective way to alleviate resource conflicts and shorten project time.In this context,studying project scheduling with random preemption has become particularly important.Therefore,based on the existing research,this paper studies the stochastic preemptive project scheduling problem in uncertain environments,constructs a model of preemptive resource-constrained project scheduling problem in which any activity is allowed to be interrupted at any time node,and designs a heuristic algorithm with time window delay scheme,which provides a new approach to solving stochastic preemption problem.In the algorithm,the transformation rule of active network graph is first introduced,and then,based on the depth-first and breadth-first solution strategies,a scheduling generation scheme based on time-window delay scheme is produced.By invoking the PSPLIB(Project scheduling problem library) datasets,setting different parameters,and designing several groups of computational experiments.The computational results show that,com
作者
王敏
张转霞
WANG Min;ZHANG Zhuanxia(School of Business,Renmin University of China,Beijing 100872,China;School of Information,North China University of Technology,Beijing 100093,China)
出处
《运筹与管理》
CSCD
北大核心
2023年第6期46-52,共7页
Operations Research and Management Science
关键词
多次抢占
资源约束项目调度
时间窗延迟
启发式算法
multiple preemption
resource-constrained project scheduling
time-window delay
heuristic algorithm
