基于整数规划强对偶求解一类局域性资源受限项目调度问题

doi:10.16381/j.cnki.issn1003-207x.2020.0272

摘要/Abstract

摘要： 资源受限项目调度问题(简称RCPSP)是最具代表性的项目调度问题之一，调度过程可理解为，将受资源约束的平行工序调整为顺序工序。本文针对实际中广泛存在的资源局域、而非全局受限的情况，研究局域性RCPSP，并重点考虑一类问题：项目某环节的一系列平行工序，可用资源量只有一半，各资源可重复利用且具有相应多功能，但最多能承担2个工序，需将这些工序两两排列成对，实现项目工期最短。本文首先探索问题“局域性”特征，量化局域调度对项目工期的影响；基于此，构建只涵盖“局域调度工序”的0-1规划模型；再者，发展整数规划强对偶理论，结合Dangzig-Wolfe分解等方法，提出多项式时间的精确算法；最后通过算例测试，验证算法优势，例如，计算大规模算例的最优解，运用该算法比常规精确方法可快数万倍以上。

关键词: 资源受限项目调度；整数规划强对偶；多项式时间精确算法；Dangzig-Wolfe分解

Abstract: Resource constraints are often broadly impacting, unavoidable impediments in project execution procedures. A number of recent, topical project management issues, such as the resource-constrainedproject scheduling problem (RCPSP), have their roots in the resource constraint problem. It is NP-hard in the strong sense. Current research on the RCPSP mainly focuses on the global problemin which all activities are constrained by resource constraints during the whole project process. Considering practical projects requiring numerous types of resources, the “resource constrained” designation may be for limited types of resources or during local project processes. The local “resource-constrained” designation may constrain activities in a part of the projectsuch that only a portion of activities need arrangement under resource restriction.The above representation denotes the local RCPSP.In this paper, a typical sub-problem of the local RCPSP is studied, which is generated by adding some special assumptions to the general local RCPSP.

Key words: resource-constrained project scheduling; strong duality of integer programming; exact polynomial time algorithm; Dangzig-Wolfe decomposition

中图分类号:

O221

苏志雄, 魏汉英, 张静文, 乞建勋. 基于整数规划强对偶求解一类局域性资源受限项目调度问题[J]. 中国管理科学, 2022, 30(11): 159-169.

SU Zhi-xiong, WEI Han-ying, ZHANG Jing-wen, QI Jian-xun. Optimization of a Type of Local Resource-Constrained Project Scheduling Problem Based on the Strong Duality Theory of Integer Programming[J]. Chinese Journal of Management Science, 2022, 30(11): 159-169.

参考文献

