带资源空窗期的资源投入型问题的建模与优化

陆志强，周皓雪

(同济大学 机械与能源工程学院，上海 201804)

基于精益思想的飞机移动式装配线已成为飞机装配生产的新模式，具有装配效率高、质量稳定、可按需批量生产等特点，近年来被世界各大航空制造企业竞相采用.实际上，对于每架飞机而言，移动式装配线上的总装任务调度问题具有装配工序繁多、装配任务复杂、装配过程受到多重约束限制等特点.调度过程可根据实际应用的目的抽象为资源受限项目调度问题(RCPSP)以及与之关联的资源投入型问题(RIP)两大类.前者与装配线的规划、设计和决策相关，而后者与装配线的运作决策关联.对装配线的日常运作决策而言，通常需要在给定工期的条件下，优化装配线的各类资源配置及分配使用，达到最小化资源投入总成本的目的，即资源投入型问题.对于一般装配线来说，装配线复杂度较低，工作可替代性强.飞机移动式装配线的工序繁琐复杂、工作专业性强，对于特殊人力资源要求极高.同时，整个装配周期较长，关键技术人员稀少并且可能存在不可用时间段，对于飞机装配生产线考虑资源利用区间是重要且必要的.因此，在基本RIP的基础上，考虑到飞机装配生产中某些关键资源具有提前已知的不可用时间段，即引入资源空窗期约束，提出带资源空窗期的资源投入型问题.

资源投入型问题作为RCPSP的对偶问题，最早由Möhring[1]引入，并且该问题被证明为NP-hard问题.以RCPSP的算法求解为基础，得到了求解该问题的图解精确算法.Drexl等[2]基于拉格朗日松弛和列生成方法为RIP提出了两个下界算法，并且通过算例实验与Möhring[1]的算法进行了比较.Rodrigues等[3]提出了一种改进型割平面法，通过启发式算法得到初始解并不断更新低界，缩小解空间，从而提高计算效率.由于精确算法只能求解小规模问题，因此大量国内外学者针对大规模问题提出启发式算法与元启发式算法.Song等[4]提出带局部搜索的进化算法，允许项目延期但是设有极高的延期惩罚.Myszkowski等[5]在混合蚁群算法中嵌入启发式优先级规则对资源进行分配.Van Peteghem等[6]提出了一种应用于RIP的人工免疫算法.He等[7]设计了基于动态优先级规则的启发式算法，并对任务开始时间决策区间内的所有位置进行评测.Qi等[8]提出了一种新的粒子群算法，在解码阶段设计了多种启发式规则以修复不可行解.由于现有考虑资源特点的RIP相关研究稀缺，因此带资源空窗期的RCPSP的研究方法对本研究具有参考意义.胡淑芳[9]针对资源时间窗和任务可拆分特性，设计了小规模单技能及多技能项目调度问题求解的分支定界算法.廖广瑞等[10]考虑资源的多技能和时间窗属性，设计了基于优先规则的Rollout求解算法，并嵌入了启发式资源分配方法对资源进行快速分配.綦方中等[11]研究了基于时间窗的多项目资源分配问题，提出了带时间窗参数以及惩罚因子的多项目管理资源分配模型.

从现有文献可以看出，对于RIP的研究范围仍偏重于基本问题，而基本RIP通常设有大量假设条件，属于较为理想化的纯理论问题，因此RIP的研究成果难以与更为复杂的实际生产过程有效结合.此外，从算法设计上来看，大部分启发式算法在任务开始时间的决策区间内取值时，计算效率不高，并且易限于局部考虑而忽略全局影响.常见的搜索算法可分为以下两类：一类以资源量进行编码，但这样编码容易导致资源上、下界差距较大，搜索效率低，难以找到结果较好的可行解；一类以任务开始时间进行编码，但这类编码大多数未考虑问题特点，搜索的方向性不强，导致算法效率低.基于此，在进行算法设计时重点考虑资源空窗期约束，首先提出求解RIP的启发式算法.区别于基本RIP，设计了非关键任务优先级、关键任务排入以及非关键任务调度的三阶段启发式算法,对模型进行求解.通过进一步的分析发现，启发式算法处理大规模算例时具有局限性，因此在启发式算法的基础上设计了以非关键任务优先级和关键任务开始时间为双链表编码的遗传算法，并将启发式规则嵌套在遗传算法的解码和评估阶段，提高了求解的精确性.最后，通过数值实验验证了启发式算法和遗传算法的有效性，同时证实了空窗期约束的存在对于算法设计具有影响.

1 问题描述及数学模型

1.1 问题描述

