Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (12): 274-282.doi: 10.11896/jsjkx.211100276

• Artificial Intelligence • Previous Articles     Next Articles

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)

398

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

CLC Number: 

  • 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] LI Xiao-dong, YU Zhi-yong, HUANG Fang-wan, ZHU Wei-ping, TU Chun-yu, ZHENG Wei-nan. Participant Selection Strategies Based on Crowd Sensing for River Environmental Monitoring [J]. Computer Science, 2022, 49(5): 371-379.
[2] ZHANG Hong-ying, SHEN Rong-miao, LUO Qian. Study on Optimal Scheduling of Gate Based on Mixed Integer Programming [J]. Computer Science, 2020, 47(8): 278-283.
[3] ZHOU Xin-yue, QIAN Li-ping, HUANG Yu-pin, WU Yuan. Optimization Method of Electric Vehicles Charging Scheduling Based on Ant Colony [J]. Computer Science, 2020, 47(11): 280-285.
[4] ZHENG Fei-feng, JIANG Juan, MEI Qi-huang. Study on Stowage Optimization in Minimum Container Transportation Cost [J]. Computer Science, 2019, 46(6): 239-245.
[5] LIU Wei, ZHAO Yu and CHEN Rui. Zero-One Integer Programming Based Optimization Model and Two-phase Resource Optimization Algorithm for Wireless Ad hoc Networks [J]. Computer Science, 2017, 44(1): 103-108.
[6] YANG Bei, ZHOU Lan-jiang, YU Zheng-tao and LIU Li-jia. Research on Semi-supervised Learning Based Approach for Lao Part of Speech Tagging [J]. Computer Science, 2016, 43(9): 103-106.
[7] CHEN Xiang,GU Wei-jiang,XU Hui,GU Qing and CHEN Dao-xu. Regression Testing Selection Techniques:A State-of-the-art Review [J]. Computer Science, 2013, 40(10): 1-9.
[8] . [J]. Computer Science, 2007, 34(11): 180-182.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.