时间—资源权衡协调问题的多目标优化决策模型

摘要

时间—资源权衡协调是以追求资源消耗费用极小和项目完工时间最短为目标，在满足项目工期要求下，根据项目活动时间的先后次序与可更新资源约束有效确定项目时间表。提出了一个具有资源约束问题的时间—资源权衡协调问题的多目标优化决策数学模型。在模型中，对相互冲突的项目工期与整个被消耗的资源费用是可权衡调节的。通过权衡协调和调节项目工期与整个资源消耗费用，得到了满足权衡协调关系的满意可行解，并给出了一个数值算例。此外，在对应于资源约束的Lagrangian松弛表示式中，给出了该二人对策问题的有关特性。

正文

《1 引言》

1 引言

结构项目计划和时间表的主要目标通常是在项目活动的某种先后次序和有效资源的限制条件下确定项目的完工时间, 使得项目总的完工费用极小^[1]。一个项目活动 (active) 的完工成本实际上是为执行任务而需求的若干资源使用量的总费用, 因而有效资源可以视为项目活动时间的函数。时间—费用协调问题作为项目实施时间的函数产生极小费用的项目时间表是结构计划和控制最重要的问题之一。对于求解时间—费用协调问题已经有一些学者^[2,3] 提出了一些模型和算法。众所周知, 项目费用极小化不但与欲求的目标有关, 而且还与某些需求的重要资源的消耗量有关。时间—资源协调问题给项目计划者如下信息:当项目时间每减少一个时间单位时, 每种资源的消耗量 (或其费用) 将增加若干。必须考虑项目时间与每种资源消耗 (或其费用) 之间的关系。取代单个时间—费用曲线, 项目计划人员必须考虑产生时间—资源协调曲线的有效集合。每种时间—资源协调曲线对应着时间—费用协调问题的最优曲线, 这种费用被定义为每种资源在每个活动使用的资源费用的加权和^[4]。在激烈的市场竞争条件下, 市场对资源要求的不确定性导致资源的有效供应是不确定的。因此它将导致项目活动时间的不确定性^[5] 及其费用的变化。这样必须考虑这些活动所需要的各种类型资源的可变需求量, 资源供应的不确定性以及时间—资源协调问题。从而, 迫切需要建立一个在不确定环境条件下具有资源约束的恰当的时间—资源协调模型。

在项目时间表里, 文献[4]把项目费用和时间的多目标数学模型^[6] 推广到极小每个活动费用和项目时间的协调问题。在这里, 假设有效的资源量是没有限制的。显然这种假设是不能完全反映实际情况。建立在这种扩展的框架基础上, 笔者提出了一个具有先后次序和资源限制的时间—资源协调模型, 它不同于文献[4]中的模型的主要差异表现在如下几个方面:a. 活动时间被作为决策变量;b.具有资源限制的时间—资源协调问题的项目时间表模型;c.所有消耗资源费用被合并为一个目标。显然, 在讨论具有资源限制的时间—资源协调问题时必须考虑到资源受限制的问题, 这一点几乎类似于具有资源受限制的时间—费用协调项目时间表问题^[7,8]。因为, PERT路径或CPM路径意义下极小化项目活动完工时间是不实际的, 并且在项目时间表过程中也不能有效监控随时发生的时间与资源相互冲突的情况。因此, 尽管求解更为困难, 然而考虑资源受限制的时间—资源协调的项目时间表问题是必须的, 并且变得更富实际意义。

《2 时间—资源权衡协调多目标优化决策模型》

2 时间—资源权衡协调多目标优化决策模型

时间—资源协调项目时间表问题主要涉及到满足有效资源和先后次序约束下的时间表、资源费用和项目活动的时间。其目标是在满足项目活动的完工时间条件下极小的总资源费用。假设项目没有抢断约束, 其每个活动时间是未知的。因此这些时间不超过活动的正常时间。并假设资源费用与项目时间具有某种递减函数关系, 如线性或其他函数关系。在模型中将用到如下一些符号:

