文摘

我们研究的项目预算版本随机离散时间/成本权衡问题(SDTCTP-B)调度的鲁棒性的观点。考虑到项目预算和一组活动执行模式,每个都有不确定的活动时间和成本,SDTCTP-B的目标是最小化最大完工时间预计项目通过确定每个活动的模式和起始时间。通过使用区间数建模活动时间和成本,我们建议积极的项目调度模型SDTCTP-B基于鲁棒优化的理论。我们的模型可以生成健壮的基线计划,使自由调节水平的鲁棒性。我们将我们的模型转换成其强劲的对手使用形式的混合整数规划模型。广泛的实验是进行大量的随机生成的网络来验证我们的模型。此外,模拟用于调查之间的权衡的优点和缺点稳健积极的项目调度模型。

1。介绍

在项目管理中,项目持续时间通常可以缩短关键活动分配更多资源。资源的数量往往是离散的,如工人和机器的数量。这些资源通常是作为不可再生资源,衡量资本(或成本),导致离散时间/成本权衡问题(DTCTP) [1];哈维和帕特森(2]和Hindelang Muth [3DTCTP)首次提出,是一种特殊情况下的多模式资源受限项目调度问题4]。

在确定性DTCTP,每个活动都有多个执行模式,具有特定的时间和成本组合。目标函数的类型,可以分为三个版本:DTCTP最后期限问题(DTCTP-D),预算问题(DTCTP-B)和时间/成本平衡曲线问题(DTCTP-C)。DTCTP-D,给定一组模式和一个项目的最后期限,目标是最小化项目总成本通过指定为每个活动执行模式。DTCTP-B,项目预算,目标是确定最大完工时间最小化项目的模式。DTCTP-C,目标是确定帕累托曲线,同时最大限度地减少项目的成本和时间。

一旦确定每个活动的模式,我们可以确定基线进度通过计算每个活动的最早开始时间按照关键路径方法(CPM)。

然而,在项目执行过程中,由于相当大的不确定性,最优基线计划是基于确定性环境和获得完整的信息可能会偏离我们的预期甚至变得不可行。可能的不确定性的来源可能是机械的短缺,延期交货的材料,没有工人的情况下,汇率的波动,等等(5,6]。因此,进度延误和/或预算超支等问题可能发生和项目时间和成本目标将受到威胁。因此,迫切需要新的程序不确定性下的DTCTP获得项目计划不中断。

最近的研究更加关注随机DTCTP (SDTCTP),占不确定性将活动的时间和成本视为随机变量,优化项目预期性能的目的。早该领域的研究人员,Gutjahr et al。7)提出了一种随机和过程解决DTCTP期限问题的基础上,假设每个活动的时代是相互独立的随机变量。Laslo [8]使用分形方法构造时间/成本曲线为一个随机的活动持续时间。科恩et al。9)实现鲁棒优化来解决时间/成本权衡问题。柯et al。10)利用机会约束规划和dependent-chance编程模型随机DTCTP;作者设计了一种智能算法搜索最优时间表,同时平衡项目时间和成本。Klerides和Hadjiconstantinou11)提出了一种基于路径两阶段随机整数规划的方法来决定如何以及何时执行每个活动项目持续时间或成本最小化使用意识到活动持续时间。马等。12]研究了随机time-cost-quality权衡问题的活动持续时间不确定,开发了一种混合遗传算法。

然而,上述研究论文主要集中在优化系统性能在平均意义上,这些方法不能保证之前的性能基线计划一个项目执行期间。因此,确定一个健壮的基线计划下的不确定性日益引起学者们的注意。实现一个健壮的基线计划,使用鲁棒优化是一种自然选择。鲁棒优化可以确定一个解决方案与某些优化最坏性能鲁棒性的系统。虽然鲁棒优化已被用于解决一些经典的项目调度问题(13,14),小的努力已经应用于研究SDTCTP。我们所知,Hazır et al。6)是唯一的研究文章,结合SDTCTP和鲁棒优化方法。Hazır等人提出三种鲁棒优化模型,在成本不确定性建模通过间隔SDTCTP期限问题。他们的模型的目的是尽量减少突发事件对项目性能的影响。他们的模型的局限性,作业成本仍认为是确定性的,只有目标函数中的参数不确定性(即。约束的参数确定的)。

