A column-generation-based algorithm for a resource-constrained project scheduling problem with a fractional shared resource
A column-generation-based algorithm for a resource-constrained project scheduling problem with a fractional shared resource
复制标题
DOI：
10.1080/0305215x.2019.1610946
复制
发表时间：
2019-05
影响因子：
2.7
通讯作者：
Qiang Wang;Changchun Liu;Li Zheng
中科院分区：
文献类型：
--
作者：
Qiang Wang;Changchun Liu;Li Zheng
摘要本文研究了一个资源受限、资源共享的项目调度问题。在该模型中，需要多个处理机以一定数量的共享资源来完成作业。资源的供应是有限的，必须在处理器之间共享。提出了一种基于列生成的算法，并采用了稳定化、解池更新机制和近似解技术等增强技术。最后，通过与拉格朗日松弛、CPLEX和自适应遗传算法的比较，通过大量的计算实验评估了该方法的性能。实验结果表明，该方法在目标和计算时间上具有优势。文中还进行了数值实验，以验证改进算法的有效性。
ABSTRACT This article considers a resource-constrained project scheduling problem with a single shared resource. In this model, multiple processors are required to complete jobs with a certain amount of shared resource. The supply of the resource is limited and must be shared between processors. A column-generation-based algorithm with some enhancement techniques, including stabilization, a mechanism to update the solution pool, and an approximate solution technique, is proposed. Finally, extensive computational experiments are conducted to evaluate the performance of the proposed method by comparing it with Lagrangian relaxation, CPLEX and a self-adapting genetic algorithm. The results prove the proposed method has an advantage in terms of the objective and CPU time. Numerical experiments are also conducted to verify the effectiveness of the proposed enhancements.