假设飞机装配项目由若干项任务构成，任务之间存在着一定的时序关系，任务的执行需要消耗相应的资源.记给定项目总工期为T，包含J项任务，每项任务j(j=1,2,…,J)的执行时间为tj，p(j)为第j项任务的紧前任务集合，s(j)为第j项任务的紧后任务集合，tES,j、tLS,j、tEF,j和tLF,j分别为任务j(j=1,2,…,J)的最早开始时间、最晚开始时间、最早结束时间以及最晚结束时间,tTF,j表示任务j开始时间的浮动长度,即tTF,j=tLS,j-tES,j.项目中使用的可更新资源种类为P，每种资源的单位使用成本为Cp(p=1,2,…,P).rjp表示任务j(j=1,2,…,J)需要的单位资源p(p=1,2,…,P)的数量,rj,max表示任务j需要的所有资源中需求量最大的资源值.关键资源pk在特定的一段或多段时间区域内不能工作，即资源的空窗期约束.Ae代表需要用到关键资源pk的任务集合.对时间进行离散化处理，模型的求解目标是优化各时刻t(t=1,2,…,T)每种资源p(p=1,2,…,P)的最大需求量Rtp的总成本.

模型中决策变量包括：xjt为0、1变量，1表示任务j(j=1,2,…,J)在时刻t被执行，否则取0；zjm为0、1变量，1表示任务j∈Ae在第m个非空窗期区间内完成，否则取0.

1.2 空窗期

在飞机装配的实际生产中，关键资源的使用时间往往不是连续的，某些时段可用，某些时段不可用，将这种约束称为资源空窗期约束.参考刘振元等[12]相关论文，对空窗期相关参数进行定义.

如图1所示，假设有M个空窗期，m=1,2,3,…,M，tb,m和te,m分别为第m个空窗期的开始和结束时间.在空窗期内资源可用数量为零，在非空窗期内资源可用数量为常数R0.lm表示第m个空窗期的长

图1 资源空窗期示意图

度，易得lm=te,m-tb,m；δ(m-1,m)表示第m个非空窗期的长度，易得δ(m-1,m)=tb,m-te,m-1.假设tb,0=te,0=0.

1.3 数学模型

目标函数为

(1)

约束为

(2)

(3)

(4)

(5)

t=1,2,…,T

(6)

txjt≤T,t=1,2,…,T

(7)

目标函数(1)表示该问题是优化整个周期内各资源使用的最大总成本.约束条件(2)表明时刻t资源p的使用量；式(3)表示任务在整个周期内的执行时间满足该任务工期约束；任务之间应该满足约束(4)，即满足一定的优先关系；式(5)说明需要关键资源的任务必须满足空窗期约束；式(6)说明任务一旦开始，在完成之前不允许被中断；式(7)说明所有任务的最晚结束时间不应大于项目给定工期.

2 启发式算法设计

启发式算法的设计思路为：基于关键路径法(CPM)获得项目中的关键链，确定关键任务和非关键任务.将关键任务纳入调度计划，决策关键任务排入方式为连续排入或预留时间间隔排入；在此基础上安排非关键任务，提出四种规则确定非关键任务优先级，然后以最小资源需求量为目标，确定非关键任务的决策区间，再通过局部规则判断基准在决策区间内的取值，最终确定非关键任务调度位置.通过以上分析可知，该启发式算法可根据决策重点分为三个阶段.

2.1 第一阶段：生成非关键任务优先级列表

吴怡薇等[13]在求解资源水平问题时提出采用资源用量规则和自由度规则来确定非关键任务优先级.本研究在基本RIP上考虑空窗期约束，为了减少空窗期对任务的交互影响，增加工期规则以及最早开始时间(EST)规则，使可能对调度结果产生更大影响的任务拥有更多可排空间，尽早排入.

(1) 工期规则

任务工期越长，与已排定任务重叠度越高，在有空窗期的条件下，与空窗期重叠的可能性也越大.RIP目标的本质就是通过调度使得任务间重叠度降低，所以tj越长，非关键任务j的优先级越高.

(2) EST规则

一般而言，在RIP中任务调度顺序与各任务在项目网络图中位置不完全一致.EST规则可作为前三种规则的补充，避免优先级相同的情况出现，因此可定义tES,j越小，非关键任务j的优先级越高.

任务的工期对开始时间决策区间的大小影响很大，而任务的资源用量直接影响资源投入总成本，故工期规则及资源用量规则作为优先规则考虑.具体操作时，按照上述四种规则顺序依次比较非关键任务j的tj、rj,max、tTF,j以及tES,j，最终确定非关键任务优先级列表Lp.

第一阶段算法步骤如下所示：

步骤1建立已安排任务集合S=∅，未安排任务集合S′=J.