N 项目的活动数,

K 可更新资源类型数,

T_j 活动j (j=1, 2, …, N) 的完工时间,

H 表示具有完工-开始先后次序的活动对集合, 即项目网络中的事件数,

S_t 于时间区间 (t-1, t]={iT_i<t≤T_i+t_i}进行中的活动数,

T_Nj 活动j的正常时间 (normal time) ,

T_Cj 活动j的应急时间 (crash time) ,

t_j 活动j的时间变量, 它取值于T_Nj-T_Cj和T_Nj之间的整数, 即T_Nj-T_Cj≤t_j≤T_Nj,

R_kt 在时间t时刻资源类型k (k=1, 2, …, K) 的所有有效资源量,

a^j_k (t_j) 活动j在时间段t_j需求资源类型k整个费用量, 其资源类型k的单位价格为a_k,

$\tilde{r}$ $\tilde{r}$ _ik (t_j) 对应于时间变量t_j, 活动j每个时期需求资源类型k的数量, 且

$\tilde{r}_{i k} (t_{j}) = r_{j k} | 1 + (Τ_{Ν j} - t_{j}) Δ k |$ $\tilde{r}_{i k} (t_{j}) = r_{j k} | 1 + (Τ_{Ν j} - t_{j}) Δ k |$

其中r_jk为单位时间里需求第k种类型资源量。不失一般性, 假设活动1表示项目的开始, 而活动N+1是哑元表示项目的完工。哑元活动不需求任何资源也没有时间要求, 即t_N+1=0和 $\tilde{r}_{(Ν + 1) k} (t_{Ν + 1}) = 0 \forall k$ $\tilde{r}_{(Ν + 1) k} (t_{Ν + 1}) = 0 \forall k$ 。

时间-资源协调问题的最优模型可以表示为:

Minz₁=T_N+1 (1)

$Μ i n z_{2} = \sum_{k = 1}^{Κ} \sum_{j = 1}^{Ν} a_{j}^{k} (t_{j}) (2)$ $Μ i n z_{2} = \sum_{k = 1}^{Κ} \sum_{j = 1}^{Ν} a_{j}^{k} (t_{j}) (2)$

$\begin{array}{l} s . t . Τ_{j} - Τ_{i} \geq t_{i} \forall (i, j) \in Η (3) \\ Τ_{C i} \leq t_{i} \leq Τ_{Ν i} 对活动 i (4) \\ \sum_{i \in S_{t}} \tilde{r}_{i k} (t_{i}) \leq R_{k t}, \\ t = 1, 2, \dots Τ_{Ν + 1}, k = 1, 2, \dots, Κ (5) \end{array}$ $\begin{array}{l} s . t . Τ_{j} - Τ_{i} \geq t_{i} \forall (i, j) \in Η (3) \\ Τ_{C i} \leq t_{i} \leq Τ_{Ν i} 对活动 i (4) \\ \sum_{i \in S_{t}} \tilde{r}_{i k} (t_{i}) \leq R_{k t}, \\ t = 1, 2, \dots Τ_{Ν + 1}, k = 1, 2, \dots, Κ (5) \end{array}$

式 (1) 和式 (2) 表明问题是一个二目标规划模型, 它们分别是极小化项目的完工时间与极小化资源消耗的总费用。约束条件式 (3) 保证活动的先后次序被满足。约束条件式 (4) 表明活动的时间变量是有界的。约束条件式 (5) 刻划了任何时刻资源需求的总和不超过它们的有效资源量。

如果删去第二个目标问题将变为具有可变时间的资源受限制的项目时间表问题:

$\begin{array}{l} \min z = Τ_{Ν + 1} (6) \\ s . t . 式 (3), 式 (4) 和式 (5) \end{array}$ $\begin{array}{l} \min z = Τ_{Ν + 1} (6) \\ s . t . 式 (3), 式 (4) 和式 (5) \end{array}$