［1］方晨, 王凌. 资源约束项目调度研究综述［J］. 控制与决策, 2010, 25(5): 641-650, 656.Fang Chen, Wang Ling. Survey on resource-constrained project scheduling［J］. Control and Decision, 2010, 25(5): 641-650,656.
［2］ Demeulemeester E L. Project scheduling: A research handbook［M］. New York/Boston/Dordrecht/London/Moscow: Kluwer Academic Publishers, 2013.
［3］石彪, 池宏, 祁明亮, 等. 资源约束下的应急预案重构方法研究［J］. 中国管理科学, 2017, 25(1): 117-128.Shi Biao, Chi Hong, Qi Mingliang, et al. A study on emergency plan reconstruction with resource constraint［J］. Chinese Journal of Management Science, 2017, 25(1): 117-128.
［4］刘士新, 宋健海. 求解资源受限项目调度问题的约束规划/数学规划混合算法［J］. 控制理论与应用, 2011, 28(8): 1113-1120.Liu Shixin, Song Jianhai. Combination of constraint programming and mathematical programming for solving resources-constrained project-scheduling problems［J］.Control Theory & Applications, 2011, 28(8): 1113-1120.
［5］ Liu Changchun, Xiang Xi, Zheng Li, et al. An integrated model for multi-resource constrained scheduling problem considering multi-product and resource-sharing［J］.International Journal of Production Research, 2018, 56(19): 6491-6511.
［6］ Naber A, Kolisch R. MIP models for resource-constrained project scheduling with flexible resource profiles［J］. European Journal of Operational Research, 2015, 239(2): 335-348.
［7］张立辉, 邹鑫, 黄元生, 等. 重复性项目调度模型的时差分析［J］. 中国管理科学, 2018, 26(6):95-103.Zhang Lihui, Zou Xin, Huang Yuansheng, et al. Float analysis in repetitive scheduling model［J］. Chinese Journal of Management Science, 2018, 26(6):95-103.
［8］ Artigues C. On the strength of time-indexed formulations for the resource-constrained project scheduling problem［J］.Operations Research Letters, 2017, 45(2): 154-159.
［9］ Sheng Buyun, Wang Hui, Xiao Zheng, et al. A novel heuristic algorithm with activity back-shift response model for resource-constrained project scheduling problem［J］. Soft Computing, 2019, 23(17): 7805-7819.
［10］ Advar M, Fang Shu-cherng. Convex analysis and duality over discrete domains［J］. Journal of the Operations Research Society of China, 2018, 6(2): 189-247.
［11］ Kannan R, Barton P I. Convergence-order analysis of branch-and-bound algorithms for constrained problems［J］.Journal of Global Optimization, 2018, 71(4): 753-813.
［12］ Davari M, Demeulemeester E. A novel branch-and-bound algorithm for the chance-constrained resource- constrained project scheduling problem［J］. International Journal of Production Research, 2018, 57(4):1265-1282.
［13］ Lombardi M, Milano M. A min-flow algorithm for minimal critical set detection in resource constrained project scheduling［J］.Artificial Intelligence, 2012, 182-183: 58-67.
［14］ Nemati-Lafmejani R, Davari-Ardakani H, Najafzad H. Multi-mode resource constrained project scheduling and contractor selection: Mathematical formulation and metaheuristic algorithms［J］. Applied Soft Computing, 2019, 81: 105533.
［15］何正文, 刘人境, 胡信布. 基于合同双方交互作用的项目调度优化［J］. 管理科学学报, 2014, 17(8):48-59.He Zhengwen, Liu Renjing, Hu Xinbu.Project scheduling optimization based on interaction between two partiesof contracts［J］. Journal of Management Sciences in China,2014, 17(8):48-59.
［16］ Servranckx T, Vanhoucke M. A tabu search procedure for the resource-constrained project scheduling problem with alternative subgraphs［J］. European Journal of Operational Research, 2019, 273(3): 841-860.
［17］于静, 徐哲, 谢芳. 活动重叠模式与资源约束下的项目调度优化［J］. 管理科学学报, 2017, 20(9): 36-45.Yu Jing, Xu Zhe, Xie Fang. Project scheduling optimization with overlapping modes and resource constraints［J］.Journal of Management Sciences in China, 2017, 20(9): 36-45.
［18］刘东宁, 徐哲, 李飞飞. 基于合作博弈协商机制的分布式资源受限多项目调度［J］. 系统工程理论与实践, 2019, 39(6): 1507-1516.Liu Dongning, Xu Zhe, Li Feifei. Distributed resource constrained multi-project scheduling with cooperative-game based negotiation mechanism［J］. Systems Engineering——Theory & Practice, 2019,39(6): 1507-1516.
［19］王海鑫, 王祖和, 温国锋, 等. 自适应粒子群算法求解资源受限多项目调度问题［J］. 管理工程学报, 2017, 31(4): 220-225.Wang Haixin, Wang Zuhe, Wen Guofeng, et al. Resource constrained multi-project scheduling based on adaptive particleswarm optimization algorithm［J］. Journal of Industrial Engineering/Engineering Management, 2017,31(4): 220-225.
［20］安晓亭, 张梓琪. 基于改进蚁群优化的多目标资源受限项目调度方法［J］. 系统工程理论与实践, 2019, 39(2):509-519.An Xiaoting, Zhang Ziqi. Multi-objective resource constrained project scheduling problem based on improved ant colony optimization［J］. Systems Engineering—Theory & Practice, 2019, 39(2):509-519.
［21］ Chakrabortty R K, Abbasi A, Ryan M J. Multi-mode resource-constrained project scheduling using modified variable neighborhood search heuristic［J］. International Transactions in Operational Research, 2020, 27(1): 138-167.
［22］ Giran O, Temur R, Bekdas G. Resource constrained project scheduling by harmony search algorithm［J］. KSCE Journal of Civil Engineering, 2017, 21(2): 479-487.
［23］ Christodoulou S E. Entropy-based heuristic for resource-constrained project scheduling［J］. Journal of Computing in Civil Engineering, 2017, 31(3): 04016068.
［24］ Bibiks K, Hu Yim-fun，Li Jianping, et al. Improved discrete cuckoo search for the resource-constrained project scheduling problem［J］. Applied Soft Computing, 2018, 69: 493-503.
［25］ Haouari M, Kooli A, Néron E. Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem［J］. Computers & Operations Research, 2012, 39(5): 1187-1194.
［26］乞建勋, 张立辉, 李星梅. 网络计划管理中的机动时间特性理论及其应用［M］. 北京: 科学出版社, 2009.Qi Jianxun, Zhang Lihui, Li Xingmei. Theories and applications of time floats’ characteristicsin network planning management［M］.Beijing: Science Press, 2009.
［27］孙小玲, 李瑞. 运筹于管理科学丛书10——整数规划［M］. 北京: 科学出版社, 2010.Sun Xiaoling, Li Rui. Operational research and Management Science Series 10—Integer Programming［M］. Beijing: Science Press, 2010.
［28］ Karmarkar N. A new polynomial time algorithm for linear programming［J］. Combinatorica,1984, 4(4):373-395.