我们最好的知识,解决时间和cost-uncertainty和应用鲁棒优化解决SDTCTP-B没有考虑在项目调度和鲁棒优化文学。本文的贡献如下。(1)我们提出了一种主动调度模型SDTCTP预算问题(SDTCTP-B)基于鲁棒优化理论。我们的模型使用区间数模型不确定的活动时间和成本可以按照任何类型的概率分布。我们的模型的目标是产生一个稳定的基线计划可以占的一些不确定性在项目执行期间确保,尽可能,每个活动开始于各自的计划开始时间。(2)我们对我们的模型进行了详细的实验分析。我们使用实验设计随机生成大量的实例来验证我们的模型。此外,鲁棒优化改善进度稳定延长项目时间为代价的。因此,我们使用模拟调查之间的权衡鲁棒优化的优点和缺点。具体地说,我们分析了活动的数量的影响,网络秩序的力量,和模式的数量安排稳定利用离散系统仿真。

本文组织如下。部分2提供了一个SDTCTP的描述。节3,我们用区间数模型的不确定参数和现在积极的解决SDTCTP-B基于鲁棒优化模型。考虑到该模型的非线性特点,我们把我们的模型转化为其强劲的对手,有一个混合整数线性规划模型,并使用branch-and-cut算法解决模型。节4,我们目前的实验结果。最后,部分5总结了纸。

2。问题描述

随机离散时间/成本权衡问题可以描述如下。一个项目网络在activity-on-node格式表示,节点的设置吗表示活动和导演弧的集合代表finish-start,无滞后优先关系。单头节点的节点拓扑编号1到单端的节点,节点1和代表两个虚拟活动。活动的时间和成本是随机变量,表示吗和,分别。活动,代表的设置模式。每个活动有模式,由一对duration-cost特征,。持续时间的一个活动是一个离散,nonincreasing功能单一的不可再生资源的数量致力于它;也就是说,如果那么,我们预期的持续时间和成本和。我们假设1和虚拟活动只有一个零时间/成本的执行模式。

考虑到项目预算,SDTCTP-B的目标是最小化最大完工时间预计项目的分配模式每个活动和确定开始时间每个活动。如果我们用随机时间和成本的活动由他们最有可能的值和分别对上述问题,SDTCTP将成为确定性DTCTP。对于DTCTP-B,我们有以下整数规划模型: 在哪里和决策变量。是0 - 1变量,确定是否选择一个活动的模式。目标函数(1)最小化假结束节点的开始时间,相当于最小化最大完工时间项目。方程(2)确保每个活动执行模式只有一个被选中。方程(3)定义了活动的优先约束关系。方程(4)确保项目总成本不超过预算。方程(5)确保每个活动的开始时间是负的。预算的DTCTP是强np困难问题1,15,16]。

面对每一个活动的持续时间和成本的不确定性,上述确定性模型生成的基线计划所确定的预计不会被执行,从而导致项目未能达到预期的目标。不确定性时,我们注意到,不确定参数主要影响约束(3)和(4)。因此,在下一节中,我们作为区间数模型的不确定参数和发展积极的SDTCTP-B基于鲁棒优化调度模型,从而获得一个健壮的基线计划。

3所示。主动为SDTCTP-B调度模型

3.1。建模不确定参数为区间数

在实践中,它通常是决策者更容易估计的范围和最可能的价值活动的持续时间和成本,而不是他们的概率分布。因此,我们利用区间数模型不确定活动的时间和成本。为模式,让和最可能的价值活动的持续时间和成本分别;和取一个值的区间和分别(例如,,)。我们定义的最大偏差活动持续时间和成本和分别代表之间的最大区别活动持续时间和成本计划和实际的活动持续时间和成本,可以容忍的决策者。

3.2。主动调度模型

