面向资源约束项目调度的二阶段帝国竞争算法

doi:10.3778/j.issn.1673-9418.2208055

摘要/Abstract

摘要： 资源约束项目调度问题是一类经典的组合优化难题，有着广泛的工程应用背景。自20世纪60年代起，该问题的优化方法层出不穷，但大多数智能优化算法在该问题空间中搜索表现一般。针对这一挑战，提出了一种二阶段演化帝国竞争算法（TSE-ICA）。首先，基于由关键路径法得到的组块提取策略，提出两种分别用于种群多样性开发和高效收敛的同化算子，通过在不同阶段选择合适的同化算子实现二阶段演化框架的构建。其次，基于组块的改进革命机制包含插入和乱序两种邻域搜索策略，帝国竞争机制则通过收集不同帝国的收敛信息实现参数的自适应调整；最后，利用记忆库引导种群进化，提高算法的收敛速率。TSE-ICA的最佳参数设置由Taguchi法的实验设计方法确定。数值实验面向典型实例库PSPLIB中的3个实例集J30、J60和J120对TSE-ICA执行了性能测试，并基于两种评价标准与17种先进的元启发式算法进行性能对比。实验结果显示，TSE-ICA具有较好的优化性能和收敛效率，初步验证了所提改进机制的有效性和所提算法的问题适用性。

关键词: 资源约束项目调度问题, 帝国竞争算法, 二阶段演化框架, 同化, 关键路径法, Taguchi法, 组块, 记忆库

Abstract: The resource-constrained project scheduling problem is a classic combinatorial optimization problem with a wide range of engineering applications. Since the 1960s, many optimization algorithms have been used to solve this problem, but most intelligent optimization algorithms do not perform well in the whole problem space. Aiming at this challenge, a two-stage evolutionary imperialist competitive algorithm (TSE-ICA) is proposed. Firstly, based on the block extraction strategy obtained by the critical-path method, two assimilation operators are presented for diversification and convergence, respectively. The two-stage evolution framework of TSE-ICA is constructed by selecting appropriate assimilation operators in different stages. Then, the block-based improved revolution mechanism includes two neighborhood search strategies of insertion and out-of-order, and the empire competition mechanism realizes the adaptive adjustment of parameters for each empire by collecting the convergence information of them. Lastly, the memory is used to guide the evolution of the population and improve the convergence rate. The design of experiment technique of Taguchi method is applied to determining the optimal parameter setting for TSE-ICA. In the following numerical experiment, the TSE-ICA is implemented and tested by 3 instance sets (J30, J60 and J120) from the standard instance library of PSPLIB. Moreover, the empirical statistical data of TSE-ICA are compared with 17 advanced state-of-the-art algorithms based on two evaluation criteria. Experimental results show that the TSE-ICA has well optimization performance and convergence efficiency, which proves the effectiveness of the proposed improved mechanism and the problem applicability of the TSE-ICA preliminarily.

Key words: resource-constrained project scheduling problem, imperialist competitive algorithm, two-stage evolution framework, assimilation;critical-path method, Taguchi method, block, memory

李斌, 黄起彬. 面向资源约束项目调度的二阶段帝国竞争算法[J]. 计算机科学与探索, 2023, 17(11): 2620-2639.

LI Bin, HUANG Qibin. Resource-Constrained Project Scheduling Problems Oriented Two-Stage Imperialist Competitive Algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(11): 2620-2639.

参考文献

