扰动环境下非标自动化设备项目反应性调度*

刘珩达,王子阳,杨宏兵

(苏州大学机电工程学院,苏州 215137)

0 引言

随着项目管理理论研究成果不断实践发展,在项目实施过程中,无法准确预见的不确定因素很多,尤其是在非标设备项目中,这也逐渐成为项目管理的一个重要研究领域。其中反应性调度方法为该领域最新的研究分支。

应对扰动的方案研究的必要性源自于项目的实际实施过程中,原先通过项目调度得到的基准计划时常会受到各式各样不确定因素的扰动[1],以非标设备项目为例,非标件供应商供货不及时、设计临时变更、作业所需资源判断失误以及资源的短缺等[2-4]。这些扰动的存在,使得管理人员在项目的实施过程中需要依照基准计划根据扰动做出调整,所以引入反应性调度就是应对这些未曾预料到的扰动。通过对原有计划的迅速调整及修复甚至重新调度,要求计划满足当前以及后续的约束要求,并减轻在项目实施过程中突发因素造成的扰动对项目过程带来的损害[5-8]。目前,反应性项目调度方法主要分为完全重新调度以及修复性调度。

由于生产活动十分依赖项目调度计划,调度计划的质量要求突发状况下对原有计划进行完全重新调度,即将未完成的作业看作一个新的项目按照某些评价指标对他进行新一轮的调度。如YANG[9]以工期最小化为目标,利用算法进行重新调度,由于希望新计划能够与原有计划尽量保持一致,尽量少的作业变动数量[10]、尽量小的提前/延迟成本[11]都会是反应性项目调度的目标。SERVRANCKX等[12]创建了多个备份计划,以应对项目进度中的意外更改,在存在不确定性的情况下,可以在不同的决策时刻在这些替代时间表之间进行切换。蒋淳等[13]提出考虑工人资源的项目型产品装配作业调度模型,以最小项目总工期为目标设计混合算法求解工程案例。卢睿等[14]基于局部搜索算法,以最小化提前/延迟期为目标求解该类问题。由于完全重新调度耗时较长,而反应性调度追求快速响应,提高重新调度的速度使之在管理人员接受程度内是其主要的研究方向。

1 问题描述

企业在制定好项目调度计划后,即刻开始投入实施装配。由于非标自动化设备的特殊性,客户定制化需求时有变更,因此导致设计上的变更,从而增加该作业环节先前预计的作业量,延长其作业周期。此外,企业众多非标件由供应商提供,企业无法对其供应商生产过程进行全程的监控,确保其供货进度与企业生产活动进度保持一致,供应商突发的供货延迟导致后续作业环节往往由于资源受限无法在规定时间进行,同理,人力资源也有类似突发状况。为应对以上问题,一是对制定的基准调度计划进行优化,使其拥有一定的抗扰动能力,这里可以理解为提高基准计划的鲁棒性;二是立即对此采取措施,对基准计划进行修复或重排,即反应性项目调度。

2 模型建立

(1)参数。I是计划期间内项目总数,J是单个项目内作业总数,VIJ是计划期间内所有作业集合,|VIJ|是计划期间内所有作业总数,M是可选的作业实施模式数量,R是项目涉及的资源种数,Fi是各项目的交期,T是整个计划周期,Eij是作业ij在各个作业模式选定后的最早开始时间(ij∈IJ),Lij是作业ij在各个作业模式选定后的最晚开始时间(ij∈IJ),dijm是作业ij在模式m下完工所需时间,Nr是资源r的数量总额(r∈R),rijm是在模式m下完成作业ij所需资源r的数量,Ti是项目i的实际完工时间,Nrt是时间t时对资源r的需求量,Sij是作业ij开始时间(ij∈IJ),Fij是作业ij结束时间(ij∈IJ),mij是作业ij选用的作业模式。

由于作业顺序约束的存在,在整个项目调度周期内每一项作业ij(i=1,2,…,I,j=1,…,J)的紧前作业集合为Pij,本文将各项作业开始时间与其所有紧前作业完成的最晚时间之间的时间差作为各项作业拥有的时间缓冲,Δij为作业ij所拥有的时间缓冲:

(1)

设定各项作业的时间缓冲值与其分配的权重系数乘积之和为研究的鲁棒系数从根据企业对各个项目长期的历史记录,每个项目中各个作业时间的均值μj以及标准差σj,基于作业时间标准差σj以及各项项目的权重ωi为每个作业定义一个权重系数ρij:

(2)

其中,ρij越大,该作业的变化性越高,其对基准计划的影响就越大,所以ρij也可以理解为作业ij上的单位时间缓冲对基准计划鲁棒性的贡献,而时间缓冲Δij对基准计划鲁棒性的总贡献即为Δijρij。

在强调效率的项目调度计划实施过程中必不可少需要利用反应性调度对突发状况快速做出响应。事实上,在反应性调度的实施过程中,各作业的作业时间是按照它们之间的逻辑关系,依次由随机变量变成确定值的。由于扰动环境下突发状况的影响,在扰动发生的时刻,原项目调度计划内的作业,分为3个集合:①在该时刻已经完成的作业集合FT;②正在进行的作业集合PT;③尚未开始的作业集合UT,而本文研究的是在突发扰动的状况下如何快速调整PT以及UT集合内的作业,调整原有的基准调度计划使之满足当前的运行要求。

(2)反应性调度模型。由于是多模式项目调度问题,作业的变动不仅考虑其作业开始时间的延期或提前引起的成本损失,同时也要考虑作业模式变动引起的成本损失,因此以上两个成本最小化建立反应性调度模型,目标为:

(3)

(4)

s.t.

Eij≤Sij≤Lij,∀i∈I,j∈J

(5)

