资源空窗期及任务可拆分的资源投入问题研究

陆志强 周皓雪

摘   要：考虑飞机装配过程中任务可拆分及资源存在空窗期的两大特性，对飞机移动生产线资源投入问题进行模型与算法研究. 针对部分任务存在已知拆分模式及拆分惩罚的情形，设计了求解该问题的改进遗传算法，对传统实数交叉操作进行优化，提出了基于染色体适应值的交叉方法，并在数值实验中对相关参数的取值范围进行了敏感性分析;同时，提出了基于任务开始时间选择概率的变异机制. 对满足优化条件的任务调度方案，结合空窗期的位置，评判各可拆分任务可否通过选取新的拆分模式重新调度执行，对不同情形进行总结归纳，通过局部操作进一步降低目标资源量. 数值实验表明：通过本文算法对求解带资源空窗期的任务不可拆分问题与基本问题的结果对比，得到任务数分别为10、16、30、60、90算例的目标值平均增量达到4.3%;对求解本文问题与任务不可拆分问题的结果对比，平均优化率达3.5%，证明了本文算法的有效性，同时证明将任务拆分纳入考虑资源空窗期的资源投入问题中，可提高问题求解的灵活性，从而获得较好的调度结果.

关键词：资源投入问题;资源空窗期;任务拆分;遗传算法

中图分类号：F273                                文献标志码：A

Abstract：Considering the two characteristics of activity splitting and resource window in the process of aircraft assembly，the model and algorithm of Resource Investment Problem on aircraft mobile production line were studied. Aiming at the situation that some activities have known splitting mode and splitting punishment，an improved genetic algorithm for solving this problem was designed. The traditional real value crossover operation was optimized，and a crossover method based on chromosome fitness value was proposed. Sensitivity analysis was carried out on the range of values of the relevant parameters. A mutation mechanism based on the probability of selection of activity start time was also proposed. For a scheduling scheme that satisfies the optimization conditions，combined with the position of the resource window，after judging whether the splitting activities can be re-scheduled and executed by selecting a new splitting mode and summarizing the different situations，the target resources were further reduced by local operations. The numerical experiments show that，compared with the results of solving the problem of non-split activities with resource window and the basic problem，the average value of the target for the 10，16，30，60，90 activities is 4.3%. For the comparison between the results of solving this problem and the non-split problem，the average optimization rate is 3.5%，which proves the effectiveness of the algorithm. At the same time，it is proved that the activity splitting is included in the Resource Investment Problem considering the resource window，which can improve the flexibility of problem solving and obtain better scheduling results.

Key words：resource investment problem;resource window;activity splitting;genetic algorithm

目前，我國的飞机总装大部分仍沿用传统的固定站位式装配模式，批量生产能力匮乏. 随着社会经济的发展，民用机的需求激增，在航空制造中深入推行基于精益思想的飞机移动式装配线模式，可提高装配效率和质量，按需批量生产是中国飞机制造向世界水平迈进的必经之路. 装配线上单架飞机的总装调度决策问题依据不同的生产目的，可将其抽象地分为资源受限项目调度问题[1]（Resource-Constrained Project Scheduling Problem，RCPSP）和资源投入型问题[2]（Resource Investment Problem，RIP）. 后者即在给定的制造期限约束下，优化配置完成项目所需的线边装配人员、工装、工具及仪器设备等各类资源，达到最小化资源投入总成本的目的.