[1]	张瑶,张煜炜,李珍萍,吴玉文. 随机需求下多种应急医疗物资联合储备与分配问题研究[J]. 中国管理科学, 2024, 32(7): 129-137.
[2]	苏志雄,乞建勋,邹鑫,魏汉英,魏亚锋. 一类局域性资源受限项目调度问题的新0-1混合线性优化模型[J]. 中国管理科学, 2023, 31(11): 238-247.
[3]	胡玉真, 闵锐, 李倩倩,. 考虑区位协同的海外仓选址及运输规划研究[J]. 中国管理科学, 2023, 31(5): 249-259.
[4]	李峰, 朱平, 梁樑, 寇纲. 基于最近距离投影的DEA两阶段效率评价方法研究[J]. 中国管理科学, 2022, 30(10): 198-209.
[5]	肖和录, 王善平. 基于机会约束随机Index-DEA的投资组合效率评价[J]. 中国管理科学, 2022, 30(9): 94-104.
[6]	李珍萍, 仪明超. 随机需求下基于“自营+外包”模式的配送中心选址-配送问题研究[J]. 中国管理科学, 2022, 30(8): 143-154.
[7]	黄肖玲, 陈焕平, 高晓楠, 王丹, 刘进平, 陈继红. 需求可拆分Milk-run与 Supply-hub协同的汽车零部件入厂物流优化[J]. 中国管理科学, 2022, 30(7): 59-68.
[8]	胡玉真, 李倩倩, 江山. 跨境电商企业海外仓选址多目标优化研究[J]. 中国管理科学, 2022, 30(7): 201-209.
[9]	颜瑞, 陈立双, 朱晓宁, 田昊彤, 温雅, 张群. 考虑区域限制的卡车搭载无人机车辆路径问题研究[J]. 中国管理科学, 2022, 30(5): 144-155.
[10]	郭放, 黄志红, 黄卫来, 杨超. 考虑自取服务和门到门服务的电动汽车物流网络优化策略研究[J]. 中国管理科学, 2022, 30(2): 264-275.
[11]	李珍萍, 贾顺顺, 卜晓奇, 吴凌云, 张国维. 无人仓系统储位分配问题的优化模型与算法[J]. 中国管理科学, 2022, 30(1): 124-135.
[12]	郭放, 杨珺, 杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究[J]. 中国管理科学, 2019, 27(8): 118-128.
[13]	苏志雄, 魏汉英, 涂远芬. 资源受限下平行工序顺序对优化的0-1规划模型[J]. 中国管理科学, 2019, 27(8): 208-216.
[14]	夏晖, 王思逸, 蔡强. 多目标条件下企业碳配额分配和政府公平——基于(p,α)比例公平的视角[J]. 中国管理科学, 2019, 27(4): 48-55.
[15]	王建建, 何枫, 吴子轩, 陈丽莉. 改进区间可接受度的证券投资组合区间二次规划模型[J]. 中国管理科学, 2018, 26(9): 11-18.