Multi-objective Optimization Modeling for Resource Constrained Project Scheduling Problem

Abstract

Abstract:

Recent studies on project scheduling problem are usually considered as lacking resource constraint issue or just concentrat on makespan or resource utilization optimization. Considering the disadvantages of traditional modeling methods, such as lacking flexibility or owning solely a single optimization objective, a novel approach is presented to optimize the problem of resource-constrained multi-objective optimization in project scheduling. The objective is to minimize the makespan and cost, maximize the net present value and level the resource fluctuation as well. An initial project schedule is originally constructed based on topology sorting algorithm, which satisfies the time sequence constraint. As for those activities in conflict with each other in resource utilization, priority rule is adopted to solve the conflicts. A case study withdrawn from Patterson benchmark database is conducted to illustrate the effectiveness of this method. Particle swarm optimization algorithm is adopted to realize the optimization. During the calculation, random weight is used to make sure the randomization of particle swarm evolution, which prevents the algorithm from trapping into local optimization. Results show that, compared with the original solution, 20% makespan reduction, 11.17% cost reduction, 11.82% increase of the net present value, and 18.29% reduction of resource fluctuation are obtained based on the proposed approach. This research shows the ability of the proposed method in optimization of project scheduling considering makespan, cost, net present value and resource fluctuation as well.

Key words: network planning, multi-objective optimization, flexible resource, modeling, particle swarm optimization algorithm

Niu Jian-wei1, Qin Jie1, Ding Wen-ying1, Wen Wei1, Yu Yang1, Wang Dao-ping2. Multi-objective Optimization Modeling for Resource Constrained Project Scheduling Problem[J]. Industrial Engineering Journal .

References

［1］张永会,马力. 多项目资源管理技术研究［J］. 计算机工程与设计, 2010，31（17）：3886-3890.
Zhang Yong-hui, Ma Li. Research of technology of multi-project resource management［J］. Computer Engineering and Design, 2010，31（17）：3886-3890.
［2］谢阳,叶春明,陈君兰，等. 基于混沌粒子群的资源受限项目调度问题［J］. 工业工程, 2012，15 (3): 57-61.
Xie Yang, Ye Chun-ming, Chen Jun-lan, et al. Resource constrained project scheduling based on chaos particle swam optimization［J］. Industrial Engineering Journal, 2012，15 (3): 57-61.
［3］郭云涛,宋红艳,白思俊. 粒子群算法在具有迭代关系资源受限项目调度中的应用［J］. 工业工程, 2013，16 (5): 74-78.
Guo Yun-tao, Song Hong-yang, Bai Si-jun. Particle swarm optimization algorithm for resource constrained project scheduling problem with overlapping relationship［J］. Industrial Engineering Journal, 2013，16 (5): 74-78.
［4］王健,刘尔烈,骆刚. 工程项目管理中工期-成本-质量综合均衡优化［J］. 系统工程学报, 2004，19（02）：148-153.
Wang Jian, Liu Er-lie, Luo Gang. Analysis of time-cost-quality tradeoff optimization in construction project management［J］. Journal of Systems Engineering, 2004，19（02）：148-153.［5］祁薇熹,李彬. 多目标演化算法的进展研究［J］. 计算机与数字工程, 2008，36（05）：16-18.
Qi Wei-xi, Li Bin. Introduction of research on multi-objective evolutionary algorithms［J］. Computer & Digital Engineering, 2008，36（05）：16-18.
［6］赵瑞,刘晓君,申金山.建设项目多目标优化方法研究［J］. 西安建筑科技大学学报:自然科学版, 2008，40（06）:858-862.
Zhao Rui, Liu Xixo-jun, Shen Jin-shan. Study on multi-objective optimization approach of construction project［J］. Journal of Xian University of Architecture & Techhdogy: Natural Science Edition, 2008，40（06）：858-862.
［7］杨林根,李红梅. 演化算法求解约束多目标优化问题［J］. 计算机工程与设计, 2008，29（24）：6243-6245.
Yang Lin-gen, Li Hong-mei. Evolution algorithm for constrained multi-objective optimization problem［J］. Computer Engineering and Design, 2008，29（24）：6243-6245.
［8］Szmerekovsky J G, Venkateshan P. An integer programming formulation for the project scheduling problem with irregular time-cost tradeoffs［J］. Computers & Operations Research, 2012, 39(7): 1402-1410.
［9］Tavana M, Abtahi A, Khalili-Damghani K. A new multi-objective multi-mode model for solving preemptive time-cost-quality trade-off project scheduling problems［J］. Expert Systems with Applications, 2014, 41(4): 1830-1846.〖ZK)〗
［10］Moukrim A, Quilliot A, Toussaint H. An effective branch-and-price algorithm for the Preemptive Resource Constrained Project Scheduling Problem based on minimal Interval Order Enumeration［J］. European Journal of Operational Research, 2015, 244(2): 360-368.
［11］Agarwal A, Colak S, Erenguc S. A neurogenetic approach for the resource-constrained project scheduling problem［J］. Computers & Operations Research, 2011, 38 (1): 44-50.
［12］Crawford B, Soto R, Johnson F, Monfroy E, Paredes F. A Max-Min Ant System algorithm to solve the Software Project Scheduling Problem［J］. Expert Systems with Applications, 2014, 41(15): 6634-6645.
［13］Lova A, Tormos P, Cervantes M, Barber F. An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes［J］. International Journal of Production Economics, 2009, 117 (2): 302-316.
［14］Ziarati K, Akbari R, Zeighami V. On the performance of bee algorithms for resource-constrained project scheduling problem［J］. Applied Soft Computing, 2011, 11 (4):3720-3733.［15］Elmaghraby S E, Herroelen W S. The scheduling of activities to maximize the net present value of projects［J］. European Journal of Operational Research,1990,49（1）：35-59.［16］Vanhoucke M, Demeulemeester E L, Herroelen W. On maximizing the net present value of a project under renewable resource constraints［J］. Management Science, 2001, 47（8）：1113-1121.
［17］Crawford B, Soto R, Monfroy E, et al. Parameter tuning of a choice-function based hyperheuristic using Particle Swarm Optimization［J］. Expert Systems with Applications, 2013, 40 (5): 1690-1695.
［18］Jarboui B, Damak N, Siarry P, Rebai A. A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems［J］. Applied Mathematics and Computation, 2008, 195 (1): 299-308.
［19］刘衍民,牛奔,赵庆祯. 求解约束优化问题的多目标粒子群算法［J］. 计算机应用研究, 2011，28（3）：851-853.
Liu Yan-min, Niu Ben, Zhao Qing-zhen. Multi-objective particle swarm optimizer for solving constraint optimization problems［J］. Application Research of Computers, 2011，28（3）：851-853.
［20］徐刚,瞿金平. 一种用于多目标优化的混合粒子群优化算法［J］. 计算机工程与应用, 2008，44（33）：18-21.
Xu Gang, Qu Jin-ping. Hybrid particle swarm optimization algorithm for multi-objective optimization［J］. Computer Engineering and Applications, 2008，44（33）：18-21.
［21］李纬,张兴华. 一种改进的基于Pareto解的多目标粒子群算法［J］. 计算机仿真, 2010，27（5）：96-99.
Li Wei, Zhang Xing-hua. An Improved Multi-objective Particle Swarm Optimization Algorithm Based on Pareto［J］. Computer Simulation, 2010，27（05）：96-99.
［22］褚春超. 工程项目进度管理方法与应用研究［D］. 天津：天津大学，2007.
Chu Chun-chao. Study of project scheduling management methods with application［D］. Tianjin: University of Tianjin, 2007.