对于每个活动,我们引入一个参数未必是一个整数,这需要在一个值区间。是用来调整我们的模型的鲁棒性(即。,保守主义的解决方案)。对于每个活动,我们假设模式的值的上界,,一个模式可以偏离值和,剩下的模式将他们最可能的值。

我们主动SDTCTP-B基于鲁棒优化调度模型17,18)如下:

上述模型介绍了不确定参数到确定性DTCTP模型,能够生成健壮的解决方案。是的一个子集属于,模式在最坏的情况下的值。的基数是由。此外,目标函数(7)是一个确定性的函数,而不是一个期望的功能。因此,计算耗时的期望是可以避免的。

我们的模型有两个主要优势。第一个优势是,鲁棒性得到时间表可以自由调整。参数的值就越大,级别越高的鲁棒性。如果,该模型将成为确定性DTCTP模型。第二个优势是,尽管该模型是非线性的,它可以很容易地重新构造一个等价的线性混合整数规划(MIP)模型根据鲁棒优化理论(17,18]。获得相当于MIP模型,我们首先。

意味着我们需要确定一个子集包括元素,这样是最大化。因此,我们引入决策变量,,。给定一个向量,等于下列线性规划的目标函数值:

问题的约束(10)接踵而至,结果最优目标函数值等于。很明显,线性规划问题(10)有一个最佳的解决方案的决策变量1和剩余的价值0的值。

的对偶问题(10)是 在哪里和是双变量。根据强对偶性,因为问题(10)有一个最优解,然后问题(11)也有一个最优解,最优值是相同的。此外,等于问题的目标函数值(11)。

同样,“马克斯”的一部分(9)可以转化为下列线性规划模型:

然后我们可以获得相当于混合整数线性规划模型,模型1用(11)和(12):

3.3。例子

我们用一个例子项目网络图1说明我们的模型。0和5都是虚拟的活动活动。1和2的活动只有一个模式。活动3和4有两种模式。我们假设项目预算。

表1列出所有可能的不同的值的组合方式。第一列中列出了值。第二和第三列显示所选模式3和4的活动。列标记为“总成本”显示了项目总成本的选择活动模式。列标记为“考”表示目标函数值(即。最大完工时间,项目)。列标注“可行的”显示了给定的模式组合是可行的,鉴于75年的预算限制。

如表所示1,当,所有的模式最有可能使用他们的价值观和我们有两个解决方案的考13。当,该模型是一个健壮的模型,我们有三个解决方案的考13。在三个解决方案,其中两个是一样的情况第三个(表中相应的行1大胆)可以被视为一个健壮的解决方案。健壮的解决方案,因为活动的持续时间4最坏值,这将导致更低的延迟项目如果活动4的概率是不确定因素而中断。当,所有模式使用他们最坏的价值观和我们有一个解决方案的考15。的最大使项目进度最稳健,在最大完工时间接受一个更大的项目的价格。

4所示。计算实验

我们有随机生成大量的问题实例来验证我们的模型。部分4.1描述如何生成这些实例。接下来,优化结果与报道不同的参数设置部分4.2。部分4.3描述了使用仿真研究不同项目网络参数对进度的影响稳定。Matlab的实验版本R2010b和英特尔酷睿i5 2.40 GHz便携式计算机上运行Windows 7。我们使用Matlab调用内置的12.4最大化策略解决MIP branch-and-cut算法。

4.1。数据生成和设置

RanGen(19],它可以产生强烈的随机网络activity-on-the-node格式,用于构建180个测试实例使用的参数设置表2。RanGen主要使用两个参数来定义网络结构:网络规模()和秩序力量(OS)。网络规模指定的数量在项目活动网络。秩序力量操作系统优先级关系的数量除以理论最大数量的优先关系网络。强度顺序描述了网络密度。操作系统的价值越大,网络密度越高。Herroelen和De Reyck20.]表明操作系统比其他常用的措施(例如,网络的复杂性,采用PSPLIB [21描述网络拓扑时])。

指定3设置活动的数量,2设置执行模式的数量,和3设置操作系统,我们为每个实例生成10个问题3×2×3参数设置,导致总共180个实例。