步骤2确定需要关键资源pk的任务集合Ae.

步骤4根据CPM获得任务j∈J的tES,j、tLS,j、tEF,j、tLF,j和tTF,j.

步骤5确定关键任务为集合Cr，余下任务即为非关键任务.

步骤6生成非关键任务优先级列表Lp.

2.2 第二阶段：关键任务排入方式的确定

2.2.2关键任务调整基准

图2 相关关键任务调整

第二阶段算法步骤如下所示：

步骤1将集合Cr内的所有关键任务连续排入.

步骤7t=t+1；返回步骤5.

2.3 第三阶段：非关键任务的调度决策

2.3.1相关任务与相关距离dij

能够影响任务j的开始时间tST,j的决策区间的任务为和任务j具有时序关系的任务，称该任务为任务j的相关任务.定义Re={i∈S|ij}为对任务j进行调度时已经完成调度的相关任务.对于两个相关任务i、j而言，定义相关距离dij为任务i到任务j的最长路径的长度，易得dij=-dji.

2.3.2任务j∈J开始时间tST,j可排区间点集

(8)

(9)

(10)

从而形成最终的tST,j可排区间离散点集

Smove,j={tST,j1,tST,j2,…,tST,jn}

(11)

2.3.3任务j∈J开始时间tST,j可变区间点集

(12)

任务j开始时间tST,j的可变区间点集即为任务j开始时间tST,j的决策区间.

2.3.4局部最优判断基准

对于任意非关键任务j而言，易得Schange,j⊆Smove,j，而Schange,j中的点实际上为只考虑任务j的资源总量最小解集，显然集合内的所有点未必都能对应全局下的最小资源总成本.

根据优先级排入非关键任务，待排任务的位置确定受后序任务的影响.因此，通过考虑任务j的调度位置对后序任务的排入影响来进一步确定tST,j，即使得连续排入的两个任务间结果最优.

第三阶段算法步骤如下所示：

步骤2生成当前任一时刻t的资源列表Rtp.

步骤3按照优先级顺序选择非关键任务优先级列表Lp中任务j，获得其对应的Re={i∈S|ij}，对于任意任务i∈Re求出相关距离dij，继而得出tST,j可排区间点集Smove,j.

步骤7result[]中的最小值为最终结果，输出该结果，算法结束.

3 遗传算法设计

分析启发式算法的设计过程，发现非关键任务的优先级以及关键任务的开始时间会对最终结果产生较大的影响，而启发式算法中并未对这两项进行更多可能性的尝试.因此，本研究遗传算法的上层算法中，对于决策项目非关键任务的优先级和关键任务的开始时间，下层解码算法采用第2节中提出的启发式规则，决策各非关键任务的开始、结束时间，并以此方案的目标函数值作为遗传算法的适应度值，返回到上层遗传算法，再不断复制、交叉、变异，通过循环迭代的方式，得到近似最优解.

3.1 编码

对于有J项任务的项目，假设其中关键任务数量为a，非关键任务数量为b，易得a+b=J.每组编码的第一层对应各非关键任务的调度优先级列表，长度为b.若编码第k位为j，则代表任务编号为j的任务调度优先级为k.第二层对应项目中各关键任务开始时间，长度为a，对于关键任务1假定开始时间为定值tST,1=1，后续关键任务开始时间在开始时间的可排区间点集内随机确定,如图3所示.

图3 编码示例

3.2 遗传操作

3.2.1初始种群

初始种群由两部分组成：一是按照第2.1节中启发式算法非关键任务的优先级列表以及第2.2节中连续排入的关键任务作为一个初始解；二是在可行范围内随机生成.

3.2.2选择

运用随机联赛选择算子，适应值小的进入下一代种群.适应值函数为

(13)

3.2.3交叉

本研究采用单点交叉的方法.由于遗传算法采用双链表编码模式，对非关键任务优先级以及关键任务开始时间进行编码，交叉操作后可能出现不可能解，因此需要进行额外操作消除不可行解.对于非关键任务链表需要消除交叉后可能出现的重复现象，对于关键任务开始时间链表需要保证交叉后的时间在该任务开始时间的可行范围之内，具体过程如图4所示.

(1) 对非关键任务优先级的链表进行交叉操作.对染色体C2，选择与染色体C1中x位置之前的基因不相同的基因链，与染色体C1中x位置之后的基因段互换，生成新的染色体Sg；对染色体C1，同理生成新的染色体D.