目标函数式 (2) 有点类似于具有资源投资问题^[9,10]的目标函数。

《3 资源约束的Lagrangian松弛形式》

3 资源约束的Lagrangian松弛形式

根据松弛方法, 考虑对应于资源约束式 (5) 的Lagrangian松弛形式, 通过改变对应于资源约束的乘子将影响资源的平滑结果。因此, 资源的使用情况随时都被受到监控。

设λ_k是对应于资源约束式 (5) 的Lagrangian乘子 (显见λ_k是非负的) , 那么有Lagrangian函数

$\begin{array}{l} L (y, λ) = \sum_{k = 1}^{Κ} \sum_{j = 1}^{Ν} a_{j}^{k} (t_{j}) - \\ \sum_{k = 1}^{Κ} \sum_{t = 1}^{Τ_{Ν + 1}} λ_{k t} (\sum_{i \in S_{t}} \tilde{r}_{i k} (t_{i}) - R_{k t}) (7) \end{array}$ $\begin{array}{l} L (y, λ) = \sum_{k = 1}^{Κ} \sum_{j = 1}^{Ν} a_{j}^{k} (t_{j}) - \\ \sum_{k = 1}^{Κ} \sum_{t = 1}^{Τ_{Ν + 1}} λ_{k t} (\sum_{i \in S_{t}} \tilde{r}_{i k} (t_{i}) - R_{k t}) (7) \end{array}$

为了方便起见, 考虑单目标问题:

$\min z_{2} = \sum_{k = 1}^{Κ} \sum_{j = 1}^{Ν} a_{j}^{k} (t_{j}), (8)$ $\min z_{2} = \sum_{k = 1}^{Κ} \sum_{j = 1}^{Ν} a_{j}^{k} (t_{j}), (8)$

$\begin{array}{l} s . t . Τ_{j} - Τ_{i} \geq t_{i} \forall (i, j) \in Η, \\ Τ_{C i} \leq t_{i} \leq Τ_{Ν i} 对活动 i, \\ \sum_{i \in S_{t}} \tilde{r}_{i k} (t_{i}) \leq R_{k t} ‚ \end{array}$ $\begin{array}{l} s . t . Τ_{j} - Τ_{i} \geq t_{i} \forall (i, j) \in Η, \\ Τ_{C i} \leq t_{i} \leq Τ_{Ν i} 对活动 i, \\ \sum_{i \in S_{t}} \tilde{r}_{i k} (t_{i}) \leq R_{k t} ‚ \end{array}$

$\begin{array}{l} t = 1, 2, \dots, Τ_{Ν + 1}, k = 1, 2, \dots, Κ, \\ Τ_{Ν + 1} \leq Τ (项目的 ⌶ 期) 。 \end{array}$ $\begin{array}{l} t = 1, 2, \dots, Τ_{Ν + 1}, k = 1, 2, \dots, Κ, \\ Τ_{Ν + 1} \leq Τ (项目的 ⌶ 期) 。 \end{array}$

因此规划式 (8) 的对偶问题为

$\max_{λ \geq 0} d (λ, R) (9)$ $\max_{λ \geq 0} d (λ, R) (9)$

其中对偶函数为

$\begin{array}{l} d (λ, R) = \sum_{k = 1}^{Κ} [L_{k} (λ) - \sum_{t = 1}^{Τ_{Ν + 1}} λ_{k t} R_{k t}] (10) \\ L_{k} (λ) = \min_{t_{i}} [\sum_{i = 1}^{Ν} a_{i}^{k} (t_{i}) - \sum_{t = 1}^{Τ_{Ν + 1}} \sum_{i \in S_{t}} λ_{k t} \tilde{r}_{i k} (t_{i})] (11) \end{array}$ $\begin{array}{l} d (λ, R) = \sum_{k = 1}^{Κ} [L_{k} (λ) - \sum_{t = 1}^{Τ_{Ν + 1}} λ_{k t} R_{k t}] (10) \\ L_{k} (λ) = \min_{t_{i}} [\sum_{i = 1}^{Ν} a_{i}^{k} (t_{i}) - \sum_{t = 1}^{Τ_{Ν + 1}} \sum_{i \in S_{t}} λ_{k t} \tilde{r}_{i k} (t_{i})] (11) \end{array}$

