基于项目拆分决策的多模式资源投入

陆志强， 宗保氏

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

在飞机、轮船等大型工业品的装配过程中，由于产品规模较大，工艺操作繁琐等自身特点，导致传统固定站位式生产方式效率低稳定性差，从而无法满足市场需求，因此由汽车精益生产方式衍变而来的具有高效率和高稳定性特点的移动式装配生产线逐渐成为大型工业品的主流生产方式.以飞机移动装配线为例，类似于汽车移动生产线，装配线通常被划分为多个工位，飞机依次缓慢通过所有工位，按照装配计划完成全部装配作业.然而由于飞机装配工期长，线边资源特别是关键资源不再被固定在特定工位，而是整个装配线共享所有资源[1]，所以这类问题可以看作一类项目调度问题.将整个飞机装配过程抽象成一个大项目，装配线上每个工位需要完成的装配作业集合组成了飞机装配的一个子项目，在装配线资源共享条件下对这些子项目进行调度，可以看作并行执行的多项目调度问题.进一步，在实际生产中，作业往往有多种执行模式，不同的执行模式对应于不同的资源用量和加工时间，而且由于飞机装配线每个工位含有大量种类繁多的装配作业，所以合理地安排作业执行模式可以有效的节约资源缩短工期.综上所述，飞机移动装配线总装调度问题在理论上是一类具有作业多模式、约束复杂等特征，且关联资源投入的大规模多项目协同调度问题.这一类问题可以称为基于项目拆分决策的多模式资源投入调度问题(multi-mode resource investment project scheduling problem based on project splitting, MRIPSP-PS).目前尚未有针对MRIPSP-PS问题的直接研究，与经典的MRIPSP(multi-mode resource investment project scheduling problem)问题相比，MRIPSP-PS 的决策不仅涵盖了作业调度、作业模式选择与资源投入等决策，同时还集成了项目拆分决策，并且这些决策相互影响，现有求解 MRIPSP 问题的方法也无法直接应用于求解 MRIPSP-PS问题，因此对 MRIPSP-PS 问题的建模与算法研究，有重要的理论及实际意义.

显然，MRIPSP-PS 问题与MRIPSP 问题具有相关性，所以现有的MRIPSP问题的算法对求解MRIPSP-PS问题具有一定参考意义.对MRIPSP问题的研究起始于单模式下的资源投入项目调度问题(Resource Investment Project Scheduling Problem, RIPSP).Mohring[2]最早提出了RIPSP问题，并设计了精确算法对问题进行求解.通过改进Mohring的算法，Demeulemeester[3]设计了一种称为Minimum Bounding Algorithm(MBA) 的精确算法，通过算例对比证明了MBA具有更高的求解效率.Rodrigues 和 Yamashita[4]将启发式算法与类似于MBA的分支算法相结合，加快了求解速度.Rangaswamy[5]详细地介绍了一个新的基于分支定界的算法，进一步提高了求解效率.然而精确算法仅能用于小规模问题，无法有效求解大规模问题.为了求解大规模问题的，不同学者提出了各种启发式算法.Kelly[6]最早研究了启发式算法，算法包括优先规则(Priority Rule, PR)和调度生成机制(Schedule Generation Scheme, SGS)两部分.之后的学者，包括Kurtulus[7]，Boctor[8]，Lawrence[9]，分别提出了不同的优先级规则.Afshar-Nadjafi[10]引入了资源释放时间的概念，建立了一种新的多模式资源投入问题模型.Chen[11]设计了3类规则，分别用于选择作业、作业的执行模式和作业的开始时间，并通过3类规则的不同组合来尝试求解多模式资源投入问题.

然而现有的研究在应用于MRIPSP-PS问题时存在几点不足：①MRIPSP-PS问题需要对项目进行拆分，需要研究如何确定合理的拆分方案；②文献中对多模式资源投入型项目调度问题的研究较少，需要更深入研究作业模式选择和作业优先规则，以及其中涉及的时间约束与资源约束的相互影响关系.因此，针对上述问题，本文提出了包含项目拆分算法和多模式资源投入型项目调度算法的双层优化算法，上层项目拆分算法将整个项目合理的拆分成多个子项目；下层多模式资源投入型项目调度算法，通过时间因素评估函数和资源因素评估函数，提出了一种新的优先级规则.

1 问题描述及数学模型

1.1 问题描述

