计算机科学

计算机科学 ›› 2022, Vol. 49 ›› Issue (12): 274-282.doi: 10.11896/jsjkx.211100276

• 人工智能 • 上一篇    下一篇

求解资源受限项目调度问题的分支定价算法

张宇哲1, 董兴业1, 周正2   

  1. 1 北京交通大学计算机与信息技术学院交通数据分析与挖掘北京市重点实验室 北京100044
    2 中国船舶工业系统工程研究院 北京100094
  • 收稿日期:2021-11-29 修回日期:2022-04-30 发布日期:2022-12-14
  • 通讯作者: 董兴业(xydong@bjtu.edu.cn)
  • 作者简介:(19120448@bjtu.edu.cn)

Branch & Price Algorithm for Resource-constrained Project Scheduling Problem

ZHANG Yu-zhe1, DONG Xing-ye1, ZHOU Zheng2   

  1. 1 Beijing Key Lab of Traffic Data Aanlysis and Mining,School of Computer and IT,Beijing Jiaotong University,Beijing 100044,China
    2 Systems Engineering Research Institute,Beijing 100094,China
  • Received:2021-11-29 Revised:2022-04-30 Published:2022-12-14
  • About author:ZHANG Yu-zhe,born in 1997,post- graduate.Her main research interests include RCPSP optimization,traditional methods and deep learning methods.DONG Xing-ye,born in 1974,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include scheduling theory,operations research and intelligent optimization algorithms.

PDF (PC)

651

摘要： 资源受限项目调度问题是最具代表性的一类项目调度问题,是很多实际调度问题的抽象表示,属于NP-hard问题,对于大规模问题难以求得全局最优解。文中提出了问题的整数规划模型,通过将模型分解为约束主问题和子问题设计了求解线性松弛模型的列生成方法,然后通过分支定价寻找问题的整数解。在求解过程中引入松弛变量解决模型伪不可解的问题,设计了剪支策略和分支策略,并根据不同情况提出了两种缩小解空间的方法。在PSPLIB基准数据集上,对于有30个工序的问题,所提算法在10 m内能够求出480个问题中的301个问题的当前最优解;对于有60个工序的问题,在20 m内能够求出480个问题中的269个问题的当前最优解;对于有90个工序的问题,在30 m内能够求出480个问题中的263个问题的当前最优解。同时,算法使用缩小解空间策略后,超时算例的个数明显减少,优化初始解的性能得到明显提升。以上实验结果表明,所提算法具有较好的求解能力。

关键词: 资源受限项目调度, 整数规划, 列生成, 分支定价, 伪不可解

Abstract: Resource-constrained project scheduling problem(RCPSP) is the most representative scheduling problem,which is an abstract representation of many practical scheduling problems.It belongs to the NP-hard problem and is difficult to obtain the global optimal solution for large-scale problems.In this paper,an integer programming model is proposed.By decomposing the model into a constrained master problem and some subproblems,a column generation method is designed for the solving of the linear relaxation model,and then the integer solution of the problem is found through branch & price.In the process of solving,relaxation variables are introduced to solve the pseudo infeasibility of the model.Furthermore,pruning strategy,branch strategy,and two methods for reducing the solution space according to different situations are designed.On the PSPLIB data set,for the problems with 30 processes,the current optimal solutions can be obtained in 10 minutes for 301 out of 480 instances.For the problems with 60 processes,the current optimal solutions can be obtained in 20 minutes for 269 out of 480 instances.For the problem with 90 processes,the current optimal solutions can be obtained in 30 minutes for 263 out of 480 instances.At the same time,by using the strategies of reducing the solution space,the number of timeout instances decreases significantly,and the performance of the optimized initial solution is significantly improved.Experimental results show that the proposed algorithm is effective.

Key words: RCPSP, Integer programming, Column generation, Branch & Price, Pseudo infeasibility

中图分类号: 

  • TP181
