一种基于任务组合优化的项目调度机制研究

摘要/Abstract

摘要： 项目调度问题解决的是将有限的资源分配给适当的活动并达到项目工期最优的目标，它是优化项目资源配置、缩短项目工期的重要手段。调度过程中，如何在不同时段，基于有限资源，选择恰当的活动调度，是该问题解决的关键。本文基于项目工期最短的目标，从任务组合角度出发，以分支定界过程为框架，嵌套任务组合优化策略，结合启发式优先规则，设计一种新的项目调度机制。在此过程中，首先利用广度优先搜索确定待决策活动和分支时刻，然后分别基于任务组合优化策略和深度优先搜索完成树的分支优化和剪枝过程，最后通过算例及问题库PSPLIB完成实验测试，对比传统启发式调度机制，分析不同项目环境对调度的影响，验证机制的有效性。结果表明，无论是项目平均工期还是最优调度方案占比，所提出的调度机制求解结果都优于传统启发式调度机制。研究结果可以进一步指导项目管理实践，对实际项目调度提供科学决策依据。

关键词: 项目调度, 任务组合优化, 优先规则, 广度优先搜索, 深度优先搜索

Abstract: Project scheduling is intended to allocate limited resources to appropriate activities and achieve the goal of optimal project construction period. It is an important means to optimize project resource allocation and shorten project construction period. In the process of scheduling, how to choose the appropriate activity based on limited resources in different periods is the key to solution. Based on the objective of minimum project construction period, from the perspective of activity combination, this paper designs a new project scheduling mechanism with the framework of branch and bound process, nested task combination optimization strategy and heuristic priority rules. In this process, firstly, breadth-first search is used to determine the activities to be decided and the branching time, and then the branching optimization and pruning process of the tree are completed based on the activity combination optimization strategy and depth-first search respectively. Finally, the experimental test is completed through an example and PSPLIB, and the traditional heuristic scheduling mechanism is compared to analyze the impact of different project environments on the scheduling and verify the effectiveness of the mechanism. The results show that the proposed scheduling mechanism is more efficient than the traditional heuristic scheduling mechanism in solving both the average project construction period and the optimal scheduling proportion. This conclusion can further guide project management practices and provide scientific decision-making basis for actual project scheduling.

Key words: project scheduling, activity combination optimization, priority rule, breadth-first search, depth-first search

王敏, 刘国山. 一种基于任务组合优化的项目调度机制研究[J]. 管理评论, 2025, 37(3): 228-237.

Wang Min, Liu Guoshan. A Project Scheduling Mechanism Based on Activity Combination Optimization[J]. Management Review, 2025, 37(3): 228-237.

参考文献