[1] BRUCKER P, DREXL A, M?HRING R, et al. Resource-constrained project scheduling: notation, classification, models, and methods[J]. European Journal of Operational Research, 1999, 112(1): 3-41.
[2] 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.
[3] PELLERIN R, PERRIER N, BERTHAUT F. A survey of hybrid metaheuristics for the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 2020, 280(2): 395-416.
[4] ELSAYED S, SARKER R, RAY T, et al. Consolidated optimization algorithm for resource-constrained project scheduling problems[J]. Information Sciences, 2017, 418: 346-362.
[5] WATERMEYER K, ZIMMERMANN J. A branch-and-bound procedure for the resource-constrained project scheduling problem with partially renewable resources and general temporal constraints[J]. OR Spectrum, 2020, 42(2): 427-460.
[6] KELLEY JR J E, WALKER M R. Critical-path planning and scheduling[C]//Proceedings of the 1959 Eastern Joint IRE-AIEE-ACM Computer Conference, Boston, Dec 1-3, 1959. New York: ACM, 1959: 160-173.
[7] BERTHOLD T, HEINZ S, LüBBECKE M E, et al. A constraint integer programming approach for resource-constrained project scheduling[C]//LNCS 6140: Proceedings of the 7th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Bologna, Jun 14-18, 2010. Berlin, Heidelberg: Springer, 2010: 313-317.
[8] RAHMAN H F, CHAKRABORTTY R K, RYAN M J. Memetic algorithm for solving resource constrained project scheduling problems[J]. Automation in Construction, 2020, 111: 103052.
[9] CHAKRABORTTY R K, RAHMAN H F, RYAN M J. Efficient priority rules for project scheduling under dynamic environments: a heuristic approach[J]. Computers & Industrial Engineering, 2020, 140: 106287.
[10] KOLISCH R, HARTMANN S. Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis[M]//WEGLARZ J. Project Scheduling. Berlin, Heidelberg: Springer, 1999.
[11] ALI I M, ELSAYED S M, RAY T, et al. Memetic algorithm for solving resource constrained project scheduling problems[C]//Proceedings of the 2015 IEEE Congress on Evolutionary Computation, Sendai, May 25-28, 2015. Piscataway: IEEE, 2015: 2761-2767.
[12] SLOWIK A, KWASNICKA H. Evolutionary algorithms and their applications to engineering problems[J]. Neural Computing and Applications, 2020, 32(16): 12363-12379.
[13] TANG J, LIU G, PAN Q. A review on representative swarm intelligence algorithms for solving optimization problems: applications and trends[J]. IEEE/CAA Journal of Automatica Sinica, 2021, 8(10): 1627-1643.
[14] KOLISCH R, SPRECHER A. PSPLIB—a project scheduling problem library: OR software-ORSEP operations research software exchange program[J]. European Journal of Operational Research, 1997, 96(1): 205-216.
[15] YANG W H, TARNG Y S. Design optimization of cutting parameters for turning operations based on the Taguchi method[J]. Journal of Materials Processing Technology, 1998, 84: 122-129.
[16] WOLPERT D H, MACREADY W G. No free lunch theorems for optimization[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 67-82.
[17] SALLAM K M, CHAKRABORTTY R K, RYAN M J. A reinforcement learning based multi-method approach for stochastic resource constrained project scheduling problems[J]. Expert Systems with Applications, 2021, 169: 114479.
[18] KOULINAS G, KOTSIKAS L, ANAGNOSTOPOULOS K. A particle swarm optimization based hyper-heuristic algorithm for the classic resource constrained project scheduling problem[J]. Information Sciences, 2014, 277: 680-693.
[19] CHAND S, HUYNH Q, SINGH H, et al. On the use of genetic programming to evolve priority rules for resource constrained project scheduling problems[J]. Information Sciences, 2018, 432: 146-163.
[20] MYSZKOWSKI P B, OLECH ? P, LASZCZYK M, et al. Hybrid differential evolution and greedy algorithm (DEGR) for solving multi-skill resource-constrained project scheduling problem[J]. Applied Soft Computing, 2018, 62: 1-14.
[21] TIAN J, HAO X, GEN M. A hybrid multi-objective EDA for robust resource constraint project scheduling with uncertainty[J]. Computers & Industrial Engineering, 2019, 130: 317-326.
[22] BAGHERINEJAD J, JOLAI F, ABDOLLAHNEJAD R, et al. A hybrid algorithm based on non-dominated sorting ant colony and genetic algorithms for solving multi-objective multi-mode project scheduling problems under resource constraints[J]. Management and Production Engineering Review, 2020, 11(2): 88-98.
[23] CHEN R M, WU C L, WANG C M, et al. Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB[J]. Expert Systems with Applications, 2010, 37(3): 1899-1910.
[24] 安晓亭, 张梓琪. 基于改进蚁群优化的多目标资源受限项目调度方法[J]. 系统工程理论与实践, 2019, 39(2): 509-519.
AN X T, ZHANG Z Q. Multi-objective resource constrained project scheduling problem based on improved ant colony optimization[J]. Systems Engineering—Theory & Practice, 2019, 39(2): 509-519.
[25] 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.
[26] KADRI R L, BOCTOR F F. An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: the single mode case[J]. European Journal of Operational Research, 2018, 265(2): 454-462.
[27] WANG L, FANG C. A hybrid estimation of distribution algorithm for solving the resource-constrained project schedu-ling problem[J]. Expert Systems with Applications, 2012, 39(3): 2451-2460.
[28] SALLAM K M, CHAKRABORTTY R K, RYAN M J. A two-stage multi-operator differential evolution algorithm for solving resource constrained project scheduling problems[J]. Future Generation Computer Systems, 2020, 108: 432-444.
[29] 项前, 周亚云, 吕志军. 资源约束项目的改进差分进化参数控制及双向调度算法[J]. 自动化学报, 2020, 46(2): 283-293.
XIANG Q, ZHOU Y Y, LV Z J. Improved differential evolution parameter control and bidirectional scheduling algorithm for the resource-constrained project[J]. Acta Automatica Sinica, 2020, 46(2): 283-293.
[30] DANG QUOC H, NGUYEN DOAN C. An effective hybrid algorithm based on particle swarm optimization with migration method for solving the multiskill resource-constrained project scheduling problem[J]. Applied Computational Intelligence and Soft Computing, 2022: 6230145.
[31] BOULEIMEN K, LECOCQ H. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J]. European Journal of Operational Research, 2003, 149(2): 268-281.
[32] LI K Y, WILLIS R J. An iterative scheduling technique for resource-constrained project scheduling[J]. European Journal of Operational Research, 1992, 56(3): 370-379.
[33] ATASHPAZ-GARGARI E, LUCAS C. Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition[C]//Proceedings of the 2007 IEEE Congress on Evolutionary Computation, Singapore, Sep 25-28, 2007. Piscataway: IEEE, 2007: 4661-4667.
[34] HOSSEINI S, AL KHALED A. A survey on the imperialist competitive algorithm metaheuristic: implementation in engineering domain and directions for future research[J]. Applied Soft Computing, 2014, 24: 1078-1094.
[35] 孟中祥, 肖玲斐, 马磊明, 等. 基于改进帝国竞争算法的微型燃气轮机容错控制[J]. 南京航空航天大学学报, 2020, 52(3): 485-492.
MENG Z X, XIAO L F, MA L M, et al. Fault tolerant control of micro gas turbine based on improved imperial competition algorithm[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2020, 52(3): 485-492.
[36] LI M, LEI D. An imperialist competitive algorithm with feedback for energy-efficient flexible job shop scheduling with transportation and sequence-dependent setup times[J]. Engineering Applications of Artificial Intelligence, 2021, 103: 104307.
[37] AKBARI R, ABBASI M, FAGHIHI F, et al. A novel multi-objective optimization method, imperialist competitive algorithm, for fuel loading pattern of nuclear reactors[J]. Progress in Nuclear Energy, 2018, 108: 391-397.
[38] BEHJATI S, NAHAVANDI N. A mathematical model and grouping imperialist competitive algorithm for integrated quay crane and yard truck scheduling problem with non-crossing constraint[J]. IJE Transactions A: Basics, 2019, 32(10): 1464-1479.
[39] SHOKOUHANDEH H, AHMADI KAMARPOSHTI M, ASGHARI F, et al. Distributed generation management in smart grid with the participation of electric vehicles with respect to the vehicle owners’ opinion by using the imperialist competitive algorithm[J]. Sustainability, 2022, 14(8): 4770.
[40] KOLISCH R. Serial and parallel resource-constrained project scheduling methods revisited: theory and computation[J]. European Journal of Operational Research, 1996, 90(2): 320-333.
[41] 赵新秋, 段思雨, 马学敏. 基于调节算子的多目标人工蜂群算法[J]. 系统工程学报, 2021, 36(5): 602-611.
ZHAO X Q, DUAN S Y, MA X M. Multi-objective artificial bee colony algorithm based on regulation operators[J]. Journal of Systems Engineering, 2021, 36(5): 602-611.
[42] LI M, LEI D, CAI J. Two-level imperialist competitive algorithm for energy-efficient hybrid flow shop scheduling problem with relative importance of objectives[J]. Swarm and Evolutionary Computation, 2019, 49: 34-43.
[43] 李郅琴, 杜建强, 聂斌, 等. 基于黑寡妇算法的特征选择方法研究[J]. 计算机工程与应用, 2022, 58(16): 147-156.
LI Z Q, DU J Q, NIE B, et al. Research on feature selection method based on black widow optimization algorithm[J]. Computer Engineering and Applications, 2022, 58(16): 147-156.
[44] MIRJALILI S, MIRJALILI S M, HATAMLOU A. Multi-verse optimizer: a nature-inspired algorithm for global optimization[J]. Neural Computing and Applications, 2016, 27(2): 495-513.
[45] SAAD H M H, CHAKRABORTTY R K, ELSAYED S, et al. Quantum-inspired genetic algorithm for resource-constrained project-scheduling[J]. IEEE Access, 2021, 9: 38488-38502.
[46] 李斌, 黄起彬. 面向进制转换和克隆进化的帝国竞争改进算法[J]. 计算机工程与应用, 2022, 58(5): 208-224.
LI B, HUANG Q B. Decimal-binary conversion and clonal evolution oriented improved imperialist competitive algorithm[J]. Computer Engineering and Applications, 2022, 58(5): 208-224.
[47] LI B, TANG Z B. Double-assimilation of prosperity and destruction oriented improved imperialist competitive algorithm with computational thinking[C]//Proceedings of the 2022 IEEE Congress on Evolutionary Computation, Padua, Jul 18-23, 2022. Piscataway: IEEE, 2022: 1-8.
[48] 王贵林, 李斌. 受春秋战国史实启发的帝国竞争改进算法[J]. 计算机应用, 2021, 41(2): 470-478.
WANG G L, LI B. Improved imperialist competitive algorithm inspired by historical facts of Spring and Autumn Period[J]. Journal of Computer Applications, 2021, 41(2): 470-478.
[49] 蔡延光, 王世豪, 戚远航, 等. 帝国竞争算法求解CVRP[J]. 计算机应用研究, 2021, 38(3): 782-786.
CAI Y G, WANG S H, QI Y H, et al. Imperialist competitive algorithm for solving CVRP[J]. Application Research of Computers, 2021, 38(3): 782-786.
[50] 罗金满, 刘丽媛, 刘飘, 等. 考虑源网荷储协调的主动配电网优化调度方法研究[J]. 电力系统保护与控制, 2022, 50(1): 167-173.
LUO J M, LIU L Y, LIU P, et al. An optimal scheduling method for active distribution network considering source network load storage coordination[J]. Power System Protection and Control, 2022, 50(1): 167-173.
[51] ALI I M, ELSAYED S M, RAY T, et al. A differential evolution algorithm for solving resource constrained project scheduling problems[C]//LNCS 9592: Proceedings of the 2016 Australasian Conference on Artificial Life and Computational Intelligence, Canberra, Feb 2-5, 2016. Cham: Springer, 2016: 209-220.
[52] ZIMMERMAN D W, ZUMBO B D. Relative power of the Wilcoxon test, the Friedman test, and repeated-measures ANOVA on ranks[J]. The Journal of Experimental Education, 1993, 62(1): 75-86.
[53] WANG X, HAN T, ZHAO H. An estimation of distribution algorithm with multi-leader search[J]. IEEE Access, 2020, 8: 37383-37405.
[54] VE?EK N, MERNIK M, ?REPIN?EK M. A chess rating system for evolutionary algorithms: a new method for the comparison and ranking of evolutionary algorithms[J]. Information Sciences, 2014, 277: 656-679.
[55] CHAND S, SINGH H K, RAY T. A heuristic algorithm for solving resource constrained project scheduling problems[C]//Proceedings of the 2017 IEEE Congress on Evolutionary Computation, San Sebastián, Jun 6-8, 2017. Piscataway: IEEE, 2017: 225-232.
[56] ZAMANI R. An evolutionary implicit enumeration procedure for solving the resource-constrained project scheduling problem[J]. International Transactions in Operational Research, 2017, 24(6): 1525-1547.
[57] LIU Z, XIAO L, TIAN J. An activity-list-based nested partitions algorithm for resource-constrained project scheduling[J]. International Journal of Production Research, 2016, 54(16): 4744-4758.
[58] ZHENG X, WANG L. A multi-agent optimization algorithm for resource constrained project scheduling problem[J]. Expert Systems with Applications, 2015, 42(15/16): 6039-6049.
[59] RAHMANI N, ZEIGHAMI V, AKBARI R. A study on the performance of differential search algorithm for single mode resource constrained project scheduling problem[J]. Decision Science Letters, 2015, 4(4): 537-550.
[60] FAHMY A, HASSAN T M, BASSIONI H. Improving RCPSP solutions quality with stacking justification-application with particle swarm optimization[J]. Expert Systems with Applications, 2014, 41(13): 5870-5881.
[61] NASIRI M M. A pseudo particle swarm optimization for the RCPSP[J]. The International Journal of Advanced Manufacturing Technology, 2013, 65(5): 909-918.
[62] RIVERA J C, MORENO V L F, DíAZ S F J, et al. A hybrid heuristic algorithm for solving the resource constrained project scheduling problem (RCPSP)[J]. Revista EIA, 2013 (20): 87-100.
[63] 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.
[64] CHEN R M. Particle swarm optimization with justification and designed mechanisms for resource-constrained project scheduling problem[J]. Expert Systems with Applications, 2011, 38(6): 7102-7111.