资源投入问题最早由Morhing[3]在一个桥梁建设项目中提出，其证明了此问题为NP-hard，提出了求解该问题的图解精确算法;Drexl等[4]基于拉格朗日松弛和列生成方法针对RIP提出了两个下界算法，并且通过算例实验与Morhing[3]提出的算法进行了比较;Demeulemeester[5]参照针对RCPSP问题提出的基于深度优先的分支定界方法，构建了求解RIP的优化算法. 上述精确算法虽然求解精度较好，但是只能应用于小规模问题，对于诸如飞机生产制造的大规模问题，大量国内外学者提出启发式算法与元启发式算法进行求解. Zhu等[6]将RIP问题的求解划分为排序问题与资源决策问题两个部分，提出了一种多起点迭代搜索的启发式方法;Song等[7]利用带有局部搜索的进化算法求解，在优化过程中不允许项目延迟;Qi等[8]提出了改进的粒子群优化算法求解多模式下资源可用性成本问题的调度生成方案;Javanmard等[9]设计了一种基于遗传和粒子群的算法，通过校准参数和染色体结构，保证解的可行性;任逸飞等[10]通过基于全局资源水平影响的任务调度评估策略，提出改进型遗传算法优化非关键任务的调度位置，然而该评估策略在求解大规模算例时效率较低.

上述文献均为对基本RIP的研究，存在大量的假设，模型偏理想化，对工况条件复杂的飞机总装过程缺乏指导意义;从算法设计上来看，多数算法局限于将RIP转化成RCPSP的求解思路，导致某些资源组合可能超出工期约束，针对资源的搜索方向性较差，求解效率低. 现代化的飞机生产制造工序繁琐，技术复杂性高，总装过程需要大量不同的专业性人才. 因此，在实际生产过程中往往会存在由于关键技术人员紧缺而必须延迟调度的情形，将资源存在的不可用时间段称为资源空窗期. 将资源空窗期约束引入到RIP模型构建中，更加贴合飞机移动式装配线应用背景. 现有文献中仅考虑资源空窗期的RCPSP，考虑资源特点的RIP研究很少. 廖广瑞等[11]针对资源的多技能和时间窗属性，设计了一种基于优先规则的Rollout求解算法，并嵌入了一种启发式资源分配方法对资源进行快速分配;Jirachai等[12]研究了考虑资源空窗期的多模式RCPSP问题，假定任务可拆分执行，设计了求解小规模该类问题的分支定界算法;綦方中等[13]研究了基于时间窗的多项目资源分配问题，提出了增加时间窗参数以及惩罚因子的多项目管理资源分配模型. 总结上述研究可以发现，空窗期的引入会导致任务调度的灵活性下降，从而加剧空窗期前后位置的资源投入量，增加项目的成本支出.

另一方面，现有RIP问题的研究通常假设任务不可拆分，但从飞机装配工艺过程中可以发现，某些任务过程并不是连续的，是可以拆分执行的. 从Javanmard等[9]和陆志强等[14]对于任务可拆分条件下RIP的研究中可以看出，考虑任务可拆分特性能增加任务调度的柔性，均衡资源使用，降低成本投入. 而在以上文献中，虽然考虑了任务可拆分执行的情形，却并未设置相应的拆分惩罚机制. 在飞机实际装配生产中，某项任务在执行过程中中断，待到后续某时刻继续执行时，需要重新进行装配准备工作，势必造成时间成本或资源成本的增加.

综上所述，本文将任务拆分及伴有拆分惩罚的情形纳入考虑资源空窗期的资源投入问题中，构建符合实际应用条件的模型，重点分析同时考虑任务可拆分及资源存在空窗期这两大特性的交互影响，设计相应的改进型遗传算法及优化操作进行求解和验证. 最后通过实例分析，以某型号支线客机驾驶舱装配工位的调度为例，验证了本文算法的有效性.

1   问题描述及数学模型

1.1   問题描述

假设项目由若干项任务构成，记给定项目工期为T，项目中包含J项任务，任务执行时间为dj，pre（j）为第j项任务的紧前任务构成的集合，j*为任务j的紧前任务，suc（j）为其紧后任务构成的集合. J项任务各有Mj（j∈J）种执行模式，其中存在K项任务，构成集合U，满足Mk>1（k∈K），存在拆分执行模式，其余任务满足Mj = 1（j∈J，j?K），不能拆分执行. r1