优化问题式 (9) 称为对应于原2个目标优化问题的部分对偶问题。显然, 对偶函数d (λ, R) 对于单个资源类型k的对偶目标是可分的。根据Lagrangian乘子的意义, λ_kt可解释为资源类型k在时刻t的影子价格, 每个子问题K_k可被解释为一个效益极大化问题 (即浪费的资源尽可能地少) 。

用‘两公司´ 模型解释对偶问题式 (9) :公司P的目标为极小化资源成本效益 (被消耗资源总的费用极小) , 在时刻t, 面临着资源供应R_kt (为方便起见将省略下标t) , 在不影响项目排序的完工时间的前提下, 尽可能出售多余的有效资源给公司Q。公司Q为了自己的利益 (极小化项目的完工时间) , 以价格λ_kt向公司P购买大量的有效资源。由于公司P的目标是为了极小化被消耗的资源总费用, 因此它可能出售多余的有效资源。为了取得公司的极大利益 (项目尽可能早的完工) , 公司Q通过调整资源价格向公司P购买更多的剩余资源。

众所周知, Lagrangian松弛算法是逐步极大对偶问题的。在每次迭代过程中, 不断修正Lagrangian乘子λ_kt, 利用具有新乘子值的资源子问题去计算d (λ, R) 。根据上面的解释和资源受限制的项目时间表问题的某些特征, 可以得到如下事实:

1) 这种两公司模型可以作为二人对策问题。公司Q (参与人1) 为极小化项目时间表的完工时间, 根据完全理想的信息情况, 经过不断地协商讨论首先确定价格λ_kt;公司P (选手2) 在观察到这个λ_kt值后, 首先考虑极小被消耗资源总费用与极小项目时间表的完工时间的平衡情况, 然后做出自己的最优选择t_j (活动的时间) 。

2) 根据数学规划中最优互补松弛条件和Lagrange乘子的某些特征, 如果在迭代中乘子λ_kt都是正值, 那么资源将被得到充分地使用。这是非常理想的情况, 因为在取得被消耗资源总费用极小化的同时, 也获得了项目时间表的极小化完工时间。为了极小化项目完工时间和被消耗资源的总费用, 只有不断增加Lagrange乘子使得资源尽可能地获得充分地使用。

3) 在资源与时间的协调过程中, 资源的使用与平滑问题将得到有效地监控。这是因为当考虑到资源约束的互补松弛条件后, 在项目的完工时间和被消耗资源的总费用极小的过程中, 通过平衡资源的使用与活动的时间选择, 可以客观有效地调节Lagrane乘子。

4) 二目标问题隐含着对相互冲突目标的优化问题。为了使项目的消耗资源的总费用极小, 必须选择活动的最大时间使得尽可能少地使用有效资源。同时, 为了使得项目的完工时间极小, 应该尽可能多地减少活动的时间 (选择较少的活动时间) 。这将导致增加有效资源的使用量。这就需要不断调整资源使用量与活动时间的关系, 从而获得一个最优或近似最优的结果。

《4 求解方法》

4 求解方法

为了求解时间—资源协调问题, 提出一个建立在三阶段策略基础上的折衷Lagrangian松弛问题的算法。详细算法过程:

初始化过程确定项目活动的时间t_j (j=1, 2, …, N) 。在时间区间T_j=T_Ci, T_Ni随机产生活动j的一个工期 (∀_j ) ; 或置t_j=T_N, (∀_j ) 。