[1]BLAZEWICZ J,LENSTRA J K,RINNOOY KAN A H G.Scheduling Subject to Resource Constraints:Classification and Complexity[J].Discrete Applied Mathematics,1983,5(1):11-24.
[2]HARTMANN S,BRISKORN D.An Updated Survey of Va-riants and Extensions of the Resource-Constrained Project Sche-duling Problem[J].European Journal of Operational Research,2022,297(1):1-14.
[3]HE Z W,JIA T,XU Y.A Survey of Heuristics for Resource-Constrained Project Scheduling Problems[J].Operations Research and Management Science,2007(3):78-84.
[4]KOLISCH R,HARTMANN S.Heuristic Algorithms for theResource-Constrained Project Scheduling Problem:Classification and Computational Analysis[M]//Project Scheduling:Recent Models,Algorithms and Applications.Boston,MA:Springer US,1998:148-178.
[5]BROWNING T R,YASSINE A A.Resource-Constrained Multi-Project Scheduling:Priority Rule Performance Revisited[J].International Journal of Production Economics,2010,126(2):212-228.
[6]TÜRKAKN O H,ARDITI D,MANISAL E.Comparison ofHeuristic Priority Rules in the Solution of the Resource-Constrained Project Scheduling Problem [J].Sustainability,2021,13(7):1-16.
[7]TOFIGHIAN A A,NADERI B.Modeling and Solving the Project Selection and Scheduling[J].Computers & Industrial Engineering,2015,83(C):30-38.
[8]SAVITRI N A,PUJAWAN I N,SANTOSA B.Resource-Constrained Project Scheduling with Ant Colony Optimization Algorithm[J].Journal of Civil Engineering,2020,35(2):34-38.
[9]JIA L,LIU Y S,SHI Y,et al.Solving Resource-Constrained Project Scheduling Problem via Genetic Algorithm[J].Journal of Computing in Civil Engineering,2020,34(2):04019055.
[10]BOCTOR F F.Resource-Constrained Project Scheduling by Si-mulated Annealing[J].International Journal of Production Research,1996,34(8):2335-2351.
[11]PAN N H,HSIANG T C,CHEN W T.Using Hybrid Simulated Annealing Algorithm in Resource Constrained Project Scheduling Problem[J].International Journal of Organizational Innovation,2020,12(3):25-46.
[12]OMER A.Tabu Search and An Exact Algorithm for the Solutions of Resource-constrained Project Scheduling Problems[J].International Journal of Computational Intelligence Systems,2011,4(2):255-267.
[13]PELLERIN R,PERRIER N,BERTHAUT F.A Survey of Hybrid Metaheuristics for the Resource-Constrained Project Sche-duling Problem[J].European Journal of Operational Research,2020,280(2):395-416.
[14]GOLAB A,GOOYA E,FALOU A,et al.Review of Conven-tional Metaheuristic Techniques for Resource-Constrained Project Scheduling Problem[J].Journal of Project Management,2022,7(2):95-110.
[15]PATTERSON J H.A Comparison of Exact Approaches for Solving The Multiple Constrained Resource Project Scheduling Problem[J].Management Science,1984,30(7):854-867.
[16]ROSTAMI M,MORADINEZHAD D,SOUFIPOUR A.Im-proved and Competitive Algorithms for Large Scale Multiple Resource-Constrained Project-Scheduling Problems [J].KSCE Journal of Civil Engineering,2014,18(5):1261-1269.
[17]MINGOZZI A,MANIEZZO V,RICCIARDELLI S,et al.AnExact Algorithm for The Resource-Constrained Project Scheduling Problem Based on A New Mathematical Formulation[J].Management Science.1998,44(5):714-729.
[18]BRUCKER P,KNUST S.A Linear Programming and Con-straint Propagation-Based Lower Bound for The RCPSP[J].European Journal of Operational Research,2000,127(2):355-362.
[19]DAMAY J,QUILLIOT A,SANLAVILLE E.Linear Programming Based Algorithms for Preemptive and Non-Preemptive RCPSP [J].European Journal of Operational Research,2007,182(3):1012-1022.
[20]WANG Q,LIU C C,ZHENG L.A Column-Generation-Based Algorithm for A Resource-Constrained Project Scheduling Problem with A Fractional Shared Resource[J].Engineering Optimization,2020,52(5):798-816.
[1] 李晓东, 於志勇, 黄昉菀, 朱伟平, 涂淳钰, 郑伟楠.
面向河道环境监测的群智感知参与者选择策略
Participant Selection Strategies Based on Crowd Sensing for River Environmental Monitoring
计算机科学, 2022, 49(5): 371-379. https://doi.org/10.11896/jsjkx.210200005
[2] 张红颖, 申荣苗, 罗谦.
基于混合整数规划的停机位优化调度研究
Study on Optimal Scheduling of Gate Based on Mixed Integer Programming
计算机科学, 2020, 47(8): 278-283. https://doi.org/10.11896/jsjkx.190400154
[3] 周欣悦, 钱丽萍, 黄玉蘋, 吴远.
一种基于蚁群的电动汽车充电调度优化方法
Optimization Method of Electric Vehicles Charging Scheduling Based on Ant Colony
计算机科学, 2020, 47(11): 280-285. https://doi.org/10.11896/jsjkx.190700129
[4] 郑斐峰, 蒋娟, 梅启煌.
最小化集装箱运输成本的配载优化
Study on Stowage Optimization in Minimum Container Transportation Cost
计算机科学, 2019, 46(6): 239-245. https://doi.org/10.11896/j.issn.1002-137X.2019.06.036
[5] 王璐,张小宁,孙智慧,吴辉.
精确求解进港飞机调度双目标优化问题的epsilon约束算法
Exact Epsilon-constraint Algorithm for Bi-objective Optimization of Flight Arrival Scheduling Problem
计算机科学, 2017, 44(Z11): 580-582. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.124
[6] 杨蓓,周兰江,余正涛,刘丽佳.
半监督学习的老挝语词性标注方法研究
Research on Semi-supervised Learning Based Approach for Lao Part of Speech Tagging
计算机科学, 2016, 43(9): 103-106. https://doi.org/10.11896/j.issn.1002-137X.2016.09.019
[7] 李华,孙涛,王显荣,邢熠,李颖杰,夏兴行.
基于CPN对系统的并发行为进行测试
Testing Concurrent Behavior of System Based on CPN
计算机科学, 2016, 43(1): 218-225. https://doi.org/10.11896/j.issn.1002-137X.2016.01.048
[8] 范菁,沈杰,熊丽荣.
混合云环境中数据敏感工作流调度
Scheduling Data Sensitive Workflow in Hybrid Cloud
计算机科学, 2015, 42(Z11): 400-405.
[9] .
支持向量逐步回归机及其改进算法研究

计算机科学, 2007, 34(11): 180-182.
[10] 刘芳 刘民 吴澄.
一种遗传进化规划

计算机科学, 2005, 32(12): 24-26.
[11] 许贵平 刘云生.
实时事务调度及静态可调度性分析

计算机科学, 2005, 32(10): 110-113.
[12] 白恩健 王静 肖国镇.
[a，b]-自缩减生成器

计算机科学, 2004, 31(5): 107-109.
[13] 王洪国 陈火旺 马绍汉.
0—1整数规划在科技项目管理中的应用

计算机科学, 2003, 30(7): 77-79.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发