以飞机移动装配线为应用背景，飞机总装项目可以用节点式网络G=(V,E)表示，其中V为项目网络G中的节点集合，代表项目的作业集合，E为项目网络中弧的集合，代表作业之间的优先关系.项目由编号为j(j=1,2,…,J)的J项作业组成，另外添加作业0和作业J+1两个虚作业分别代表项目的开始作业和结束作业.

一架飞机所需的全部装配作业及优先关系如图1所示.飞机缓慢通过整个装配线，同时利用装配线两侧的装配资源，按照装配调度计划完成总装所需的全部装配作业任务.

图1 单架飞机总装作业

装配线对多架飞机同时进行装配，每隔一个装配节拍，一架飞机完成装配离开生产线，同时一架待装配飞机进入生产线.为了对装配线上的多架飞机进行调度建模，同时满足装配节拍的周期性调度，可以将装配线上各个工位对应为多个“虚拟大工位”，进而把一架飞机所包含的全部装配作业合理的分配给这些“虚拟大工位”，每个“虚拟大工位”对应一个装配作业子集合，称为子项目.例如以图1中的虚线为界，将飞机总装作业划分为3个子项目，划分后的示意图如图2所示.

在此情形下，一方面，对一架飞机来讲，它通过了整个装配线也就通过了所有子项目，完成所有需要的装配任务；另一方面，每隔一个装配节拍，装配线当前子项目位置上的飞机完成对应作业子集中所有任务后进入下一个子项目(或者装配完成离开生产线)，同时后一架飞机进入当前子项目位置.由于各个子项目的装配过程在时间上是不同的，这多个子项目可以作为并行开展的多个项目共享整个装配线的资源，这样既实现了资源在项目内和项目间的共享，又使得资源的分配计划符合装配节拍的周期性要求.显然，装配线的资源投入量取决于子项目划分决策和划分后多个子项目的资源投入调度计划.

图2 飞机总装作业子项目拆分

1.2 数学模型

不同于单模式问题，在作业多模式条件下的资源投入调度问题中，作业j有m(m=1,2,…,M)种执行模式，分别对应的执行时间为djm，全部作业共享K种可更新资源，rjmk(k=1,2,…,K)表示作业j按照模式m需要第k中资源的数量.Pj表示作业j的紧前作业集合，作业h(h∈Pj)表示作业h为作业j的紧前作业，Sj表示作业j的紧后作业集合.按照从左到右的顺序，定义第i个“虚拟大工位”对应的作业任务集合记为子项目i(i=1,2,…,N).项目节拍周期记为C，对时间离散化处理，时间点集合T={t|t=1,2,…,C}，设U为一个足够大的正数.

MRIPSP-PS问题要求在满足作业优先关系约束和节拍周期约束的前提下，确定作业的所属子项目和作业的开始时间，与基本RIPSP问题一样，MRIPSP-PS问题的目标函数也是项目资源投入最小化.

项目资源投入记为A，具体决策变量如下：Yij为0，1变量，作业j属于子项目i为1，否则为0；xjmt为0，1变量，作业j在选择模式且在时刻完成为1，否则为0.

目标函数：

(1)

约束条件：

∀i∈N,∀j∈J,∀h∈Pj,∀t∈T

(2)

(3)

U(2-Yij-Yih), ∀i∈N,∀j∈J,∀h∈Pj

(4)

(5)

(6)

xjmt≤C,∀j∈J,t∈T

(7)

其中，式(1)表示问题的目标函数为最小化资源投入；式(2)表示在拆分决策中，任意作业的紧前作业不能被分配到该作业所在子项目的后续子项目中；式(3)表示一项作业只能在一种模式下被执行一次；式(4)表示优先关系约束，任意一项作业开始时间必须大于所有实际有效紧前作业的完成时间；式(5)表示任意一项作业能且仅能被分配到某一个子项目中；式(6)表示资源实际用量，项目所需资源量必须大于或等于任意时刻所有在执行作业的资源使用总量；式(7)表示工期约束，任意作业必须在项目工期内完成，不能延期.

2 PSS-JRTS双层迭代算法

根据模型的决策变量，需要做出两种决策，针对决策变量Yij的决策称为拆分决策，针对决策变量xjmt的决策称为多模式资源投入项目调度决策.基于项目拆分决策的多模式资源投入问题不仅要决策作业的所属节拍，还要决策作业的执行模式及开始时间，因此本文提出一种双层迭代算法，PSS-JRTS算法 (project split scheme，joint resource and time scheme)，上层PSS(project split scheme)算法包含项目初始拆分策略和作业移动调整策略，通过对不断有效调整拆分结果获得合理的拆分方案， 下层JRTS(joint resource and time scheme)算法通过分析安排不同作业时对项目时间约束和资源约束的影响来确定作业的优先级规则.