全部任务共享P种可更新资源，每种资源的单位使用成本为Cp（p∈P）. 其中资源分关键资源和普通资源，关键资源存在空窗期，部分时刻不可用，普通资源在任意时刻皆可使用;Wp为资源在项目周期T内的可用时间窗集，普通资源满足Wp = [1，T]，引入参量Zpt，表示资源p在t时刻是否可用，若t∈Wp，则Zpt = 1，否则Zpt = 0. 任务间存在着一定的时序关系，当满足紧前任务皆完成调度且所需资源充足的情况下，任务即可开始执行. 将时间进行离散处理，各任务在时刻t对资源p的总需求量用Rtp表示. 最小化各时刻t（t = 1，2，…，T）每种资源p的最大需求量Rtp的总成本之和是模型的优化目标.

式（1）为目标函数，表示该问题是优化整个周期内各资源使用的最大总成本;式（2）为约束条件，表示任务只能选择一种执行模式;式（3）表示任务在整个项目工期内的执行时间之和必须满足该任务工期约束;式（4）计算了各时间段t内每种资源p的使用量;式（5）表示任务只有在所需资源皆可用时才能执行;任务之间需满足时序约束（式（6）），即满足一定的优先关系;式（7）表示所有任务的最晚结束时间不应大于项目给定工期;式（8）定义了决策变量xjmt与yjm的可行域.

2   算法设计

本文采用直接确定任务位置来获得任务调度计划及资源使用情况的算法设计思路，通过确定任务开始时间的方式来间接获得项目中的资源投入量，针对可拆分任务，将其结束时间也在编码中体现. 以遗传算法为搜索框架，设计基于染色体适应值的实数交叉方式及基于任务开始时间选择概率的变异方式进行遗传操作，在解码过程中针对各染色体调度计划，结合资源空窗期与可拆分任务的拆分模式，进行拆分任务的模型更换，进一步降低项目资源投入量，优化目标资源成本.

2.1   基于任务开始时间的编码

本文在可行范围内，采用对任务开始时间进行编码的方式，直观展现各任务调度位置;为体现拆分任务的拆分与否，同时对可拆分任务的结束时间进行编码. 当项目中存在J项任务和M项可拆分任务时，编码的长度为J + M，其中编码第1到J位表示任务 j的开始时间;编码第J + 1到J + M位表示第m个可拆分任务的结束时间. 以图1所示算例为例，编码第8位表示可拆分任务3的结束时间为时刻3，故可知该任务选择的是连续执行的模式.

2.2   实数交叉

经过轮盘赌选择机制获得的种群，根据交叉概率Pc选择需要进行交叉操作的染色体组成集合C，Pc由式（9）求得，其中，Pc1、Pc2为预先定义的参数，favg、 fmin分别为所有染色体的平均适应度值和最小适应度值.

为提高染色体交叉后的多样性，本文结合文献[15]设计了一种新的基于染色体适应值的交叉方式. 不同父体之间适应值的差异不仅对繁殖过程有所裨益，而且可能会为生成更优异的后代提供潜在的搜索方向. 定义搜索方向v为：

式中：fitnessh和fitnessl分别表示父代中适应值较大和较小的染色体.染色体i的适应值fitnessi通过式（11）求得，Oi为该染色体编码对应的资源使用量，LB为项目最低资源用量，通过式（12）求取，其中rjp表示任务需要的单位资源的数量.

2.3   基于任务开始时间选择概率的变异

经过交叉之后得到的染色体，根据变异概率Pm选择需要进行变异操作的染色体组成集合M，Pm同样通过式（9）求得.

由于项目存在工期上限，因此各任务j的开始时间Sj存在决策区间[ESj，LSj]. 各任务不同开始时间的组合对应不同项目目标资源量，随着遗传算法不断迭代搜索，较低的目标值被发现的同时，所得调度计划中的任务开始时间也趋向于更小的决策区间[ES′j，LS′j]，甚至趋向于某一精确值. 定义任务开始时间选择概率P′S（ES≤S≤LS）和该开始时间下需要多投入的资源量R′S. 在初始种群中，令R′S = 1. 之后的每条染色体都根据当代的资源用量R更新R′S为：

2.4   局部优化操作

