项目拆分与资源投入调度问题的集成优化

doi:10.16183/j.cnki.jsjtu.2018.07.006

摘要/Abstract

摘要： 基于一类实际生产决策需求，提出了依赖于项目拆分的资源投入调度问题.在分析项目拆分对资源投入影响的基础上，以资源投入最小化为目标，建立了项目拆分与资源投入调度问题的集成优化模型.结合项目拆分和资源投入调度的特点，提出了包含项目拆分优化和资源投入调度优化的两阶段集成优化算法.项目拆分阶段分析可行的拆分条件，采用项目初始拆分及局部调整的方法，可以快速获得较优的项目拆分方案.资源投入调度阶段以采用作业优先级和资源能力双列表编码的遗传算法为搜索框架，充分利用迭代过程中的信息，设计一种基于概率分布的资源能力选择方法来改进资源列表，使资源能力列表加速向最优解收敛.应用PSPLIB标准算例进行数据实验，结果证明了该算法的有效性和可靠性.

关键词: 项目拆分, 资源投入, 集成优化, 遗传算法

Abstract: Based on a class of actual production decision requirements, a resource investment scheduling problem that depends on project splitting is proposed. Based on the analysis of project splitting's impact on resource investment, the integrated optimization model of project splitting and resource investment scheduling problem is established with the aim of minimizing resource investment. A two-stage integrated optimization algorithm is proposed including project splitting optimization and resource investment scheduling optimization. The feasibility of split conditions is studied in the project splitting stage. Using an initial split and a local adjustment method, a project split program can be quickly obtained. Genetic algorithm with job priority and resource capacity dual list are used for the search frame in the resource investment scheduling stage. With full use of the information in the iterative process, a resource allocation method based on probability distribution is designed to accelerate the algorithm convergence. Results from numerical experiments using PSPLIB standard library prove the effectiveness and reliability of the algorithm.

Key words: project splitting, resource investment, integrated optimization, genetic algorithm

中图分类号:

TP 29

宗保氏，陆志强. 项目拆分与资源投入调度问题的集成优化[J]. 上海交通大学学报（自然版）, 2018, 52(7): 793-800.

ZONG Baoshi,LU Zhiqiang. Integrated Optimization of Project Splitting and Resource Investment Project Scheduling[J]. Journal of Shanghai Jiaotong University, 2018, 52(7): 793-800.

参考文献

［1］MASTOR A A. An experimental investigation and comparative evaluation of production line balancing techniques［J］. Management Science, 1970, 16(11): 728-746. ［2］MOHRING R H. Minimizing costs of resource requirements in project networks subject to a fixed completion time［J］. Operations Research, 1984, 32(1): 89-120. ［3］DEMEULEMEESTER E. Minimizing resource avai-lability costs in time-limited project networks［J］. Management Science, 1995, 41(10): 1590-1598. ［4］RANGASWAMY B. Multiple resource planning and allocation in resource-constrained project networks［D］. Colorado: University of Colorado, 1999. ［5］DREXL A, KIMMS A. Optimization guided lower and upper bounds for the resource investment problem［J］. Journal of the Operational Research Society, 2001, 52(3): 340-351. ［6］RODRIGUES S B, YAMASHITA D S. An exact algorithm for minimizing resource availability costs in project scheduling［J］. European Journal of Ope-rational Research, 2010, 206(3): 562-568. ［7］KELLEY J E. The critical-path method: Resources planning and scheduling［C］∥Industrial Scheduling. New Jersey: Prentice-Hall, 1963: 347-365. ［8］YAMASHITA D S, ARMENTANO V A, LAGUNA M. Scatter search for project scheduling with resource availability cost［J］. European Journal of Operational Research, 2006, 169(2): 623-637. ［9］SHADROKH S, KIANFAR F. A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty［J］. European Journal of Operational Research, 2007, 181(1): 86-101. ［10］RANJBAR M, KIANFAR F, SHADROKH S. Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm［J］. Applied Mathematics and Computation, 2008, 196(2): 879-888. ［11］PETEGHEM V V, VANHOUCKE M. An artificial immune system algorithm for the resource availability cost problem［J］. Flexible Services & Manufacturing Journal, 2013, 25(1/2): 122-144. ［12］陆志强, 杨超. 基于项目网络拆分决策的多项目协同调度问题建模［J］. 上海交通大学学报, 2017, 51(2): 193-201. LU Zhiqiang, YANG Chao. Modeling of resource constrained multi-project scheduling problem based on project splitting［J］. Journal of Shanghai Jiao Tong University, 2017, 51(2): 193-201.

[1]	闫青, 鲁建厦, 江伟光, 邵益平, 汤洪涛, 李英德. 考虑双端口布局的紧致化仓储系统堆垛机路径优化[J]. 上海交通大学学报, 2022, 56(7): 858-867.
[2]	周天颜, 冯小恩, 范云锋, 董诗音, 李玉庆, 金慧中. 避免防空火力过剩的地面兵力防御部署优化模型[J]. 空天防御, 2022, 5(4): 19-23.
[3]	王箫剑, 洪君, 陈晶华, 李鸿光. 基于参数化建模和响应面优化的箱体减重研究[J]. 空天防御, 2022, 5(4): 60-66.
[4]	王卓鑫, 赵海涛, 谢月涵, 任翰韬, 袁明清, 张博明, 陈吉安. 反向传播神经网络联合遗传算法对复合材料模量的预测[J]. 上海交通大学学报, 2022, 56(10): 1341-1348.
[5]	陶海红, 闫莹菲. 一种基于GA-CNN的网络化雷达节点遴选算法[J]. 空天防御, 2022, 5(1): 1-5.
[6]	周宇泰, 徐岳, 李宇, 蒋国韬. 基于遗传算法的干扰态势下三维雷达网优化布站方法[J]. 空天防御, 2022, 5(1): 52-59.
[7]	李翠明, 王宁, 张晨. 基于改进遗传算法的光伏板清洁分级任务规划[J]. 上海交通大学学报, 2021, 55(9): 1169-1174.
[8]	顾一凡, 赵文龙, 唐善军, 杨擎宇, 郑鑫. 分布式主/被动成像探测系统目标空间协同定位方法研究[J]. 空天防御, 2021, 4(4): 119-126.
[9]	卓鹏程, 严瑾, 郑美妹, 夏唐斌, 奚立峰. 面向滚动轴承全生命周期故障诊断的GA-OIHF Elman神经网络算法[J]. 上海交通大学学报, 2021, 55(10): 1255-1262.
[10]	王金凤, 陈璐, 杨雯慧. 考虑设备可用性约束的单机调度问题[J]. 上海交通大学学报, 2021, 55(1): 103-110.
[11]	牛志华, 苑璨, 孔得宇. 计算周期序列k-错线性复杂度的混合遗传算法[J]. 上海交通大学学报, 2020, 54(6): 599-606.
[12]	康俊涛, 张亚州, 秦世强. 基于一种混合智能算法的有限元模型修正多解问题[J]. 上海交通大学学报, 2020, 54(6): 652-660.
[13]	戴少怀, 王磊, 李旻, 余科, 罗晨. 基于遗传算法的SVM自适应干扰样式选择[J]. 空天防御, 2020, 3(2): 59-64.
[14]	姚来鹏, 侯保林, 刘曦. 采用摩擦补偿的弹药传输机械臂自适应终端滑模控制[J]. 上海交通大学学报, 2020, 54(2): 144-151.
[15]	高云凯, 马超, 刘哲, 田林雳. 基于NSGA-III的白车身焊装生产平台的离散拓扑优化[J]. 上海交通大学学报, 2020, 54(12): 1324-1334.