阶段1 求解具有可变时间的资源受限制的项目时间表问题式 (6) 。利用某些有效算法 (如资源约束Lagrangian松弛方法^[11]或遗传算法^[12] ) 试图寻求一个可行的时间表, 即满足先后次序 (技术约束条件) 和资源约束的项目时间表。

如果项目的完工时间小于项目的工期则转阶段2;否则将减少某些活动 (如需求资源数与活动时间乘积较大的活动) 的时间 (使之位于时间区间T_j) 重新求解问题式 (6) 。倘若不能找到一个可行时间表, 则停止计算, 无需进入下阶段的计算。

阶段2 检验当前的解是否违反资源限制。如果没有资源冲突则把具有最小的 $\sum_{k} a_{j}^{k} (t_{j}) t_{j}$ $\sum_{k} a_{j}^{k} (t_{j}) t_{j}$ 对应的活动j尽可能地向右移动 (当然不能违反活动的先后次序与资源约束限制条件) , 然后转阶段3;否则, 利用具有离散或连续变量非线性规划中的某种原始-对偶优化算法求解时间变量被限制于区间T_j的问题式 (9) , 从而得到项目被消耗的总费用。

阶段3 改进资源的使用情况, 主要目的是修正或调整某些活动的时间, 使得资源浪费的情况得到改善, 由此而来可减少项目的完工时间。令

$\begin{array}{l} R_{G k t} = \sum_{i \in S_{t}} \tilde{r}_{i k} (t_{i}) - R_{k t} ‚ \\ f o r t = 1, 2, \dots, Τ_{Ν + 1}, k = 1, 2, \dots, Κ (12) \end{array}$ $\begin{array}{l} R_{G k t} = \sum_{i \in S_{t}} \tilde{r}_{i k} (t_{i}) - R_{k t} ‚ \\ f o r t = 1, 2, \dots, Τ_{Ν + 1}, k = 1, 2, \dots, Κ (12) \end{array}$

Step 1 对i∈S_t₂, 计算 $R_{G t_{2}} = \min \sum_{k} R_{G k t}$ $R_{G t_{2}} = \min \sum_{k} R_{G k t}$ 和 $\sum_{k} \tilde{r}_{k t_{2}} (t_{i}) a_{i}^{k} (t_{i})$ $\sum_{k} \tilde{r}_{k t_{2}} (t_{i}) a_{i}^{k} (t_{i})$ 。令S_t₂=I₂, 对任意得t=1, 2, …, T_N+1, k=1, 2, …, K, 显然有R_Gkt≤0。如果R_Gkt < 0, 那么发生最大资源浪费。

倘若在集合S_t₂中至少有两个相同, 那么选取具有较小值的指标 (时间) 。当然, 它的时间区间必须是一点。

Step 2 修正活动的时间, 需要考虑两种情况:

1) I₂=1。设S_t₂∩S_t₂+1=∅, 如果t_Ci₂≠{t_i₂}, 置 $\bar{t}_{i_{2}} = t_{i_{2}} - 1$ $\bar{t}_{i_{2}} = t_{i_{2}} - 1$ ;否则固定t_i₂。依据项目管理部门的意见, 重复这个过程直到获得一个满意的结果。

2) I₂≥2或S_t₂∩S_t₂+1≠∅。不失一般性, 可得如下排列:

$\begin{array}{l} \sum_{k} \tilde{r}_{k t_{2}} (t_{i_{2}}) a_{i_{2}}^{k} (t_{i_{2}}) \geq \dots \geq \\ \sum_{k} \tilde{r}_{k t_{2}} (t_{i_{Ι_{2}}}) a_{i_{Ι_{2}}}^{k} (t_{i_{Ι_{2}}}) 。 \end{array}$ $\begin{array}{l} \sum_{k} \tilde{r}_{k t_{2}} (t_{i_{2}}) a_{i_{2}}^{k} (t_{i_{2}}) \geq \dots \geq \\ \sum_{k} \tilde{r}_{k t_{2}} (t_{i_{Ι_{2}}}) a_{i_{Ι_{2}}}^{k} (t_{i_{Ι_{2}}}) 。 \end{array}$