当部分任务存在可拆分执行模式，且该模式下某一拆分子任务的执行过程中无需使用存在空窗期的资源时，可考虑通过调整可拆分任务的执行模式及其余部分任务的执行位置，降低相应资源的占用量.

2.4.1   可拆分任务优化调整

针对空窗期位置及任务拆分模式等信息，当资源g满足g≠k，最大使用量出现的时刻Hg = 1，tsj≤Mg1≤tfj时，以下两种情形通过更换可拆分任务的拆分模式来降低资源g的投入量. 记对应染色体下各资源p（p∈P）的最大使用量和最大使用量出现的时刻分别为Vp、Mph（h = 1，…，Hp）（可能存在多个位置资源用量相同），资源k（k∈P）存在空窗期[mk，nk]，可拆分任务j（j∈J）在该调度计划下的执行时刻为[tsj， ffj]，可选拆分模式下前后两段所用资源种类分别为集合Baj和Bbj.

情形1：mk > Mg1，k?Bbj，区间[Mg1，nk]属于任务j的浮动区间. 资源k的空窗期位于最大资源时刻之后，任务j可以在区间[Mg1，nk]内任意时刻开始执行，且其拆分模式后半段无需使用资源k，该情形下可通过更换任务j为拆分模式执行，重调度区间[Mg1，nk]内的任务，降低资源k的Vk值.

仍以图1（a）所示项目网络图为例，假设资源2存在空窗期[5，6]，任务3为可拆分任务，拆分模式为2/2/2和1/2/0，拆分任务的惩罚时间成本为θ = 1. 对应染色体编码下初始调度结果如图2（a）所示，其中纵坐标R代表资源总用量，R1和R2为每个任务执行时所消耗的两种资源量，横坐标表示时间. 时刻6内无可执行任务，资源1和资源2的最大资源用量时刻皆为时刻1，资源用量分别为7和6. 鉴于可拆分任务3满足情形1，选取拆分模式执行后，将任务2的开始时间提前一个单位，任务3分别在时间段[0，2]、[4，6]内执行，资源1的用量V1降低了2个单位，调度结果如图2（b）所示.

情形2：nk > Mg1，k?Ba

j，区间[mk，Mg1]属于任务j的浮动区间. 资源k的空窗期位于最大资源时刻之前，任务j可以在区间[mk，Mg1]内任意时刻开始执行，且其拆分模式前半段无需使用资源k，该情形下可通过更换任务j为拆分模式执行，重调度区间[mk，Mg1]内的任务，降低资源k的Vk值.

以图1（a）所示项目网络图为例，假设资源2存在空窗期[0，1]，任务3为可拆分任务，拆分模式分别为2/2/0和1/2/2，拆分任务的惩罚时间成本为θ = 1. 对应染色体编码下初始调度结果如图3（a）所示，时刻1内无可执行任务，资源1和资源2的最大资源用量时刻皆为时刻1，资源用量分别为7和6. 鉴于可拆分任务3满足情形2，选取拆分模式执行后，将任务2的开始时间提前两个单位，任务3分别在时间段[0，2]、[4，6]内执行，资源1的用量V1降低了2个单位，同时资源2的用量V2降低了1个单位，调度结果如图3（b）所示.

2.4.2   算法步骤

步骤1   对染色体F进行解码操作，得到各资源 p（p∈P）的最大使用量和最大使用量出现的时刻Vp、Mph（h=1，…，Hp）及项目资源水平X，记资源k（k∈P）的空窗期為[mk，nk]，可拆分任务j（j∈J）的执行时刻为[Sj，Fj]，可选拆分模式下前后两段工期分别为daj和dbj. 令p = 1，转步骤2.

3   數值实验

为验证上述改进遗传算法对于求解考虑资源空窗期及任务可拆分特性下的资源投入问题的有效性，本文运用C#（Visual Studio 2013）编程实现该算法. 测试平台为Intel Core i5处理器，2.40 GHz主频，8 G内存. 通过对PSPLIB中的算例进行改造，获得了本文所用的测试算例，对于实验所需而基本算例中未提供的参数，通过随机数的方式来确定，其中工期上限T取关键路径长的1.2倍，资源空窗期通过在项目工期内随机产生不同长度的区间获得. 基于不同规模的算例，对小规模算例选择2项任务作为可拆分任务，生成拆分模式下的执行时间及资源需求;对中大规模算例选择5项任务作为可拆分任务. 设定任务拆分的惩罚时间为θ = 1，即可拆分任务的后半段执行时间延长一个单位.