我们还需要生成最可能的值为每个活动的持续时间和成本。在DTCTP,成本函数的类型可以是线性的,凸、凹或随机的。我们研究了随机情况下,这是更普遍。后Demeulemeester et al。19),一个活动的模式在以下方式生成。首先,模式的数量根据模式确定参数表中列出2。接下来,不同的数字从离散均匀分布随机选择形成了持续时间按升序排序。确定成本,从正常时间模式,其相应的成本从离散均匀分布随机选择。通过随机选择一个斜坡从离散均匀分布的成本,我们可以计算下一个模式,我们重复这个过程逐步直到最大成本的模式。

我们的模型处理数据不确定,所以我们生成的活动持续时间和成本的最大偏差,让和,在那里。此外,项目预算计算,在那里,,。

4.2。实验结果

的参数代表我们的模型的鲁棒性。研究不同的影响在解决方案,我们设置5个不同的值,在那里和。我们看到的价值很小,因为我们发现甚至一点点的偏差影响进度高稳定(见下一节)。请注意,我们的模型就变成了确定性DTCTP模型时。我们解决了180个问题实例300秒的CPU时间限制;表中列出的结果3。列”操作系统“代表活动的数量,代表秩序的力量,””表示模式的数量。列“Avg”、“最小值”和“Max”提供平均、最小和最大目标函数值,分别。“%”列显示最佳解决问题的百分比。

结果在表3表明,随着订单的增加力量,目标函数值(即。,project makespan) increases, while the number of modes exhibits a contrary behavior. The reason for this behavior is that a higher order strength value means that more precedence relationships are involved, resulting in a longer project duration. More modes provide more choices for the durations of the activities, thus making it possible to shorten the project duration.

