文章快速检索    
  同济大学学报(自然科学版)  2019, Vol. 47 Issue (10): 1520-1527.  DOI: 10.11908/j.issn.0253-374x.2019.10.019
0

引用本文  

陆志强, 周皓雪. 带资源空窗期的资源投入型问题的建模与优化[J]. 同济大学学报(自然科学版), 2019, 47(10): 1520-1527. DOI: 10.11908/j.issn.0253-374x.2019.10.019.
LU Zhiqiang, ZHOU Haoxue. Modeling and Optimization of Resource Investment Problem with Resource Window[J]. Journal of Tongji University (Natural Science), 2019, 47(10): 1520-1527. DOI: 10.11908/j.issn.0253-374x.2019.10.019

基金项目

国家自然科学基金(61473211, 71171130)

第一作者

陆志强(1968—),男,教授,博士生导师,工学博士,主要研究方向为物流与供应链的建模和优化以及生产工程等.E-mail:zhiqianglu@tongji.edu.cn

文章历史

收稿日期:2018-12-12
带资源空窗期的资源投入型问题的建模与优化
陆志强 , 周皓雪     
同济大学 机械与能源工程学院,上海 201804
摘要:以飞机移动式装配线为背景,在基本资源投入型问题的基础上考虑资源空窗期约束,建立以最小化资源使用总成本为目标的数学模型.针对该模型设计了一种构造启发式算法,并提出了非关键任务优先级决策规则.考虑空窗期约束特点,以连续排入的两个非关键任务间结果最优的启发式规则来确定非关键任务位置,并提出以非关键任务优先级和关键任务开始时间为双链表编码的遗传算法,然后将启发式规则嵌套在遗传算法的解码和评估阶段.最后通过数值实验比较启发式算法和遗传算法与CPLEX在求解该问题时的优劣,证明了两种算法的有效性.
关键词资源投入    资源空窗期    启发式算法    遗传算法    
Modeling and Optimization of Resource Investment Problem with Resource Window
LU Zhiqiang , ZHOU Haoxue     
School of Mechanical Engineering, Tongji University, Shanghai 201804, China
Abstract: Resource investment problem with resource window constraint was considered in the context of aircraft mobile assembly line. A mathematical model was proposed to solve the problem with the objective of the total cost minimization of resource. Firstly, based on the characteristics of the resource window constraint, a constructive heuristic algorithm with non-critical activity priority decision rules was developed to solve small-scale problems. Secondly, a genetic algorithm, which was coded by a double-linked list including non-critical activity priority and critical activity start time and decoded by non-critical activity priority decision rules, was proposed for the large-scale problems. Finally, numerical experiments were carried out to compare the advantages and disadvantages between heuristic algorithm, genetic algorithm and CPLEX, and the effectiveness of the two proposed algorithms was proved.
Key words: resource investment    resource window    heuristic algorithm    genetic algorithm    

基于精益思想的飞机移动式装配线已成为飞机装配生产的新模式,具有装配效率高、质量稳定、可按需批量生产等特点,近年来被世界各大航空制造企业竞相采用.实际上,对于每架飞机而言,移动式装配线上的总装任务调度问题具有装配工序繁多、装配任务复杂、装配过程受到多重约束限制等特点.调度过程可根据实际应用的目的抽象为资源受限项目调度问题(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)的执行时间为tjp(j)为第j项任务的紧前任务集合,s(j)为第j项任务的紧后任务集合,tES, jtLS, jtEF, jtLF, 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表示任务jAe在第m个非空窗期区间内完成,否则取0.

1.2 空窗期

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

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

图 1 资源空窗期示意图 Fig.1 Schematic diagram of resource window
1.3 数学模型

目标函数为

$ \min \sum\limits_{p = 1}^P {\left( {{C_p}\max \left( {{R_{tp}}} \right)} \right)} $ (1)

约束为