对j=1, 2, …, I₂, 选择γ_{i_j}使得γ_i₂≥…≥γ_{i_I₂}≥0与t_{i_I₂}≥γ_{i_I₂}+t_{Ci_I₂} 成立, 然后修正 $\bar{t}_{i_{Ι}} = t_{i_{Ι}} - γ_{i_{Ι}}$ $\bar{t}_{i_{Ι}} = t_{i_{Ι}} - γ_{i_{Ι}}$ 。例如, 可以选择γ_i₂使得 $\max (\tilde{r}_{k t_{2}} (γ_{i_{2}})) \leq q_{i_{2}}$ $\max (\tilde{r}_{k t_{2}} (γ_{i_{2}})) \leq q_{i_{2}}$ , 其中 $q_{i_{2}} = \min_{k, i_{2}} [R_{k t_{2}} - \tilde{r}_{k t_{2}} (\bar{t}_{i_{2}})]$ $q_{i_{2}} = \min_{k, i_{2}} [R_{k t_{2}} - \tilde{r}_{k t_{2}} (\bar{t}_{i_{2}})]$ ;或者, 为简单起见, 选择所有的γ_i₂为0或1。重复这个过程直到|R_Gkt| 是一个适当小的量或者获得一个满意的结果。

终止条件的检验如果满足下列三条件之一, 计算终止。否则转到阶段1。

1) 如果对所有的t和k有 $Y_{k t} - \sum_{i \in S_{t}} \tilde{r}_{i k} (t_{i}) \leq ε_{k t}$ $Y_{k t} - \sum_{i \in S_{t}} \tilde{r}_{i k} (t_{i}) \leq ε_{k t}$ , 其中Y_kt表示资源类型k在t时刻的供应量且Y_kt≤R_kt, ε_kt 是预先给定的一个上界。

2) 满足预先给定的阶段迭代数。

3) 对t $_{i}^{j}$ $_{i}^{j}$ ∈T_i (j=1, 2) 并且t $_{i}^{2}$ $_{i}^{2}$ ≤t $_{i}^{1}$ $_{i}^{1}$ ∀i, 如果存在一个 $\bar{t}$ $\bar{t}$ _i∈ (t $_{i}^{2}$ $_{i}^{2}$ , t $_{i}^{1}$ $_{i}^{1}$ ) 使得z₁ ( $\bar{t}$ $\bar{t}$ ) 满足 $z_{1} (\bar{t}) \leq z_{1} (t^{1})$ $z_{1} (\bar{t}) \leq z_{1} (t^{1})$ 和 $z_{1} (\bar{t}) \leq z_{2} (t^{2})$ $z_{1} (\bar{t}) \leq z_{2} (t^{2})$ 。

对资源类型k在t时刻Y_kt可以表示资源的平均使用量^[9]。

当活动时间减少时, 项目的完工时间将减少但是资源消耗的总费用将增加。

稍后将看到, 减少资源约束条件下的活动时间并不总是能够减少项目的工期。因此, 上面描述的终止条件式 (3) 是可行的。

在执行算法阶段2时, R_Gkt的非负性必定会取得, 即资源不足的情况不可能发生。当发生资源浪费的情况时, 阶段3的主要任务是调整活动时间。为了得到一个折衷的结果, 在协调过程中, 主要是通过重复调整减少项目工期的效益与增加使用有效资源的费用之间关系来完成。

《5 一个算例》

5 一个算例

为了显示所提出的模型和算法, 一个要求两种资源类型的简单项目网络模型见图1, 所有活动的正常时间与应急时间如表1所示。

《图1》

图1 项目网络

Fig.1 Project network

表1 活动期限

Table 1 Bounds of activity duration

《表1》