3.1   算法参数分析

本文遗传算法设计中交叉操作部分基于传统实数交叉方法进行了改进，设计了新的基于染色体适应值的交叉方式，采用参数α1、α2控制所生成染色体的方向. 选取标准算例库PSPLIB中包含J30、J60和J90共3种规模算例的任务对α1、α2进行敏感性分析，平均gap表示所有规模下不同算例误差百分比的均值. 图5为参数α1、α2的敏感性分析结果，分别比较取值范围为[0，1]和[1，2]下各算例的计算结果. 遗传算法设定的种群规模N=100.

3.2   数值实验分析

3.2.1   算法对比

为了验证本文所提出的改进型遗传算法的有效性，选取任务数分别为10、30、60的各10个算例为样本，与粒子群算法求解的结果进行对比，求解时间统一设定为60 s，结果如图6所示，GA为遗传算法求解结果，PSO为粒子群算法求解结果.从图6可以看出，虽然两种算法结果相近，但是遗传算法结果更优，说明本文所提出的改进型遗传算法具有优越性.

3.2.2   数值结果

选取任务数分别为10、16、30、60、90的各50个算例为样本进行数值实验分析，结果如表1～表5所示. GA及GA·NP分别代表每组为5个算例下本文算法和本文算法在考虑任务不可拆分情形下求得的目标值的均值;gap1为这两列值间的差异，用以体现任务拆分的意义. 由于当不考虑空窗期时本文中对于任务拆分的设定条件无任何意义，故GA·N表示本文算法考虑任务不可拆分及资源无空窗期情形下求得的目标值，gap2为GA·NP与GA·N值间的差异，用以体现空窗期对任务调度的影响.v表示每组为5个算例下每种算法求得的目标值的均值，t表示求解时间的均值，单位为s.

3.2.3   讨论与分析

从表6可以看出，本文针对求解考虑资源空窗期及任务可拆分条件下的资源投入问题所设计的遗传算法，能在较短时间内求得较优解. 对比本文算法改进下的求解任务不可拆分问题的结果与基本资源投入问题的结果，平均增量达4.3%;对比本文算法与改进下的求解任务不可拆分问题的结果，平均优化比率达3.5%. 结果表明本文提出的改进型遗传算法在求解中具有优越性.

从模型角度来看，在飞机实际装配过程中，空窗期约束的存在是客观事实，同时现实中部分任务可以被拆分执行;由于文中对任务拆分的模式假定是针对空窗期所设计，可选模式的执行方案也是根据空窗期进行设置，故能在一定程度上提高问题调度的柔性，从而获得更加贴合实际的调度方案.

3.3   实例应用分析

以某型号支线客机驾驶舱装配工位的调度为例对算法进行验证. 该工位共包含14项装配任务，任务间的时序约束关系、工期及所需资源量如表7所示，任务1与任务14表示虚任务，任务7及任务13为可拆分任务，存在拆分执行模式. 主要考虑关键人力资源R1、关键设备资源R2、物料配送能力R3和线边空间存储能力R4共4类对飞机生产过程影响较大的资源类型，已知关键人力资源R1存在空窗期[4，6].

图7和图8中，横轴表示时间，由于项目的执行需要4种资源，无法用一张图表明各资源使用量，所以纵坐标不代表任何参量. 图示两种方法求得实例的资源成本均为59，说明本文算法在此实例下能够求得最优解.

4   结   论

本文以飞机移动式装配线为背景，在研究基本资源投入问题的基础上，同时考虑任务可拆分及资源存在空窗期两大特性，设计了改进型遗传算法进行求解，结果表明：