$ {R_{tp}} = \sum\limits_{j = 1}^J {{r_{jp}}} {x_{jt}}, t = 1, 2, \cdots , T, p = 1, 2, \cdots , P $ (2)
$ \sum\limits_{t = {t_{{\rm{ES}}, j}}}^{{t_{{\rm{LF}}, j}}} {{x_{jt}}} = {t_j}, j = 1, 2, \cdots , J $ (3)
$ t_{j} x_{j t} \leqslant \sum\limits_{k=1}^{t-1} x_{j^{*} k}, \quad \forall j^{*} \in p(j) $ (4)
$ \sum\limits_{m=1}^{M} z_{j m} t_{\mathrm{e}, m-1} \leqslant \sum\limits_{t=t_{\mathrm{EF}, j}}^{t_{\mathrm{LF}, j}} t x_{j t} \leqslant \sum\limits_{m=1}^{M} z_{j m} t_{\mathrm{b}, m}, j \in A_{\mathrm{e}} $ (5)
$ t_{j} x_{j t}-t_{j} x_{j(t+1)}+\sum\limits_{k=t+2}^{T} x_{j k} \leqslant t_{j}, j=1, 2, \cdots, J, t=1, 2, \cdots, T $ (6)
$ t x_{j t} \leqslant T, t=1, 2, \cdots, 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的优先级越高.

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

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

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

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

步骤3  计算每种资源的最大需求量的总和${r_{\max }}, {r_{\max }} = \sum\limits_{p = 1}^P {\max } {r_{jp}} $.

步骤4  根据CPM获得任务jJtES, jtLS, jtEF, jtLF, jtTF, j.

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

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

2.2 第二阶段:关键任务排入方式的确定 2.2.1 相关关键任务j0*

由第2.1节获得非关键任务优先级列表Lp,设列表Lp中第1个非关键任务为j0,令Δ=tES, j*-tES, j0,称使得Δ取0或最小正数的j0*为相关关键任务.如图 2所示,任务2、5、7、8、9为关键任务,任务1为列表Lp中第1个非关键任务,任务7为相关关键任务.

图 2 相关关键任务调整 Fig.2 Related critical activity adjustment
2.2.2 关键任务调整基准

调整关键链时,关键链中相关关键任务j0*之前的关键任务不做调整,j0*按调整区间点集进行位置的改变,而j0*之后的关键任务将随着j0*的调整顺次右移,最终确定所有关键任务的位置.调整相关关键任务j0*的位置可使优先级最高的非关键任务拥有更多的可排空间,可最大限度降低资源用量峰值.

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

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

步骤2  选择列表Lp中第1个非关键任务,记为j0;根据Δ=tES, j*-tES, j0计算得到相关关键任务j0*.

步骤3  将j0*之前的每个关键任务按最早开始时间排入,更新集合SS′.

步骤4  j0*的最早开始时间记为tES, j0*,令t=tES, j0*.

步骤5  j0*的开始时间为t.

步骤6  将j0*之后的关键任务按照最早开始时间规则排入,若在任务工期约束和空窗期约束下有解,则将t记入j0*的开始时间tST, j0*的调整区间点集Schange, j0*;否则,转入步骤8.

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

步骤8  生成j0*的开始时间tST, j0*的调整区间点集Schange, j0*.

2.3 第三阶段:非关键任务的调度决策 2.3.1 相关任务与相关距离dij

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

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

对任意任务jtST, j可排区间[tES, j, tLS, j]应满足下述条件:

$ t_{\mathrm{ES}, j}^{\prime}=\max \left\{t_{\mathrm{ES}, j}, \max\limits_{i \in R_{\mathrm{e}}}\left(t_{\mathrm{ST}, i}+d_{i j}\right)\right\}, d_{i j}>0 $ (8)
$ t_{\mathrm{LS}, j}^{\prime}=\min \left\{t_{\mathrm{LS}, j}, \min\limits_{i \in R_{\mathrm{e}}}\left(t_{\mathrm{ST}, i}+d_{i j}\right)\right\}, d_{i j}<0 $ (9)