Activity	Crash (t_C)	Normal (t_N)
A (1)	1	3
B (2)	2	4
C (3)	3	3
D (4)	4	6
E (5)	3	5
F (6)	2	2

为简单起见, 只讨论资源费用与活动时间具有如下线性关系:

$a_{j}^{k} (t) = b_{j}^{k} - c_{j}^{k} t, 对 k = 1, 2; j = 1, 2, \dots, 6 (13)$ $a_{j}^{k} (t) = b_{j}^{k} - c_{j}^{k} t, 对 k = 1, 2; j = 1, 2, \dots, 6 (13)$

非负参数b^k_j, c^k_j如表2所示。需求的资源是R₁=10和R₂=6。活动需求的资源与时间的关系是逐段线性函数 (见表3) 。

表2 资源费用与活动期

Table 2 Resource cost and activity duration

《表2》

活动数	k=1		k=2
活动数	b	c	b	c
A (1)	6.09	2.43	6.58	2.00
B (2)	8.01	1.48	9.80	1.75
C (3)	9.50	2.30	7.20	2.86
D (4)	10.95	1.19	12.65	0.50
E (5)	9.55	1.98	12.14	2.34
F (6)	12.05	1.96	14.88	2.71

表3 单位活动期资源要求量

Table 3 Resource required per duration for activity

《表3》

