不确定资源受限项目调度研究综述_资源约束的项目调度问题资源-CSDN文库

189 浏览量 2021-01-14 11:26:01 上传评论 1 收藏 203KB PDF 举报

资源推荐

资源详情

资源评论

第 29 卷第 4 期

Vol. 29 No. 4

控制与决策

Control and Decision

2014 年 4 月

Apr. 2014

不确定资源受限项目调度研究综述

文章编号: 1001-0920 (2014) 04-0577-08 DOI: 10.13195/j.kzyjc.2013.1309

王凌, 郑环宇, 郑晓龙

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

摘要: 不确定资源受限项目调度问题 (RCPSP) 是研究在不确定环境和有限资源约束下如何合理安排项目活动, 以

实现既定目标的最优化. 不确定 RCPSP 具有很强的工程背景, 在学术和应用上均具有很高的研究价值, 但存在大规

模、强约束、多极小、多目标和不确定等诸多复杂性, 求解非常困难. 为此, 介绍了不确定 RCPSP 的数学描述和几种

具体形式, 重点综述了不确定 RCPSP 的算法进展, 并归纳了相关的应用成果, 最后指出了有待进一步研究的若干方

向和内容.

关键词: 资源受限项目调度；不确定；模型；算法

中图分类号: TP18 文献标志码: A

Survey on resource-constrained project scheduling under uncertainty

WANG Ling, ZHENG Huan-yu, ZHENG Xiao-long

(Department of Automation，Tsinghua University，Beijing 100084，China．Correspondent：WANG Ling，E-mail:

wangling@tsinghua.edu.cn)

Abstract：：：The resource-constrained project scheduling problem(RCPSP) under uncertainty is to study the arrangement

of activities with limited resources under the uncertain environment so as to optimize certain objectives. The RCPSP

under uncertainty is of strong engineering background, which has great research signiﬁcance in both the academic and the

application ﬁelds. The problem has the complexities such as large scale, strong constraint, multiple local minima, multiple

objective and uncertainty, which make it very difﬁcult to be solved. Thus, the mathematical description of the RCPSP under

uncertainty and some of its speciﬁc forms are introduced, and the advances in algorithms for the RCPSP under uncertainty are

reviewed, and some related applications are summarized. Finally, some future research directions and contents are pointed

out.

Key words：：：resource-constrained project scheduling；uncertainty；model；algorithm

0 引引引言言言

不确定资源受限项目调度问题 (不确定 RCPSP)

研究如何在环境不确定的情况下, 通过合理利用资

源和调度活动实现既定目标的最优化. 不确定 RCPSP

具有很强的工程背景, 涉及诸多工业和生活领域, 例

如化工、半导体生产、物流、钢铁制造、工程管理、芯

片制造、软件开发、铁路调度、港口调度以及飞机航

线制定和大型运动会比赛安排等. 不确定 RCPSP 是

经典 RCPSP

[1]

的扩展. 除经典问题存在的大规模、强

约束、多极小和多目标等复杂性, 活动、资源和环境

等环节存在的不确定性使得不确定 RCPSP 具有更高

的求解难度, 是一个更具挑战性的复杂优化问题. 一

方面, 不确定 RCPSP 在数学上属于 NP-hard 问题; 另

一方面, 不确定 RCPSP 更切合实际问题. 因此, 不确定

RCPSP 的研究具有非常重要的学术意义和实际应用

价值.

迄今, 不确定 RCPSP 的研究已经取得了很多成

果. Herroelen 等

[2]

主要针对 10 年前的不确定项目调

度问题的研究进展给予了综述, 但没有专门对资源受

限的问题给予重点考虑. 考虑到近 10 年不确定资源

受限项目调度问题得到了诸多领域的密切关注, 相

关研究得到了迅速发展, 尤其在求解算法方面取得了

很大进展, 本文主要总结近些年国内外有关不确定

RCPSP 的代表性研究成果, 介绍不确定 RCPSP 的问

题描述和几种具体形式, 重点综述相关算法的研究进

展和应用成果, 并提出了不确定 RCPSP 有待进一步

收稿日期: 2013-09-21；修回日期: 2014-01-07.

基金项目: 国家自然科学基金项目(61174189)；高等学校博士学科点专项科研基金项目(20130002110057).