若任务ij不相关,即不存在dij,则tES, j=tES, j;否则,tLS, j=tLS, j.

由于存在空窗期约束,因此对任意任务jAe的可排区间点集需剔除处于空窗期区间内的不可行解.假定关键资源pk的可用区间为[te, m, tb, m],则对任意任务jAetST, j可排区间[tES, j, tLS, j],需与[te, m, tb, m+1-tj]取交集,即满足

$ \sum\limits_{m = 1}^M {{t_{{\rm e}, m}}} \le \sum\limits_{t = {t_{{\rm{ST}}, j}}}^{{t_{{\rm{TF}}, j}}} t \le \sum\limits_{m = 1}^M {{t_{{\rm{b}}, m}}} $ (10)

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

$ S_{\text {move }, j}=\left\{t_{\mathrm{ST}, j 1}, t_{\mathrm{ST}, j 2}, \cdots, t_{\mathrm{ST}, j n}\right\} $ (11)
2.3.3 任务jJ开始时间tST, j可变区间点集

将任务j按照Smove, j={tST, j1, tST, j2, …, tST, jn}依次排入,更新资源列表Rtp,计算每一个排入点所对应的rmax,将rmax的最小值记为rmmin,将所有取得rmmintST, j记为任务j的开始时间tST, j的可变区间点集

$ S_{\text {change }, j}=\left\{t_{\mathrm{ST}, j 1}^{\prime}, t_{\mathrm{ST}, j2}^{\prime}, \cdots, t_{\mathrm{ST}, j n}^{\prime}\right\} $ (12)

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

2.3.4 局部最优判断基准

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

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

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

步骤1  j0*按照调整区间点集Schange, j0*排入;将j0*之后的关键任务按照最早开始时间规则排入,更新集合SS′.

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

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

步骤4  将任务j按照Smove, j依次排入,更新资源列表Rtp,得到任务j开始时间tST, j的可变区间点集Schange, j.若rmminrmax,更新集合SS′,取点集Schange, j的第一个点排入,返回步骤3;若rmmin>rmax,则转入步骤5.

步骤5  将任务j在列表Lp中的上一任务按照可变区间点集Schange, j依次排入,返回步骤3;若上一任务按照可变区间点集Schange, j=∅,则令rmax=rmmin,转入步骤1.

步骤6  直至已安排任务集合S=J,未安排任务集合S′=∅.输出此时rmax,记入result[].按照j0*的开始时间tST, j0*的调整区间点集Schange, j0*依次移动,重复步骤1~6,直至Schange, j0*=∅,转入步骤7.

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

3 遗传算法设计

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

3.1 编码

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

图 3 编码示例 Fig.3 Coding example
3.2 遗传操作 3.2.1 初始种群

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

3.2.2 选择

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

$ f(s) = \sum\limits_{p = 1}^P {\left( {{C_p}\max {R_{tp}}} \right)} $ (13)
3.2.3 交叉

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

图 4 交叉操作示例 Fig.4 Cross example

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

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

3.2.4 变异

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

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

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

图 5 变异操作示例 Fig.5 Variation example
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.

下载CSV 表 1 10项任务实验结果 Tab.1 Results of 10 jobs
下载CSV 表 2 20项任务实验结果 Tab.2 Results of 20 jobs
下载CSV 表 3 30项任务实验结果 Tab.3 Results of 30 jobs
下载CSV 表 4 60项任务实验结果 Tab.4 Results of 60 jobs
下载CSV 表 5 90项任务实验结果 Tab.5 Results of 90 jobs

表 1~5中:

$ g_{1}=\frac{H-C}{H} \times 100 \% $ (14)
$ g_{2}=\frac{G-C}{G} \times 100 \% $ (15)
$ g_{3}=\frac{H-G}{H} \times 100 \% $ (16)

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