$\tilde{r}_{1}^{1} (t_{1}) = {\begin{cases} 8 - t_{1} 1 \leq t_{1} \leq 2 \\ 14 - 4 t_{1} 2 \leq t_{1} \leq 3 \end{cases}$ $\tilde{r}_{1}^{1} (t_{1}) = {\begin{cases} 8 - t_{1} 1 \leq t_{1} \leq 2 \\ 14 - 4 t_{1} 2 \leq t_{1} \leq 3 \end{cases}$	$\tilde{r}_{1}^{2} = 7 - t_{1} 1 \leq t_{1} \leq 3$ $\tilde{r}_{1}^{2} = 7 - t_{1} 1 \leq t_{1} \leq 3$
$\tilde{r}_{2}^{1} = {\begin{cases} 13 - 2 t_{2} 2 \leq t_{2} \leq 3 \\ 10 - t_{2} 3 \leq t_{2} \leq 4 \end{cases}$ $\tilde{r}_{2}^{1} = {\begin{cases} 13 - 2 t_{2} 2 \leq t_{2} \leq 3 \\ 10 - t_{2} 3 \leq t_{2} \leq 4 \end{cases}$	$\tilde{r}_{2}^{2} = 7 - t_{2} 2 \leq t_{2} \leq 4$ $\tilde{r}_{2}^{2} = 7 - t_{2} 2 \leq t_{2} \leq 4$
$\tilde{r}_{3}^{1} (t_{3}) = 5$ $\tilde{r}_{3}^{1} (t_{3}) = 5$	$\tilde{r}_{3}^{2} (t_{3}) = 4$ $\tilde{r}_{3}^{2} (t_{3}) = 4$
$\tilde{r}_{4}^{1} (t_{4}) = 13 - t_{4} 4 \leq t_{4} \leq 6$ $\tilde{r}_{4}^{1} (t_{4}) = 13 - t_{4} 4 \leq t_{4} \leq 6$	$\tilde{r}_{4}^{2} (t_{4}) = 8 - t_{4} 4 \leq t_{4} \leq 6$ $\tilde{r}_{4}^{2} (t_{4}) = 8 - t_{4} 4 \leq t_{4} \leq 6$
$\tilde{r}_{5}^{1} (t_{5}) = {\begin{cases} 13 - 2 t_{5} 3 \leq t_{5} \leq 4 \\ 9 - t_{5} 4 \leq t_{5} \leq 5 \end{cases}$ $\tilde{r}_{5}^{1} (t_{5}) = {\begin{cases} 13 - 2 t_{5} 3 \leq t_{5} \leq 4 \\ 9 - t_{5} 4 \leq t_{5} \leq 5 \end{cases}$	$\tilde{r}_{5}^{2} (t_{5}) = {\begin{cases} 8 - t_{5} 3 \leq t_{5} \leq 4 \\ 12 - 2 t_{5} 4 \leq t_{5} \leq 5 \end{cases}$ $\tilde{r}_{5}^{2} (t_{5}) = {\begin{cases} 8 - t_{5} 3 \leq t_{5} \leq 4 \\ 12 - 2 t_{5} 4 \leq t_{5} \leq 5 \end{cases}$
$\tilde{r}_{6}^{1} (t_{6}) = 4$ $\tilde{r}_{6}^{1} (t_{6}) = 4$	$\tilde{r}_{6}^{2} (t_{6}) = 2$ $\tilde{r}_{6}^{2} (t_{6}) = 2$

计算过程描述如下:

Step 1 初始化置所有活动的时间为正常时间。初始时间与资源如表4所示。

表4 初始期与资源要求

Table 4 Initial duration and resources requirement

《表4》

活动时间		A 3		B 4		C 3		D 6		E 5		F 2
$\tilde{r}_{1}$ $\tilde{r}_{1}$	$\tilde{r}_{2}$ $\tilde{r}_{2}$	2	4	6	3	5	4	7	2	4	2	4	2

Step 2 由Step1得项目的完工时间为z₁=20个时间单位, 其时间表为:A—D—B—C //E—F, 其中符号C//E表示活动C与E是并行关系。

Step 3 经过Step 2的计算, 目标函数z₂=36.63单位。

Step 4 由Step 3的计算, 可以选取活动的时间及其每单位时间需求的资源量如表5所示。返回Step 1 (不存在q_i₂使得I₂≥2和S_t₂∩S_t₂+1≠∅) 。

表5 选择期与资源要求

Table 5 Selecting duration and resources requirement

《表5》

活动时间		A 3		B 4		C 3		D 5		E 5		F 2
$\tilde{r}_{1}$ $\tilde{r}_{1}$	$\tilde{r}_{2}$ $\tilde{r}_{2}$	2	4	6	3	5	4	8	3	4	2	4	2

Step 5 经计算, 项目的时间表与Step 2的结果相同, 项目的完工时间为z₁=19时间单位, 目标函数z₂=38.32单位。

如此迭代, 可以得到能够接受的满意结果。

在研究具有资源约束的时间-资源协调问题中, 有时发现项目的工期并不随活动时间的减少而减少。例如, 可置如下活动时间:A=3, B=3或4, C=3, D=6, E=4, F=5。经计算, 项目时间表为A—D—B—C—E—F或A—D—B— E—C—F, 项目的工期z₁分别是21和22个时间单位, 总的资源费用分别是44.18单位和40.95单位。显然, 这些项目工期都大于前面所得到的结果。这个结论表明:在资源约束条件下, 项目的完工时间并不随活动时间的减少而减少。

《6 结论》

6 结论

笔者所提出的时间—资源协调问题新的数学模型, 不同于其他模型 (如参考文献[4]) , 其主要差异如下:a. 把活动的时间视为决策变量;b. 考虑了资源约束问题;c. 具有2个相互冲突的目标函数, 即项目工期与总的资源费用, 并且在任何时刻这2个目标之间都是自适应的和可调节的。求解时间—资源协调问题较为困难。但其目的是在某些先后次序与资源约束条件下, 确定每个活动的时间使得项目完工时间和总的资源消耗费用尽可能地小。

建立在一个三阶段结构 (时间表-可行性-修正) 策略的基础上, 提出了一个求解时间—资源协调问题的折衷Lagrangian松弛算法。连续使用这个折衷Lagrangian松弛方法可以获得一个满意的可行解。

进一步研究的问题:求解时间—资源协调问题的更有效的算法;不确定环境条件下的时间-资源协调问题;具有可变资源的时间—资源协调问题等。

展示更多