2.1 算法整体步骤

算法的整体结构：上层PSS算法划分作业的所属子项目，下层JRTS算法确定作业的执行模式及开始时间来生成调度方案，具体步骤如下：

(1)调用上层PSS算法的项目初始拆分策略，将项目中所有作业划分到N个子项目中，初始化项目拆分结果Yij，设置拆分调整迭代次数Iiter=100，z表示当前迭代次数，初始化为零，项目资源投入记为Abest，初始化为无穷大.

(2)调用下层JRTS算法对当前拆分方案求解，更新xjmt，得到当前方案的资源投入A′.若A′

(3)若z

(4)输出Abest.

2.2 上层PSS算法

为了获得一个合理的拆分方案，本文采用一种先将项目作初始拆分，再不断调整拆分结果的启发式算法.项目初始拆分策略将项目拆分为N个子项目，使得每个作业都属于且仅属于某一个子项目.在每次迭代中，通过将某个子项目中的一个作业移动到其它子项目的方式来调整拆分结果，获得不同的拆分方案.

2.2.1项目初始拆分策略

初始拆分策略是要在满足作业优先关系的其条件下将作业划分到N个子项目中，本文采用了基于CPM(critical path method)的初始拆分方案[12].对未拆分的初始项目，由CPM生成满足优先关系的调度方案，得到每个作业的结束时间tftj，其中，作业的工期均采用作业所有模式的平均工期计算.为了将项目拆分成N个可行的子项目，按照关键链工期长度tftJ+1将项目拆分成N份.定义时间截断区间长度L为

(8)

对每一个作业，按照以下方案分配到子项目中：

(9)

由于CPM得到每个作业的结束时间tftj均小于其紧前作业的结束时间，这样的拆分方案保证了任意作业的紧前作业不会被分配到该作业所在子项目的后续子项目中，从而使得拆分方案可行.

2.2.2拆分调整策略

按照初始拆分策略将项目拆分为N个子项目后，通过在不同子项目间移动作业来调整拆分结果，获得新的拆分方案.每次移动需要确定两个变量，包括从哪一个子项目中移出作业和确定此子项目中的可移动的作业.为了获得一个较优的拆分方案，使目标函数最小化，那么应该避免在拆分方案中出现各个子项目中作业个数分布差异过大的情况.本文设计了一种考虑子项目中作业个数分布情况的优先规则来决策每次迭代中用于移出作业的子项目.同时，根据不同子项目中作业的可移动条件来确定可移动作业的集合，最终从可移动作业的集合选定要移动的作业.

用mi表示子项目i的作业个数，αi表示选择子项目i作为移出作业子项目的概率：

(10)

图3 子项目n中可移动作业

(1) 若n=1，图3表示第一个子项目，此时子项目的作业只能向后移动到子项目2中，不能前移.图3中作业14和作业15可以移动，而作业7—13都存在有效紧后作业，不能直接移动.即子项目1中的作业需满足紧后作业为空时才能移动，则有

∅∩Y1j=1,∀j∈J}

(11)

(2) 若1

Ynj=1,∀j∈J} (1

(12)

(3) 若n=N，此时图3表示最后一个子项目，子项目中作业只能前移到子项目n-1中，不能向后移动.图3中作业7、8、9可以前移，其他作业都不能移动，即子项目N中的可移动作业集FN为

∀j∈J}

(13)

当选定子项目来移出作业，本文按照每次从可移动作业集Fn中移动一个作业到其他子项目的方式来调整项目拆分方案，得到新的拆分结果Yij.

2.3 下层JRTS算法

通过上层PSS算法，将项目拆分为多个并行的子项目，如图2所示，下层JRTS算法需要确定作业的执行模式以及开始时间，即决策变量xjmt.本文采用启发式算法[6]，包含进度生成机制和优先级规则两部分.其中进度生成机制为串型进度生成机制(serial schedule generation scheme, SSGS)，而传统的优先级规则涉及到选择每一次要排的作业以及这个作业的开始时间和执行模式.选择不同的作业、不同的执行模式和不同的开始时间，会对调度计划产生不同的影响，主要包括对时间约束的影响和对资源约束的影响.本文提出一种同时考虑资源与时间调度(JRTS, joint resource and time scheme)的函数，分别分析作业安排对两种约束的影响，设计了一种有效的优先级规则，同时决策要排的作业以及相应的执行模式和开始时间.