作者简介: 王凌(1972−), 男, 教授, 博士生导师, 从事智能优化调度理论与方法等研究；郑环宇(1989−), 男, 硕士生, 从

事智能优化调度的研究.

578

控制与决策

第 29 卷

研究的若干方向和内容.

1 不不不确确确定定定 RCPSP 的的的描描描述述述

不确定 RCPSP 的项目网络可用单节点 (activity-

on-node, AON) 网络图 𝐺 =(𝑵 , 𝑨) 描述. 其中: 𝐺 表示

网络, 节点 𝑵 = {0, 1, ⋅ ⋅ ⋅ , 𝑛} 表示活动, 边 𝑨 = {(𝑖, 𝑗),

𝑖, 𝑗 ∈ 𝑵 } 表示活动的优先约束. 活动 0 和活动 𝑛 为虚

拟活动, 用于表示项目的开始和结束, 其持续时间及

资源需求均为 0. 活动 𝑗 = 1, 2, ⋅ ⋅ ⋅ , 𝑛 − 1 则为实际活

动, 其开始时间为不确定变量 𝒔

𝑗

, 持续时间为不确定

变量 𝒅

𝑗

, 𝒅 = {𝒅

, 𝒅

, ⋅ ⋅ ⋅ , 𝒅

𝑛−1

} 表示活动时间集合,

它的一个实现 𝑑 = {𝑑

, 𝑑

, ⋅ ⋅ ⋅ , 𝑑

𝑛−1

} ∈ 𝑹

𝑛−1

称为一

次采样或一个场景, 为确定性向量. 在某次实现中, 活

动 𝑗 ∈ 𝑵 的实际开始时间为确定性常量. 𝑺

𝑡

表示在时

刻 𝑡 执行中的活动集合, 𝑷

𝑗

表示活动 𝑗 的前驱活动集

合. 项目共包含 𝐾 种可更新资源, 对于资源 𝑘 = 1, 2,

⋅ ⋅ ⋅ , 𝐾, 项目执行时提供 𝒂

𝑘

单元资源, 𝒂

𝑘

为变量或常

量.

考虑如下假设: 1) 活动优先约束为结束-开始型

约束, 即对活动 𝑗 ∈ 𝑵 , 当其前驱活动 𝑷

𝑗

结束后才

能执行, 且不考虑准备时间; 2) 以最小化项目最大完

工时间为目标; 3) 活动均不可中断, 即一旦开始则必

须执行到结束; 4) 只考虑可更新资源. 因此, 不确定

RCPSP 可描述如下:

min 𝒔

𝑛

. (1)

s.t. 𝒔

𝑖

+ 𝒅

𝑖

⩽ 𝒔

𝑗

, ∀(𝑖, 𝑗) ∈ 𝑨; (2)

∑

𝑗∈𝑆

𝑡

𝒓

𝑗𝑘

⩽ 𝒂

𝑘

, ∀𝑡, ∀𝑘. (3)

其中: 式 (1) 为目标函数; 式 (2) 为活动间优先约束关

系; 式 (3) 为资源约束, 即任意时刻执行中的活动所占

用的某种可更新资源 𝒓

𝑗𝑘

的总和不能超过此种可更新

资源总量.

需要指出的是, 考虑到不确定性的来源和表示方

式的不同, 对于特定的问题, 上述描述可以有不同的

具体形式.

2 不不不确确确定定定 RCPSP 的的的具具具体体体形形形式式式

2.1 分分分类类类原原原则则则

由于不确定性的存在, 人们通常采用前摄调度

(proactive schedule) 和反应调度 (reactive schedule) 来

处理不确定性. 前摄调度通过考虑不确定性的统计特

征建立预测调度, 其目的是减小不确定扰动对调度的

影响. 称确定性 RCPSP 和加入前摄调度生成的调度

为基线调度 (baseline schedule), 以预测项目执行时活

动的实际开始时间, 而在不确定环境下的活动开始时

间与基线调度有所不同. 可以加入反应调度处理执行

过程中出现的扰动, 对调度进行校正或再优化. 通常,

基线调度都需要反应调度对实际执行时出现的扰动

进行处理. 基线调度的鲁棒性越强, 反应调度需要调

整的幅度越小. 极端情况下也可只存在反应调度, 不

