《1 引言》
1 引言
结构项目计划和时间表的主要目标通常是在项目活动的某种先后次序和有效资源的限制条件下确定项目的完工时间, 使得项目总的完工费用极小
在项目时间表里, 文献
《2 时间—资源权衡协调多目标优化决策模型》
2 时间—资源权衡协调多目标优化决策模型
时间—资源协调项目时间表问题主要涉及到满足有效资源和先后次序约束下的时间表、资源费用和项目活动的时间。其目标是在满足项目活动的完工时间条件下极小的总资源费用。假设项目没有抢断约束, 其每个活动时间是未知的。因此这些时间不超过活动的正常时间。并假设资源费用与项目时间具有某种递减函数关系, 如线性或其他函数关系。在模型中将用到如下一些符号:
N 项目的活动数,
K 可更新资源类型数,
Tj 活动j (j=1, 2, …, N) 的完工时间,
H 表示具有完工-开始先后次序的活动对集合, 即项目网络中的事件数,
St 于时间区间 (t-1, t]={iTi<t≤Ti+ti}进行中的活动数,
TNj 活动j的正常时间 (normal time) ,
TCj 活动j的应急时间 (crash time) ,
tj 活动j的时间变量, 它取值于TNj-TCj和TNj之间的整数, 即TNj-TCj≤tj≤TNj,
Rkt 在时间t时刻资源类型k (k=1, 2, …, K) 的所有有效资源量,
ajk (tj) 活动j在时间段tj需求资源类型k整个费用量, 其资源类型k的单位价格为ak,
其中rjk为单位时间里需求第k种类型资源量。 不失一般性, 假设活动1表示项目的开始, 而活动N+1是哑元表示项目的完工。哑元活动不需求任何资源也没有时间要求, 即tN+1=0和
时间-资源协调问题的最优模型可以表示为:
Minz1=TN+1 (1)
式 (1) 和式 (2) 表明问题是一个二目标规划模型, 它们分别是极小化项目的完工时间与极小化资源消耗的总费用。约束条件式 (3) 保证活动的先后次序被满足。约束条件式 (4) 表明活动的时间变量是有界的。约束条件式 (5) 刻划了任何时刻资源需求的总和不超过它们的有效资源量。
如果删去第二个目标问题将变为具有可变时间的资源受限制的项目时间表问题:
《3 资源约束的Lagrangian松弛形式》
3 资源约束的Lagrangian松弛形式
根据松弛方法, 考虑对应于资源约束式 (5) 的Lagrangian松弛形式, 通过改变对应于资源约束的乘子将影响资源的平滑结果。因此, 资源的使用情况随时都被受到监控。
设λk是对应于资源约束式 (5) 的Lagrangian乘子 (显见λk是非负的) , 那么有Lagrangian函数
为了方便起见, 考虑单目标问题:
因此规划式 (8) 的对偶问题为
其中对偶函数为
优化问题式 (9) 称为对应于原2个目标优化问题的部分对偶问题。显然, 对偶函数d (λ, R) 对于单个资源类型k的对偶目标是可分的。根据Lagrangian乘子的意义, λkt可解释为资源类型k在时刻t的影子价格, 每个子问题Kk可被解释为一个效益极大化问题 (即浪费的资源尽可能地少) 。
用‘两公司´ 模型解释对偶问题式 (9) :公司P的目标为极小化资源成本效益 (被消耗资源总的费用极小) , 在时刻t, 面临着资源供应Rkt (为方便起见将省略下标t) , 在不影响项目排序的完工时间的前提下, 尽可能出售多余的有效资源给公司Q。公司Q为了自己的利益 (极小化项目的完工时间) , 以价格λkt向公司P购买大量的有效资源。由于公司P的目标是为了极小化被消耗的资源总费用, 因此它可能出售多余的有效资源。为了取得公司的极大利益 (项目尽可能早的完工) , 公司Q通过调整资源价格向公司P购买更多的剩余资源。
众所周知, Lagrangian松弛算法是逐步极大对偶问题的。在每次迭代过程中, 不断修正Lagrangian乘子λkt, 利用具有新乘子值的资源子问题去计算d (λ, R) 。根据上面的解释和资源受限制的项目时间表问题的某些特征, 可以得到如下事实:
1) 这种两公司模型可以作为二人对策问题。公司Q (参与人1) 为极小化项目时间表的完工时间, 根据完全理想的信息情况, 经过不断地协商讨论首先确定价格λkt;公司P (选手2) 在观察到这个λkt值后, 首先考虑极小被消耗资源总费用与极小项目时间表的完工时间的平衡情况, 然后做出自己的最优选择tj (活动的时间) 。
2) 根据数学规划中最优互补松弛条件和Lagrange乘子的某些特征, 如果在迭代中乘子λkt都是正值, 那么资源将被得到充分地使用。这是非常理想的情况, 因为在取得被消耗资源总费用极小化的同时, 也获得了项目时间表的极小化完工时间。为了极小化项目完工时间和被消耗资源的总费用, 只有不断增加Lagrange乘子使得资源尽可能地获得充分地使用。
3) 在资源与时间的协调过程中, 资源的使用与平滑问题将得到有效地监控。这是因为当考虑到资源约束的互补松弛条件后, 在项目的完工时间和被消耗资源的总费用极小的过程中, 通过平衡资源的使用与活动的时间选择, 可以客观有效地调节Lagrane乘子。
4) 二目标问题隐含着对相互冲突目标的优化问题。为了使项目的消耗资源的总费用极小, 必须选择活动的最大时间使得尽可能少地使用有效资源。同时, 为了使得项目的完工时间极小, 应该尽可能多地减少活动的时间 (选择较少的活动时间) 。这将导致增加有效资源的使用量。这就需要不断调整资源使用量与活动时间的关系, 从而获得一个最优或近似最优的结果。
《4 求解方法》
4 求解方法
为了求解时间—资源协调问题, 提出一个建立在三阶段策略基础上的折衷Lagrangian松弛问题的算法。详细算法过程:
初始化过程 确定项目活动的时间tj (j=1, 2, …, N) 。 在时间区间Tj=TCi, TNi随机产生活动j的一个工期 (∀j ) ; 或置tj=TN, (∀j ) 。
阶段1 求解具有可变时间的资源受限制的项目时间表问题式 (6) 。利用某些有效算法 (如资源约束Lagrangian松弛方法
如果项目的完工时间小于项目的工期则转阶段2;否则将减少某些活动 (如需求资源数与活动时间乘积较大的活动) 的时间 (使之位于时间区间Tj) 重新求解问题式 (6) 。倘若不能找到一个可行时间表, 则停止计算, 无需进入下阶段的计算。
阶段2 检验当前的解是否违反资源限制。如果没有资源冲突则把具有最小的
阶段3 改进资源的使用情况, 主要目的是修正或调整某些活动的时间, 使得资源浪费的情况得到改善, 由此而来可减少项目的完工时间。令
Step 1 对i∈St2, 计算
倘若在集合St2中至少有两个相同, 那么选取具有较小值的指标 (时间) 。当然, 它的时间区间必须是一点。
Step 2 修正活动的时间, 需要考虑两种情况:
1) I2=1。设St2∩St2+1=∅, 如果tCi2≠{ti2}, 置
2) I2≥2或St2∩St2+1≠∅。不失一般性, 可得如下排列:
对j=1, 2, …, I2, 选择γij使得γi2≥…≥γiI2≥0与tiI2≥γiI2+tCiI2 成立, 然后修正
终止条件的检验 如果满足下列三条件之一, 计算终止。否则转到阶段1。
1) 如果对所有的t和k有
2) 满足预先给定的阶段迭代数。
3) 对t
对资源类型k在t时刻Ykt可以表示资源的平均使用量
当活动时间减少时, 项目的完工时间将减少但是资源消耗的总费用将增加。
稍后将看到, 减少资源约束条件下的活动时间并不总是能够减少项目的工期。因此, 上面描述的终止条件式 (3) 是可行的。
在执行算法阶段2时, RGkt的非负性必定会取得, 即资源不足的情况不可能发生。当发生资源浪费的情况时, 阶段3的主要任务是调整活动时间。为了得到一个折衷的结果, 在协调过程中, 主要是通过重复调整减少项目工期的效益与增加使用有效资源的费用之间关系来完成。
《5 一个算例》
5 一个算例
为了显示所提出的模型和算法, 一个要求两种资源类型的简单项目网络模型见图1, 所有活动的正常时间与应急时间如表1所示。
Table 1 Bounds of activity duration
《表1》
Activity | Crash (tC) | Normal (tN) |
A (1) | 1 | 3 |
B (2) | 2 | 4 |
C (3) | 3 | 3 |
D (4) | 4 | 6 |
E (5) | 3 | 5 |
F (6) | 2 | 2 |
为简单起见, 只讨论资源费用与活动时间具有如下线性关系:
非负参数bkj, ckj如表2所示。需求的资源是R1=10和R2=6。活动需求的资源与时间的关系是逐段线性函数 (见表3) 。
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 |
计算过程描述如下:
Step 1 初始化置所有活动的时间为正常时间。初始时间与资源如表4所示。
Step 2 由Step1得项目的完工时间为z1=20个时间单位, 其时间表为:A—D—B—C //E—F, 其中符号C//E表示活动C与E是并行关系。
Step 3 经过Step 2的计算, 目标函数z2=36.63单位。
Step 4 由Step 3的计算, 可以选取活动的时间及其每单位时间需求的资源量如表5所示。返回Step 1 (不存在qi2使得I2≥2和St2∩St2+1≠∅) 。
Step 5 经计算, 项目的时间表与Step 2的结果相同, 项目的完工时间为z1=19时间单位, 目标函数z2=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, 项目的工期z1分别是21和22个时间单位, 总的资源费用分别是44.18单位和40.95单位。显然, 这些项目工期都大于前面所得到的结果。这个结论表明:在资源约束条件下, 项目的完工时间并不随活动时间的减少而减少。
《6 结论》
6 结论
笔者所提出的时间—资源协调问题新的数学模型, 不同于其他模型 (如参考文献
建立在一个三阶段结构 (时间表-可行性-修正) 策略的基础上, 提出了一个求解时间—资源协调问题的折衷Lagrangian松弛算法。连续使用这个折衷Lagrangian松弛方法可以获得一个满意的可行解。
进一步研究的问题:求解时间—资源协调问题的更有效的算法;不确定环境条件下的时间-资源协调问题;具有可变资源的时间—资源协调问题等。