(2) 对关键任务开始时间的链表进行交叉操作.对染色体C2，选择与染色体C1中x位置之前的基因链，与染色体C1中x位置之后的基因段互换，若互换后的开始时间点处在区间[tES,tLS]内，则直接互换；若互换后的开始时间点小于tES，则互换后的基因取值为tES；若互换后的开始时间点大于tLS，则互换后的基因取值为tLS；生成新的染色体Sg；对染色体C1，同理生成新的染色体D.

图4 交叉操作示例

3.2.4变异

本研究采用基本位变异的方法，分以下两步进行:

(1) 对k=1,2,…,b，在[1,b]之间随机产生两个数x、y，交换x、y两位置所对应的任务的优先级，生成新的列表.

(2) 对k=2,3,…,a，在[2,a]之间随机产生一个数z，改变位置z所对应任务的开始时间，并重新生成位置z后序所有关键任务的开始时间.具体过程如图5所示.

图5 变异操作示例

3.3 解码

利用上述遗传算法，得到了非关键任务优先级列表以及关键任务的开始时间，接下来对所得到的染色体根据第2节中介绍的启发式规则，进行相应链表的解码操作.

4 数值实验

实验中所用测试算例基于测试问题库PSPLIB中的算例进行改造，对于未提供的参数，采用在一定大小范围内通过random函数随机产生自然数的方式来确定，其中工期上限T取资源不受限下基于最早开始时间调度得到的任务最晚完成时间的1.2倍.空窗期数M=1，空窗期开始时间和结束时间随机生成，长度不超过0.1T.遗传算法设定的种群规模N=100，最大迭代次数λmax=50，交叉概率Pc=0.8，变异概率Pm=0.1.测试平台为Intel Core i5处理器，2.20 GHz主频，4.00G内存.

表1～3显示了小规模问题的算例结果，算例规模依次为10、20、30项任务；每组包含五个算例，C列、H列和G列分别表示CPLEX以及启发式算法和遗传算法在处理本组五个算例时得到的最好解的平均值取整.对于包含60和90项任务的大规模问题，启发式算法和遗传算法在求解速度上的差异较为明显，而CPLEX在规定运算时间内无法求得结果，故对于大规模问题分别对提出的两种算法进行求解精度和求解速度的比较.每个算例的空窗期约束在首次随机生成后统一设定，保证比较的合理性.表4～5为大规模问题的算例结果，v列表示每组算例在相应算法下各运行10次后得到的最小值的平均值，w列表示求得对应结果的平均时间，单位为s.

表1～5中：

(14)

(15)

(16)

表1 10项任务实验结果

表2 20项任务实验结果

从表1～3中g1项和g2项可以发现，对任务数为10、20、30的小规模算例，所设计的启发式算法与CPLEX求解得到的最优解分别相差4.05%、6.12%、10.85%，遗传算法求得的结果与CPLEX求得的最优解分别相差1.57%、3.20%、6.73%.可以证实所提出的启发式算法和遗传算法在一定误差范围内均能求解出较好的结果，遗传算法求解精度更高；随着算例规模的增大，启发式算法在求解精度上的局限性越发明显；小规模算例中启发式算法与遗传算法的g3值相差3%左右.

表3 30项任务实验结果

表4 60项任务实验结果

表5 90项任务实验结果

对于任务数为60和90的大规模算例而言，通过表4、表5中的g3项结果可以看出，两种算法的g3值分别为11.87%、13.57%，相差较大，虽无法与精确结果作比较，但可以说明求解大规模问题时，与启发式算法相比，采用遗传算法可以明显提升求解精度.比较两表中的w列结果发现，任务数为60时两种算法的平均求解时间分别为29.54、48.89 s,任务数为90时两种算法的平均求解时间分别为60.60、116.78 s，启发式算法的求解速度更快.所设计的启发式算法的时间复杂性为O(n2)，由于提出的遗传算法在解码和评估阶段嵌套了相同的启发式规则，随着算例规模的增大，两者在求解时间上的差异也随之变大.对于大规模算例，遗传算法与启发式算法相比具有较高的精度，但求解速度较慢.由此表明，提出的两种算法在不同的层面上具有不同的应用价值.

5 总结与展望

针对飞机移动式装配线上存在的关键资源带有空窗期约束这一特性，提出以连续排入的两个非关键任务间结果最优的启发式规则，分别设计了构造启发式算法和改进遗传算法求解带资源空窗期的RIP，并通过数值实验验证了所提出算法的求解精度和求解速度在不同层面上的有效性.小规模算例中，两种算法所得解与最优解间的平均差值在11%以内；大规模算例中，遗传算法的求解精度较高，启发式算法的求解速度较快.将飞机移动式装配线抽象为项目调度资源投入问题的研究对于提升我国飞机制造业水平、带动经济发展和科技进步具有重要意义.