2.3.1时间因素评估函数

时间因素评估函数用于评价作业的安排方案对时间约束的影响.根据CPM可以得到作业j的最早及最晚开始时间，分别对最短工期模式(shortest duration mode)和最长工期模式(longest duration mode)得到的变量做出如下定义：tSESTj为最早开始时间(最短工期模式)；tSLSTj为最晚开始时间(最短工期模式)；tSLFTj为最晚结束时间(最短工期模式)；tLTFTj为最晚结束时间(最长工期模式).如图4所示，作业j的执行时间应在时间窗[tSEST,tSLFTj]内，且当位于时间窗的前半段[tSESTj,tLTFTj]内时，因为不超过最长工期模式下的最晚结束时间，所以作业j的后续作业均可以选择所有的执行模式执行而不会延期.当作业j的执行时间位于[tLTFTj,tSLFTj]内时，超过了最长工期模式下的最晚结束时间，此时若作业j的后续作业均按照最长工期模式执行，必然无法在项目总工期内完工，引起延期.极端情况为作业j的完工时间为tSLFTj，此时作业j的后续作业只能选择最短工期模式执行，否则必然引起延期.

综合考虑作业j的执行时间处在不同位置是对后续作业的影响，当作业j以模式m在t时刻开始的时间因素评估函数为

(14)

图4 作业j的可排区间

式(14)中tft(j,m,t)=t+djm，表示作业j以模式m在t时刻开始的结束时间，分母用于标准化最大值为1.当作业j在tLTFTj结束时，ftime(j,m,t)为0;随着结束时间的推迟，ftime(j,m,t)会逐渐增大，且当作业在tSLFTj时刻结束时，ftime(j,m,t)取最大值1；若ftime(j,m,t)大于1时，说明后续作业必然引起延期，表示作业j以模式m在t时刻开始不可行，且时间因素评估函数的值越小越好.

2.3.2资源因素评估函数

资源因素评估函数用于评价作业安排对资源约束的影响.对于一个局部进度计划，Rrt表示时刻t时资源k的消耗量;Rke表示时刻e时资源k的消耗量.项目中资源k的投入成本Ik可以表示为

Ik=MaxRkt

(15)