[1]	LIU Xuehong, ZHANG Tao, PENG Zhao, WANG Lei. Batch Scheduling of Parallel Machines with Different Capacity for Sterilization Process in Medical Equipment Enterprises [J]. Industrial Engineering Journal, 2021, 24(1): 82-89.
[2]	HOU Yan, HUANG Kanghuan, ZHANG Yixian, WU Naiqi. A Multi-objective Scheduling Optimization for Crude Oil Operations [J]. Industrial Engineering Journal, 2020, 23(4): 131-139.
[3]	CHEN Jihkuang. Application of Combining Interpretative Structure Model and Analytic Network Process with FMEA [J]. Industrial Engineering Journal, 2020, 23(4): 154-158.
[4]	XU Yan, LAI Chaoan. A Strategic Analysis of Service Leasing Based on Multi-objective Non-cooperative Game in Cloud Manufacturing [J]. Industrial Engineering Journal, 2020, 23(1): 112-118,133.
[5]	DAI Anshu, WEI Guanzhou, HE Shuguang, HE Zhen. Two Dimensional Warranty Management Review and Research Prospect [J]. Industrial Engineering Journal, 2019, 22(6): 96-102,117.
[6]	CHEN Min, LI Zhantao, CHEN Qingxin, PENG Chengfeng. AGV Scheduling Algorithm of Intelligent Workshop Considering Limited Logistics Transportation Capacity [J]. Industrial Engineering Journal , 2019, 22(4): 49-57.
[7]	LI Qi, MIAO Rui, ZHANG Jie, JIANG Zhibin, FU Yuan. A Multi-objective Optimization Design of Service Portfolio for Electric Vehicle Lease [J]. Industrial Engineering Journal , 2019, 22(4): 101-108.
[8]	ZHENG Feifeng, MEI Qihuang, LIU Ming, ZHANG Xiaoning. A Research on Bi-Objective Exact Algorithm of Stowage Planning for Multiple Container Ports [J]. Industrial Engineering Journal , 2018, 21(6): 1-6.
[9]	XIE Jieming, MAO Ning, CHEN Qingxin. Modeling Robotic Cell and Analyzing the Influences of Stochastic Factors [J]. Industrial Engineering Journal , 2017, 20(6): 84-89,95.
[10]	HAO Zhigang. A Method of Surgical Scheduling:Improving the Satisfaction of Doctors and Patients while Cutting Operation Costs [J]. Industrial Engineering Journal , 2017, 20(4): 49-56,71.
[11]	SHEN Xiaobing, YANG Baohua. A Fuzzy Multi-objective Optimization of Post-earthquake Emergency Logistics Systems Based on Bi-level Programming and Mixed Transportation [J]. Industrial Engineering Journal , 2017, 20(3): 113-117.
[12]	WANG Bangjun1，2, LI Runqi2, DAI Wei3, SHE Yuanguan1. Product Manufacturing Process Quality Variation Source Interpretative Structural Modeling and its Application [J]. Industrial Engineering Journal , 2016, 19(5): 146-152.
[13]	WU Xiaodan1, LIU Dan1, SUN Yuanyuan2, YUE Dianmin1, ZUO Xiangjun1. An Aggregation Error Analysis for Activitybased Costing under the Consideration of Resource Consumption Pattern [J]. Industrial Engineering Journal , 2016, 19(4): 48-54.
[14]	He Meng-ying, Xu Mei, Zhang Ning-bo, Yan Fu. An Analysis of Passenger Car Transportation Problems Based on Heuristic Algorithm [J]. Industrial Engineering Journal , 2015, 18(5): 141-147.
[15]	Zhu Xing-guang1，Yang Gong-zhen2. Multi-stage Production Plan Modeling and Management Information System Design of Electric Resistant Welding Steel Pipe Enterprises [J]. Industrial Engineering Journal , 2015, 18(2): 133-141.