[1] Dorndorf U., Pesch E., Phan-Huy T. A. A Branch-and-Bound Algorithm for the Resource-constrained Project Scheduling Problem[J]. Mathematical Methods of Operations Research, 2000,52（3）:413-439
[2] Blazewicz J., Lenstra J., Rinnooy K. A. Scheduling Subject to Resource Constraints: Classification and Complexity[J]. Discrete Applied Mathematics, 1983,5(1):11-24
[3] 李洪波,熊励,刘寅斌. 项目资源均衡研究综述[J]. 控制与决策, 2015,30(5):769-779 Li H. B., Xiong L., Liu Y. B. A Literature Survey of Project Resource Leveling[J]. Control and Decision, 2015,30(5):769-779
[4] Ding H., Zhuang G., Liu J. Extensions of the Resource-constrained Project Scheduling Problem[J]. Automation in Construction, 2023,153:104958
[5] 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
[6] Rahman H. F., Chakrabortty R. K., Michael J. R. Memetic Algorithm for Solving Resource Constrained Project Scheduling Problems[J]. Automation in Construction, 2020,111:103052
[7] Pellerin R., Perrier N., Berthaut F. A Survey of Hybrid Meta-heuristics for the Resource-constrained Project Scheduling Problem[J]. European Journal of Operational Research, 2020,280(2):395-416
[8] 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
[9] Ma Y., He Z., Wang N., et al. Tabu Search for Proactive Project Scheduling Problem with Flexible Resources[J]. Computers and Operations Research, 2023,153:106185
[10] Kolisch R., Hartmann S. Experimental Investigation of Heuristics for Resource-constrained Project Scheduling: An Update[J]. European Journal of Operational Research, 2006,174(1):23-37
[11] Lancaster J., Ozbayrak M. Evolutionary Algorithms Applied to Project Scheduling Problems: A Survey of the State-of-the-art[J]. International Journal of Production Research, 2007,45(2):425-450
[12] 刘寅斌,余咪咪,李洪波,等. 多目标项目调度研究综述:复杂系统优化的视角[J]. 系统科学学报, 2020,28(3):84-89 Liu Y. B., Yu M. M., Li H. B., et al. A Literature Review of Multi-objective Project Scheduling: A Perspective of Complex Systems Optimization[J]. Journal of Systems Science, 2020,28(3):84-89
[13] 张俊光,季飞. 基于开工柔韧性的关键链项目缓冲分配方法[J]. 中国管理科学, 2021,29(8):126-135 Zhang J. G., Ji F. Project Buffer Allocation Method Based on Activity Flexibility[J]. Chinese Journal of Management Science, 2021,29(8):126-135
[14] 张俊光,李凯. 基于项目资源细分的关键链进度监控方法研究[J]. 管理评论, 2021,33(6):224-231 Zhang J. G., Li K. Critical Chain Schedule Monitoring Based on Project Resource Segmentation[J]. Management Review, 2021,33(6):224-231
[15] 张俊光,李婧. 基于活动时间特性的项目缓冲确定方法研究[J]. 管理评论, 2021,33(9):274-283 Zhang J. G., Li J. Project Buffer Sizing Method Based on Activity Time Characteristics[J]. Management Review, 2021,33(9):274-283
[16] 张俊光,武转转. 基于工序逻辑关系的关键链缓冲确定方法研究[J]. 工业工程, 2022,25(6):62-70 Zhang J. G., Wu Z. Z. Buffer Sizing of Critical Chain Based on Activities’ Precedence Relationships[J]. Industrial Engineering Journal, 2022,25(6):62-70
[17] 张俊光,张旭. 基于状态转移预测的关键链活动监控周期确定[J]. 管理评论, 2022,34(10):201-208 Zhang J. G., Zhang X. Determination of Critical Chain Activity Monitoring Cycle Based on State Transition Prediction[J]. Management Review, 2022,34(10):201-208
[18] 张俊光,万丹. 基于缓冲账户差异配置的关键链项目动态集成监控[J]. 管理评论, 2023,35(1):233-242 Zhang J. G., Wan D. Dynamic Integration Monitoring and Control Based on Buffer Accounting Differential Configuration[J]. Management Review, 2023,35(1):233-242
[19] 李雪,何正文,王能民. 考虑鲁棒性成本的多模式双目标项目前摄性调度优化[J]. 系统工程学报, 2021,36(1):74-87 Li X., He Z. W., Wang N. M. Multi-mode Bi-objective Proactive Project Scheduling Optimization Considering Robust Cost[J]. Journal of Systems Engineering, 2021,36(1):74-87
[20] 李阳,何正文,王能民,等. 带有模糊工期的多模式项目鲁棒优化[J]. 工业工程与管理, 2022,27(4):39-49 Li Y., He Z. W., Wang N. M., et al. Robust Optimization for the Multi-mode Project Scheduling Problem with Fuzzy Duration[J]. Industrial Engineering and Management, 2022,27(4):39-49
[21] 贾梦超,何正文,王能民. 基于仿真分析的随机活动工期鲁棒性项目调度优化[J]. 工业工程与管理, 2023,28(2):186-197 Jia M. C., He Z. W., Wang N. M. Simulation Analysis Based Robust Project Scheduling Optimization under Random Activity Duration[J]. Industrial Engineering and Management, 2023,28(2):186-197
[22] 王艳婷,何正文. 资源随机中断下突发事件应急救援鲁棒性多模式项目调度优化[J]. 运筹与管理, 2023,32(3):70-77 Wang Y. T., He Z. W. Multi-mode Robust Project Scheduling Optimization in Emergence Rescue with Stochastic Resource Breakdown[J]. Operations Research and Management Science, 2023,32(3):70-77
[23] Chen Z., Demeulemeester E., Bai S. J., et al. Efficient Priority Rules for the Stochastic Resource-constrained Project Scheduling Problem[J]. European Journal of Operational Research, 2018,270(3):957-967
[24] 李小鹏,李存斌,庞南生. 基于图的广度搜索的进度生成机制[J]. 中国管理科学, 2018,26(9):119-127 Li X. P., Li C. B., Pang N. S. A Schedule Generation Scheme Based on Breadth Search of Graph[J]. Chinese Journal of Management Science, 2018,26(9):119-127
[25] 刘振元,袁慧涛,周成,等. 多技能资源时间窗约束下可中断项目调度的分支定界算法[J]. 系统工程理论与实践, 2019,39(1):183-199 Liu Z. Y., Yuan H. T., Zhou C., et al. Branch-and-bound Based Approach for Preemptive Project Scheduling with Time-window Constraints on Multi-skilled Resources[J]. Systems Engineering-Theory & Practice, 2019,39(1):183-199