Max{Rke+rjmk|t≤e

(16)

假设此时的资源投入上限为RRIL，则资源因素评估函数为

∀j,∀m

(17)

同样的，式(17)中分母用于标准化函数的最大值为1.安排作业j以模式m在t时刻开始，若不增加额外的资源投入，fresource(j,m,t)的值为零；若增加额外的资源投入，fresource(j,m,t)的值增大，且在达到资源投入上限RIL时，取得最大值1；若fresource(j,m,t)大于1，表示此时资源约束被破坏，作业j以模式m在t时刻开始不可行.类似于时间因素评估函数，资源因素评估函数越小越好.

2.3.3时间-资源综合评估函数

ftime(j,m,t)和fresource(j,m,t)分别表示安排活动时面临的时间影响和资源影响.将两个因素结合考虑，作业j以模式m在t时刻开始的时间-资源综合评估函数为

ftotal(j,m,t)=

(18)

在式(18)中，condition条件为11表示存在约束被破坏.若资源约束和工期约束均未被破坏，则ftotal(j,m,t)取时间因素评估函数和资源因数评估函数的平均值，易知此时ftotal(j,m,t)的取值范围是[0,1]；若某一个约束被破坏，即作业j以模式m在t时刻开始不可行时，将ftotal(j,m,t)赋值为2.应用式(18)，选择j,m,t的步骤：

(1)对每个待选择的作业，选定它对应于最小综合评估函数值的模式和开始时间，这表示若选择此作业时的最优选择.

(2)对于所有确定了模式和开始时间的待选择作业，选择最大综合评估函数值的作业.这样，综合评估函数值最大的活动最先排，对后续作业的影响最下，避免安排后续作业时使得解变差，即

(19)

在串行调度阶段，进度生成机制按照每一步排入一个作业的方式，将所有作业排入进度计划中.其中，每一步需要决策将要排入调度计划的作业和作业的执行模式与作业的开始时间.应用式(19)，可以综合时间约束和资源约束，选择合适的作业和作业的执行模式与作业的开始时间.

2.3.4JRTS算法步骤

JRTS算法采用先设定一个较低的资源投入上限RRIL，在此RRIL下，应用串行进度生成机制和由式(19)确定的优先级规则对拆分后的多个子项目进行调度求解.若根据式(19)选定的j,m,t使得式(19)中ftotal(j,m,t)>1，即不可行时，不断增加资源投入上限RRIL，并重新进行调度求解，直到求出可行的最小RRIL，具体步骤如下：

(1)初始化已排作业集合SAS=∅,可排作业集合SCS=∅,待排作业集合SWS=J，初始化Rrt为均为零，设定初始资源投入上限RRIL=0.

(2)更新可排作业集合，调用式(19)选择j,m,t.

(3)判断是否可行.若ftotal(j,m,t)>1，即不可行时，RRIL=RRIL+1，并转入(1)；若ftotal(j,m,t)≤1，则转入(4).

(4)将作业j以模式m安排在t时刻开始，并更新Rkt，更新SAS,SCS和SWS.

(5)若待排作业集合SWS=∅，表示作业已排完，则转入(6)；否则，转入(2).

(6)输出资源投入最小值A=RRIL.

3 数据实验

选用PSPLIB标准算例库中的算例进行算法测试，运用PyCharm(Python 3.5.3)开发环境编程，仿真测试平台为Intel Core i7-4790处理器，12G内存.现有文献中关于MRIPSP-PS的研究较少，为了验证本文算法的有效性，选择多模式资源首相项目调度问题MRCPSP (Multi-Mode Resource-Constrained Project Scheduling Problem)问题中常用的优先规则构建对比算法[13]，其优先规则通常包含两类:①优先级规则用于选择每次要排的作业;②优先级规则用于选择作业的执行模式和开始时间.

3.1 基于优先级规则的启发式算法

基于优先级规则的对比算法通过串行进度生成机制生成调度计划，每次应用作业优先级规则选定要排的作业，再调用作业模式和开始时间优先级规则将作业排入调度计划中.具体规则如表1所示：

表1 两类优先级规则

表1中的规则中最小松弛时间规则表示RMST；最晚完成时间规则表示RMLTT；最小额外投入规则表示RMEI；同时上述三种规则可以组成MST-MEI和MLTT-MEI两种启发式算法，本文将分别针对不同规模算例与两种对比算法比较.

3.2 数据对比

表2 J10实验结果

表3 J20实验结果

为了在更大的规模下对比算法的有效性，在PSPLIB问题库的基础上，将30个作业的算例串联，分别构造出包含60个作业和90个作业的大规模算例，进一步对算法的性能进行对比，实验结果如表5～表6所示.

从表2～表4的数据实验结果可以看出，在小规模的问题下，本文算法领先于MST-MEI算法和MLTT-MEI算法，说明本文算法可以发挥资源评价函数和时间评价函数的综合优势，使作业按照较优的方式安排.同时，两种对比算法，尤其是MLTT-MEI算法的结果在小规模问题中非常接近本文算法，这也说明本文选择最晚作业结束时间规则作为对比算法是正确的.而且针对不同的拆分数量N，实验结果显示本文算法都得到更优的解，证明了其稳健性.

表4 J30实验结果

在图5的图例中，MST_N2和MST_N3分别表示在拆分个数分别为2和3时，每组算例平均领先对比算法的百分比.在问题规模从10增加到30时，本文算法的GAP从2%左右提高到4%以上，而且对比不同的对比算法都展现出有效的竞争力.同时，在不同拆分个数下，本文算法都能取得稳定的领先.在60和90个作业的大规模问题下，本文算法领先对比算法的GAP稳定在4%左右，而且对比不同的拆分个数和不同的对比算法，本文算法均能保持不低于3%的领先.

表5 J60实验结果

表6 J90实验结果

图5 不同规模算法提高百分比

4 总结与展望

研究了飞机移动装配线作业调度的作业执行多模式问题，建立了包含项目拆分和多模式资源投入项目调度的数学模型，提出了合理的项目拆分策略和基于时间-资源综合评估规则的启发式算法.通过数据实验，PSS-JTRS算法可以发挥资源评价函数和时间评价函数的优势，能够比其他启发式算法更好的对问题进行求解.在以后的研究中，可以考虑依次启发式算法为基础，进一步加入遗传算法、模拟退火算法等元启发式算法，使算法加入搜索机制，对飞机移动装配线作业调度问题进行更系统的优化.