依赖基线调度直接对出现的扰动进行资源和活动的

重新规划.

根据不确定性的表示方法、基线调度方法和项

目执行时调度方法, 现有不确定 RCPSP 主要分为 3

类: 模糊 RCPSP、随机 RCPSP 和鲁棒 RCPSP, 如表 1

所示.

表 1 不确定 RCPSP 分类

问题形式表示方法基线调度方法执行的调度方法

模糊 RCPSP 模糊数模糊调度无

随机 RCPSP 随机变量无调度策略

随机变量仅确定性调度反应调度

鲁棒RCPSP

随机变量加入前摄调度反应调度

2.2 模模模糊糊糊 RCPSP

研究模糊 RCPSP 的学者认为, 采用模糊数描述

活动时间更加适合. 理由是, 活动时间的精确分布因

历史数据的缺失通常难以得到, 而由专家或技术人员

预测的活动时间却通常是模糊的. 模糊 RCPSP 是对

不确定 RCPSP 基于模糊数进行建模, 只生成基于模

糊数的基线调度, 调度包含了项目实际执行的各种实

现.

模糊数是描述元素对集合隶属度的函数. 对于确

定性集合 𝑨, 隶属度函数 𝜇

𝐴

: 𝑿 → {0, 1}, 若 𝑥 ∈𝑨, 则

𝜇

𝐴

= 1, 否则 𝜇

𝐴

= 0. 模糊数情况下, 事件 𝑥 ∈ 𝑨 为不

确定事件, 用隶属度函数表示. 定义模糊数

𝑨 的 𝛼 截

集 (𝛼-cut) 为

𝑨

𝛼

= {𝑥 ∈ 𝑿 ∣ 𝜇

𝐴

(𝑥) ⩾ 𝛼}, 所有 𝛼 ∈(0, 1]

的截集均为闭区间. 模糊 RCPSP 的调度为模糊调度,

即所有活动的开始和结束时间均为模糊数, 它涵盖了

所有确定性调度方案.

模糊 RCPSP 通常可描述如下:

min

𝒔

𝑛

. (4)

s.t.

𝒔

𝑖

𝒅

𝑖

⩽

𝒔

𝑗

, ∀(𝑖, 𝑗) ∈ 𝑨; (5)

∑

𝑗∈𝑆

𝑡

𝒓

𝑗𝑘

⩽ 𝒂

𝑘

, ∀

𝑡, ∀𝑘 . (6)

其中

𝑡, ˜𝑠

𝑗

𝑑

𝑗

, 𝑗 ∈ 𝑵 均用模糊数表示.

考虑到一些实际问题, 上述模糊 RCPSP 模型可

扩充为若干特定问题.

1) 模糊项目网络的关键路径问题. 在大型项目管

理中, 关键路径法/计划评审技术 (CPM/PERT) 应用广

泛. 将 CPM/PERT 应用到模糊项目网络, 需要计算模

糊项目网络的关键路径. Chen 等

[3]

根据各活动的浮动

时间定义了活动在模糊项目网络中的关键性, 并根据

剩余7页未读，继续阅读

评论收藏

内容反馈

weixin_38738983

粉丝: 5
资源: 872

不确定资源受限项目调度研究综述

资源受限项目调度问题的研究综述

人工蜂群算法求解资源受限项目调度问题

论文研究-一种求解多目标资源受限项目调度的遗传算法.pdf

资源受限多项目调度问题的两阶段算法

论文研究-应用遗传模拟退火算法实现资源受限项目调度.pdf

基于关键链的柔性资源受限项目调度问题研究 (2007年)

柔性资源受限多项目调度的混沌粒子群算法研究 (2013年)

论文研究-基于改进蚁群优化的多目标资源受限项目调度方法.pdf

论文研究-带有活动重叠的资源受限项目调度问题建模与求解.pdf

资源受限App开发项目进度优化研究.pdf

柔性资源受限多项目调度的混沌粒子群算法研究.pdf

求解资源受限项目调度的双种群准粒子群算法.pdf

基于粒子群算法的多类资源受限项目调度.pdf

群算法求解多模式资源受限项目调度问题.pdf

自适应粒子群算法求解资源受限多项目调度问题.pdf

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

XCP协议的规范文档

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）