小问题实例(在300秒内可以解决最优。增加了活动的数量减少的比例问题实例优化解决。我们也观察到更大的价值,比例越低解决优化问题的实例。反映了之间的权衡的鲁棒性和最优的解决方案。一个更大的结果在一个更稳定的长期项目时间进度为代价的。此外,相比于确定性模型(),由于许多辅助变量的引入,解决了鲁棒优化模型需要更多的时间,从而导致更少的最佳解决方案。因此,一个更小的伴随着较低的计算要求。

4.3。不同的因素对进度的影响稳定

鲁棒优化提高了调度的鲁棒性的项目持续时间延长。因此,我们感兴趣的是之间的权衡的优点(改善进度稳定)和缺点(增加项目持续时间)的鲁棒优化。具体来说,从稳定成本的角度,我们使用模拟调查项目的影响(即网络结构参数。活动的数量,订单强度和模式)计划的数量稳定。

4.3.1。仿真设计

我们使用稳定的成本 测量计划的稳定性。被定义为预期的绝对偏差的加权和计划和真正意识到活动开始时间(22,23]: 在哪里活动的计划开始时间吗在基线计划,是一个随机变量表示活动的实际开始时间,代表了cost-per-time单位发生的情况,实际开始时间晚于计划时间活动,。的价值反映出难改变基线进度或开始一个活动是多么的重要。更健壮的一个时间表,小成本相应的稳定。

不现实的使用全因子试验分析不同因素对进度的影响稳定(24]。相反,我们专注于不同的主要影响因素。当我们研究一个因素的影响平均稳定成本,我们保持其他因素固定在某一水平。

仿真策略如下。(1)权重从均匀分布吗。(2)活动方式是由我们主动调度模型的解决方案。(3)活动持续时间是从三角形分布,在那里,,。注意,因为我们的模型可以处理任何类型的分布,我们也可以画出活动持续时间从其他发行版。(4)我们使用铁路调度策略来确定实际的活动开始时间。在铁路调度,实际开始时间总是晚于或等于计划开始时间(火车时刻表,一样飞行调度,等等)。因此,优先关系的条件已经满足,计算根据 在哪里活动的开始时间吗通过解决我们主动调度模型。

为每个实例在我们的数据集,仿真复制的数量设置为100。注意在以下提到的稳定成本总是平均值。

4.3.2。活动的数量的影响

图2显示活动的数量的影响平均进度稳定成本,而另两个因素是固定的(,)。在图2,设在代表。有两个相互重合。的设在左边显示了稳定成本和右边的表示(即目标函数值。最大完工时间、项目)。传奇的人物2字母“s”和“o”在括号中意味着相应的行对应于稳定成本和目标函数值,分别。请注意,由于我们不能为大多数情况下,找到最优的解决方案我们的期限内,结果数据集将不会被包括在本节,以确保分析的有效性。

对于每一个鲁棒性水平活动的人数增加,稳定增加的成本。换句话说,活动数量越大,越不稳定。

我们看到,虽然实际的区别和很小,它已经足以严重降低稳定成本什么时候改变从来。为有趣的是,的影响在进度稳定成本就变得很弱等于或大于。然而,的影响目标函数值仍然是积极的。这意味着对于小规模项目,没有必要使用高值,因为这不会显著降低进度稳定成本。相反,高值在这种情况下将延长项目时间。

4.3.3。影响订单的力量

图3表示顺序的影响强度平均进度稳定成本,而另两个因素是固定的(,)。订单的影响强度的稳定性依赖于成本稳健性水平。当强度低,订单稳定成本具有积极的影响。然而,这种影响就弱的增加。我们可以得出这样的结论:当我们选择一个相对较高的值,我们可以少关注项目优先级的密度关系由于疲软的影响强度。

一个有趣的发现是,当增加,增加的大小(即目标函数值。、项目持续时间)对不同强度基本上是相同的。然而,的大小相应的进度稳定成本的变化更大,尤其是当强度高的水平(例如,)。换句话说,当项目的密度很高,一个时间表的稳定性可以通过使用我们大力加强积极的项目持续时间模型和相应的损失很小。

4.3.4。模式的数量的影响

图4给的影响模式的数量平均进度稳定成本,而另两个因素是固定的(,)。结果如图4并不少见。对于每一个鲁棒性水平模式的数量的增加,稳定增加的成本。换句话说,模式一个活动可以选择越多,计划变得更不稳定。

此外,在大多数情况下,对于任何因子(活动的数量、强度顺序或模式)的数量,数据2,3,4也揭示了一个更大的可靠性水平结果在一个较小的稳定成本,这是长期的项目持续时间的成本。这进一步证实了我们的结果部分4.2鲁棒性级别就越大更稳定的基线进度。

5。结论

在本文中,我们提出了一个主动调度模型为项目预算版本的随机离散时间/成本权衡问题基于鲁棒优化理论。计算经验随机生成数据集验证了我们的模型问题。我们还利用仿真分析不同项目网络参数对进度的影响稳定。

从随机的实验时间/成本平衡环境,我们得出这样的结论:(1)更大的值参数的鲁棒性水平导致一个更稳定的基线计划。然而,计划提高鲁棒性的项目持续时间延长。因此,是否采用鲁棒优化取决于决策者的偏好。但是,我们建议使用我们的方法时的密度高(即项目优先级关系。强度高的顺序)。因为在这种情况下,项目的损失时间获取一个健壮的时间表是非常小的。(2)项目持续时间和调度的鲁棒性非常敏感。即使是轻微的增加已经足以获得一个足够健壮的时间表。(3)在我们的主动模式,订单强度最大完工时间对项目产生积极的影响,而模式有负面影响。(4)在大多数情况下,增加活动的数量,订单的力量,和模式的数量,安排稳定性降低。然而,当是相对较高的,顺序的影响强度的进度稳定成本变得虚弱。这意味着我们可以忽略的因素当我们使用高价值秩序的力量。(5)对于小规模项目,很容易生成一个相当稳定的小计划。然而,对于较大规模的项目,我们必须增加结果安排足够健壮。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者感谢审查员提供有价值的建议,改善了摘要的质量。这项研究受到了美国国家科学基金会资助下的中国71271019,人文学科和社会科学的基础下教育部授予12 yja630158,和上海的软科学研究项目拨款14692105900。