一种复杂项目调度问题的混合智能算法

• 论文 •

一种复杂项目调度问题的混合智能算法

程序，吴澄

清华大学自动化系，北京 100084

收稿日期:2005-02-24 修回日期:2005-04-26 出版日期:2006-04-15 发布日期:2006-04-25
基金资助:
国家重点基础研究计划资助项目（2002CB312202）。

Hybrid algorithm for complex project scheduling

CHENG Xu,WU Cheng

Dep.of Automation, Tsinghua Univ.,Beijing 100084, China

Received:2005-02-24 Revised:2005-04-26 Online:2006-04-15 Published:2006-04-25
Supported by:
Project supported by the National Basic Research Program，China(No.2002CB312202).

摘要/Abstract

摘要： 针对有资源约束的项目调度问题模型的不足，调研了企业需求，提出了带有预约时间窗口约束的项目调度模型，并针对该类模型的特点分析了原有算法存在的问题，将分枝定界算法与启发式算法相结合，提出了一种解决该类问题的混合智能算法。仿真结果表明，该算法的优化效果明显优于其他算法。

关键词: 项目调度, 预约时间窗口约束, 分枝定界算法, 启发式算法<

Abstract: To deal with deficiency of Resource Constrained Project Scheduling Problem (RCPSP) model, a project scheduling model with engaged time windows constraint was proposed after surveying enterprises demands. After analyzing the characteristics of the proposed model and the shortcomings of existing algorithms for model, a hybrid algorithm which combined branch-and-bound procedure and heuristic algorithms was presented. The simulation results demonstrated that the optimization effect of the proposed algorithm was better than other algorithms.

Key words: project scheduling, engaged time window constraint, branch-and-bound algorithm, heuristic algorithm

中图分类号:

F406.2

程序，吴澄. 一种复杂项目调度问题的混合智能算法[J]. .

CHENG Xu,WU Cheng. Hybrid algorithm for complex project scheduling[J]. .

参考文献

［1］ HERROLEN W,REYCK B D,DEMEULEMEESTER E.Resource-constrained project scheduling:a survey of recent developments［J］.Computers & Operations Research,1998,25(4):279-302.

[2] WEGLARZ J.Project scheduling:recent models,algorithms and applications［M］.Amsterdam,Netherlands：Kluwer，1999.

[3] BRUCKER P,DREXL A,MOHRING R,et al.Resource-constrained project scheduling:notation,classification,models,and methods［J］.European Journal of Operational Research,1999,112:3-41.

[4] DEMEULEMEESTER E,HERROLEN W.A branch-and-bound procedure for the multiple resource-constrained project scheduling problem［J］.Management Science,1992,38(12):1803-1818.

[5] DEMEULEMEESTER E,HERROLEN W.A branch-and-bound procedure for the generalized resource-constrained project scheduling problem［J］.Operations Research,1997,45(2):201-212.

[6] REYCK B D,HERROLEN W.A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations［J］.European Journal of Operational Research,1998,111:152-174.

[7] DORNDORF U,PESCH E,PHAN-HUY T.A time-oriented branch-and-bound algorithm for project scheduling with generalised precedence constraints［J］.Management Science,2000,46:1365-1384.

[8] NEUMANN K,SCGWINDT C.Activity-on-node networks with minimal and maximal time lags and their application to make-to-order production［J］.Operation Research Spectrum,1997,19:205-217.

[9] HEILMANN R.A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags［J］.European Journal of Operational Research,2003,144:348-365.

[10] BLAZEWICZ J,LENSTRA J,RINNOOYKA A.Scheduling subject to resource constraints:classification and complexity［J］.Discrete Applied Mathematics,1983,5:11-24.

[11] KOLISCH R.Project scheduling under resource constraints - efficient heuristics for several problem classes［M］.Heidelberg,Germany:Physica，1995.

[12] DAVIS E,PATTERSON J.A comparison of heuristic and optimum solutions in resource-constrained project scheduling［J］.Management Science,1975,21:944-955.

[13] ALVAREZ-VALDEZ R,TAMARIT J M.Heuristic algorithms for resource-constrained project scheduling:a review and an empirical analysis［A］.Advances in Project Scheduling［C］.Amsterdam,Holland:1989.113-134.

[14] HARTMANN S.A competitive genetic algorithm for resource-constrained project scheduling［J］.Naval Research Logistics,1998,45:733-750.

[1]	陈志远,伍章俊,童珊珊,刘晓. 基于改进双归档进化算法的多目标动态软件项目调度[J]. 计算机集成制造系统, 2021, 27(9): 2565-2574.
[2]	王小明,陈庆新,毛宁. 基于近似动态规划的模具项目调度[J]. 计算机集成制造系统, 2020, 26(6): 1691-1701.
[3]	朱宏伟,陆志强. 考虑资源转移时间的项目可拆分资源受限多项目调度问题[J]. 计算机集成制造系统, 2019, 25(第3): 586-597.
[4]	廖怡娜,陆志强. 考虑作业返工的资源受限项目调度问题[J]. 计算机集成制造系统, 2019, 25(第11): 2762-2774.
[5]	杨超,陆志强. 项目拆分和多项目调度集成决策模型与算法[J]. 计算机集成制造系统, 2018, 24(第3): 550-557.
[6]	初梓豪,徐哲,于静. 带有活动重叠的多模式资源受限项目调度问题[J]. 计算机集成制造系统, 2017, 23(第3期): 557-566.
[7]	张猛,陆志强. 多技能资源约束项目调度问题的改进算法[J]. 计算机集成制造系统, 2016, 22(第3期): 782-792.
[8]	何杰光,陈新度,陈新,刘强. 求解资源受限项目调度的双种群准粒子群算法[J]. 计算机集成制造系统, 2015, 21(第9期): 2446-2457.
[9]	何杰光,陈新度,陈新,刘强. 求解资源受限项目调度的动态多样性进化策略[J]. 计算机集成制造系统, 2015, 21(第8期): 2089-2098.
[10]	贾艳,王致民,张跃刚. 柔性资源约束项目调度问题的启发式求解方法[J]. 计算机集成制造系统, 2015, 21(第7期): 1846-1855.
[11]	崔南方,赵雁. 考虑项目网络特征的鲁棒性项目调度缓冲方法比较[J]. 计算机集成制造系统, 2015, 21(第1期): 280-288.
[12]	王伟鑫,王旭,葛显龙. 任务可拆分的多模式多项目调度模型与算法[J]. 计算机集成制造系统, 2014, 20(6): 1388-1397.
[13]	靳金涛,聂兰顺,战德臣,徐晓飞. 基于人工蜂群的空间资源受限项目调度算法[J]. 计算机集成制造系统, 2014, 20(5): 1088-.
[14]	王磊,战德臣,聂兰顺. 基于市场机制的多项目分散式调度问题[J]. 计算机集成制造系统, 2014, 20(08): 1969-1979.
[15]	张静文,刘金波,李若楠. 基于鲁棒性的离散时间—费用权衡项目调度[J]. , 2013, 19 (11 ): 0-0.