Sij≥max(Fij′+dij′m),∀i∈I,∀(j,j′)∈J×J,∀m∈M

(6)

(7)

Nrt

(8)

max(Sij+dijm-1)≤Fi,∀i∈I,∀j∈J,∀m∈M

(9)

zijt=1,Sij≤t≤Sij+dijm-1,∀i∈I,∀j∈J

(10)

(11)

xijr,yijij′,zijt∈{0,1}

(12)

值得注意的是,在反应性调度实施过程中,随着各作业时间依次由随机变量变成确定值,基准计划的调整可能不止一次。所以,上述反应性调度模型可能会反复多次地重复调用。在此需要特别强调的是,当每次利用上述模型对基准计划进行调整后,应将活动的基准开始时间更新为新得到的开始时间,作为计划下一次调整时的基准开始时间使用。

3 算法设计及优化

为了能达到快速响应的要求,设计双层嵌套变邻域搜索算法,上层算法对模式选择进行优化,下层在模式组合已定的情况下对作业开始时间选择进行寻优。

下层算法在模式组合已定的情况下,先对各个作业开始时间进行可选范围的缩小,以此大大减小不可行解出现的概率,这样可以理解为下层算法在各个作业开始时间可选的邻域内进行搜索,而作业模式的可选项已有限制,这样可以大大提高算法的搜索效率。

为了扩大算法的搜索能力,对变邻域算法中的关键扰动因子进行设置,算法将扰动因子设计为此次迭代过程中将有n个作业会进行模式或作业时间的随机邻域选择,n小于或等于需要重新进行调度的作业数量。通过随机确定需要进行调整的作业数量,随机选取作业,再随机对其作业模式或作业开始时间进行调整以提高算法的搜索能力,其具体的步骤为:

步骤1:参数初始化,将上层算法迭代计数器重置为0,随机生成一个可行解作为初始解;

步骤2:随机生成需调整的作业数量,按其随机挑选相应数量作业改变作业模式,计算模式转换成本;

步骤3:将下层算法迭代计数器重置为0,根据生成模式组合计算各作业开始时间选择区间;

步骤4:随机生成需调整的作业数量,按其随机挑选相应数量作业改变作业开始时间,计算作业时间变动成本并记录;

步骤5:判断下层算法是否满足迭代终止条件,若不符合跳转步骤3,若符合输出该模式下最优解,结合模式转换成本与初始解进行对比,若由于初始解则代替初始解跳转步骤2,否则保留初始解跳转步骤2;

步骤6:判断上层算法是否满足迭代终止条件,若满足终止运算。

为了便于理解,图1为算法流程图详细展示其算法流程。为了能满足算法的收敛性,对下层进行测试得到作业时间变动成本收敛图,如图2所示。

图1 算法流程图

图2 下层算法收敛图

由此可见下层算法在迭代到100次左右时开始收敛,在满足算法收敛的同时提高算法运行效率设置下层算法迭代次数k=200。

设定上层算法迭代次数IT为100,1000和10 000,子算法层参数设定为迭代上限k=200。GD表示收敛性评价指标,值越小收敛性越好,SP表示空间的均匀性评价指标。由表1可以看出,迭代次数和算法运行时间呈倍数影响趋势。在低迭代次数的情况下(IT=100),算法已经拥有很好的收敛性,从SP结果来看,算法的迭代次数差异并不会对结果的均匀性产生影响。

表1 上层算法性能对比

故上层算法迭代次数IT=100,子算法迭代上限k=200,算法在拥有较高的运算性能的同时运算时间极短,满足生产活动中快速求解要求。

4 实验分析

实验以某企业非标自动化设备项目为背景,即各作业模式选择为[2,2,1,2,2,2,1,2,1],开始时间选择为[0,0,2,3,6,3,10,12,14],设定第7天两类资源可用量分别缩减为两个单位,且作业4在两种作业模式下作业时间分别增加1天,以模拟生产过程中可能发生的突发扰动。

利用设计的算法求得最终方案如表2所示,表3和表4分别为各方案的项目甘特图,图3为各方案的资源负载情况。

表2 帕累托解集具体方案

表3 方案1项目甘特图

表4 方案2项目甘特图

(a) 方案1资源负载情况 (b) 方案2资源负载情况图3 各方案资源负载情况

以上工作为验证算法的可行性,为了验证其(简称VNS)优越性,选取文献中出现频率较高的遗传算法(GA)、模拟退火算法(SA)、禁忌搜索算法(TS)进行对比,对比结果如表5所示。由表5及图4可知,4种算法在求解质量上没有明显差距,但在运算时间上,本文设计算法拥有明显优势,相较于遗传算法(GA)、模拟退火算法(SA)、禁忌搜索算法(TS),其运算速度提升62.9%、46.2%以及55.0%,由此可见本文设计的算法在求解该问题上的优越性。

表5 算法结果性能对比

图4 算法结果性能对比

5 结论

非标自动化设备项目因内外环境频繁扰动导致其执行过程中经常面临快速重调度的需求,在分析了作业延期或提前以及模式变更引发成本损失的基础上,建立了资源受限的多模式项目反应性调度模型。为了快速求解获得项目调度方案,设计了一种新颖的双层嵌套变邻域搜索算法,上下层算法分别对模式选择和作业开始时间进行优化,同时设计了一种高效的扰动算子,有效提升了算法的搜索效率。最后以某非标自动化设备企业的实际项目为例,通过与遗传算法、模拟退火算法和禁忌搜索算法进行了实验对比,在求解质量没有明显差距的情况下,所提出的双层嵌套变邻域搜索算法在求解效率上分别提升了62.9%、46.2%以及55.0%,实验结果验证了算法的有效性和性能的优越性,能够满足非标自动化设备企业的实际生产需求。