多次抢占项目调度问题的混合遗传算法

来源：计算机工程与应用杂志2019年第6期北京时间：

作者：祝 政，胡志华

单位：上海海事大学 物流科学与工程研究院，上海 201306

摘要：研究多次抢占式资源受限的项目调度问题，假设任意时间点可作为资源抢占节点且抢占次数不受限制，建立满足多次资源抢占的线性整数规划模型并提出改进遗传算法对其进行求解。为克服遗传算法（GA）局部搜索能力缺陷，在算法中引入禁忌搜索（TS）进一步优化子代。针对性地设计了允许多次抢占的基于工作优先级编码策略以及串行调度方案生成机制。通过测试算例集实验调试算法参数，并以标准算例集（Project Scheduling Problem Library，PSPLIB）对算法进行可行性检验。实验结果表明，资源受限项目调度问题中引入多次抢占机制能有效缩减项目工期，设计的算法对问题求解效果良好。

关键词：资源受限,项目调度,多次抢占,遗传算法,禁忌搜索,参数调试