1）考虑空窗期下的问题调度缺乏灵活性，调度结果所用资源成本相对较高;将任务拆分纳入考虑资源空窗期的资源投入问题中，能通过任务拆分调度的灵活性降低空窗期对问题调度带来的不良影响，利用对任务不同调度位置的决策，合理配置现有资源的使用，从而获得相对较好的调度结果.

2）本文算法在求解效率及求解精度上表现良好，且能用于求解大规模算例.

参考文献

[1]    王琰，陆志强. 基于多重约束的飞机移动装配线作业任务调度优化[J]. 工业工程与管理，2011，16（6）：115-120.WANG Y，LU Z Q. Job scheduling optimization of aircraft moving assembly line under multiple constraints[J]. Industrial Engineering and Management，2011，16（6）：115-120.（In Chinese）

[2]    宗保氏，陆志强. 项目拆分与资源投入调度问题的集成优化[J]. 上海交通大学学报，2018，52（7）：793-800.ZONG B S，LU Z Q. Integrated optimization of project splitting and resource investment project scheduling[J]. Journal of Shanghai Jiaotong University，2018，52（7）：793—800. （In Chinese）

[3]    MORHING R H. Minimizing costs of resource requirements in project networks subject to a fixed completion time[J]. Operations Research，1984，32（1）：89—120.

[4]    DREXL A，KIMMS A. Optimization guided lower and upper bounds for the resource investment problem[J]. Operational Research Society，2001，52（3）：340—351.

[5]    DEMEULEMEESTER E L. Minimizing resource availability costs in time-limited project networks[J]. Operations Research and the Management Science，1995，41（10）：1590—1598.

[6]    ZHU X，RUIZ R，LI S Y，et al. An effective heuristic for project scheduling with resource availability cost[J]. European Journal of Operational Research，2016，257 （3）：746—762.

[7]    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.

[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.

[9]    JAVANMARD S，AFSHAR-NADJAFI B，NIAKI S T A. Preemptive multi-skilled resource investment project scheduling problem：Mathematical modelling and solution approaches[J]. Computers & Chemical Engineering，2017，96（4）：55—68.

[10]  任逸飛，陆志强.多技能资源投入项目调度问题的建模与优化[J]. 同济大学学报（自然科学版），2017，45（11）：1713—1721.REN Y F，LU Z Q. Modeling and optimization of resource investment project scheduling problem with multi-skill[J]. Journal of Tongji University（Natural Science），2017，45（11）：1713—1721.（In Chinese）

[11]  廖广瑞，刘振元，毕阳. 多技能资源时间窗约束下项目调度研究[C]// 第26届中国控制与决策会议论文集. 长沙：控制与决策，2014：4885—4891.LIAO G R，LIU Z Y，BI Y. Project Scheduling with Time Window Constraints on Multi-Skill Resources[C]// 26th Chinese Control and Decision Conference （CCDC）. Changsha：Control and Decision，2014：4885—4891. （In Chinese）

[12]  JIRACHAI B，DAVID S K. Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting[J]. European Journal of Operational Research，2006，175（1）：279—295.

[13]  綦方中，胡丹，叶雷宏. 基于时间窗和关键链的多项目资源分配问题的研究[J]. 科技管理研究，2013，33（13）：229—232.QI F Z，HU D，YE L H. Study on resource allocation of multi-project based on time window and critical chain[J]. Science and Technology Management Research，2013，33（13）：229—232. （In Chinese）

[14]  陆志强，石婷.作业任务可拆分的资源投入问题的建模与优化[J]. 计算机集成制造系统，2018，24（3）：602—611.LU Z Q，SHI T. Modeling and optimization of resource investment problem with activity splitting[J]. Computer Integrated Manufacturing System，2018，24（3）：602—611. （In Chinese）

[15]  陈小平，于盛林. 实数遗传算法交叉策略的改进[J]. 电子学报，2003，31（1）：71—74.CHEN X P，YU S L. Improvement on crossover strategy of real-valued genetic algorithm[J]. Acta Electronica Sinica，2003，31（1）：71—74.（In Chinese）