对于任务数为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%以内;大规模算例中,遗传算法的求解精度较高,启发式算法的求解速度较快.将飞机移动式装配线抽象为项目调度资源投入问题的研究对于提升我国飞机制造业水平、带动经济发展和科技进步具有重要意义.

参考文献
[1]
MÖHRING R H. Minimizing costs of resource requirements in project networks subject to a fixed completion time[J]. Operations Research, 1984, 32(1): 89 DOI:10.1287/opre.32.1.89
[2]
DREXL A, KIMMS A. Optimization guided lower and upper bounds for the resource investment problem[J]. Operational Research Society, 2001, 52(3): 340
[3]
RODRIGUES S B, YAMASHITA D S. An exact algorithm for minimizing resource availability costs in project scheduling[J]. European Journal of Operational Research, 2010, 206(3): 562 DOI:10.1016/j.ejor.2010.03.008
[4]
SONG Y, LIU J, WIMMERS M O, et al. A differential evolution algorithm with local search for resource investment project scheduling problems[C]//Evolutionary Computation. Sendai: IEEE, 2015: 1725-1731.
[5]
MYSZKOWSKI P B, SKOWROŃSKI M E, OLECH L P, et al. Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem[J]. Soft Computing, 2015, 19(12): 3599 DOI:10.1007/s00500-014-1455-x
[6]
VAN PETEGHEM V, VAN HOUCKE M. An artificial immune system algorithm for the resource availability cost problem[J]. Flexible Services and Manufacturing Journal, 2013, 25(1/2): 122
[7]
HE L H, ZHANG L Y. Dynamic priority rule-based forward-backward heuristic algorithm for resource leveling problem in construction project[J]. Journal of the Operational Research Society, 2013, 64(8): 1106 DOI:10.1057/jors.2013.33
[8]
QI J J, LIU Y J, JIANG P, et al. Schedule generation scheme for solving multi-mode resource availability cost problem by modified particle swarm optimization[J]. Journal of Scheduling, 2015, 18(3): 285 DOI:10.1007/s10951-014-0374-0
[9]
胡淑芳.考虑资源技能和时间窗特性的任务可拆分项目调度[D].武汉: 华中科技大学, 2012.
HU Shufang. Preemptive project scheduling with resources of multi-skill and time-windows[D]. Wuhan: Huazhong University of Science and Technology, 2012. http://cdmd.cnki.com.cn/Article/CDMD-10487-1013012309.htm
[10]
廖广瑞, 刘振元, 毕阳.多技能资源时间窗约束下项目调度研究[C]//中国控制与决策会议.长沙: 出版者不详, 2014: 4885-4891.
LIAO Guangrui, LIU Zhenyuan, BI Yang. Project scheduling with time window constraints on multi-skill resources[C]//Chinese Control and Decision Conference. Changsha: [s.n.], 2014: 4885-4891. http://cpfd.cnki.com.cn/Article/CPFDTOTAL-KZJC201405001924.htm
[11]
綦方中, 胡丹, 叶雷宏. 基于时间窗和关键链的多项目资源分配问题的研究[J]. 科技管理研究, 2013, 33(13): 229
QI Fangzhong, HU Dan, YE Leihong. Study on resource allocation of multi-project based on time window and critical chain[J]. Science and Technology Management Research, 2013, 33(13): 229
[12]
刘振元, 黄亚健. 资源多时间窗约束下的项目调度[J]. 系统工程, 2014(10): 126
LIU Zhenyuan, HUANG Yajian. Project scheduling with constraints of multiple time windows on resources[J]. Systems Engineering, 2014(10): 126
[13]
吴怡薇, 陆志强. 飞机移动装配线资源水平问题的建模研究[J]. 工业工程与管理, 2017, 22(1): 95
WU Yiwei, LU Zhiqiang. Modeling resource leveling for aircraft moving assembly line[J]. Industrial Engineering and Management, 2017, 22(1): 95