基于T-SSA算法的流水车间订单调度问题研究

王 婷，毋 涛

(西安工程大学 计算机科学学院，陕西 西安 710048)

0 引 言

随着中国经济社会的发展，产品定制服务的出现，消费者个性化需求也日益凸显，有一部分制造型企业开始采用订单生产模式[1](make-to-order，MTO)，比如西装定制、船舶制造。

在MTO生产模式中,订单内不同的工件的交货期不同，而制造型企业通常都是配备固定的车间、机器和人员，订单调度决策往往受车间生产能力的制约。在这种情况下，这种决策往往会与实际生产有所偏差，造成计划外的生产成本(如加班、外包)和拖期罚金，导致企业信誉受损，客户满意度降低。

为提高订单交付的准时率,企业需要在有限产能下对订单生产作业进行合理的计划安排和调度，依据订单产品的要求交期及时交付产品，履行合约。研究基于流水线车间的订单调度问题可以有效提高企业的生产效率和竞争力，对于处于MTO生产模式的企业制定出合理有效的订单调度决策，及时交付作业具有重要的研究意义。

长期以来，混合流水车间调度问题[2](hybrid flow shop scheduling problem，HFSP)被证明是一个经典的NP难题。目前，求解HFSP的算法主要包括遍历式算法、构造型算法和智能化优化算法，其中遍历式算法可以求解出该类问题的精确解，但计算速度较慢；构造型算法在求解该类问题时运算速度较快，但算法结构复杂且通常无法求解出全局最优解[3]；优化算法有严格的理论基础，能在短时间内解决问题的最优或理想解。智能优化算法[4]主要有混合萤火虫算法(hybrid firefly algorithms，HFA)[5]、最佳觅食算法(optimal foraging algorithm，OFA)[6]、离散狼群算法(discrete wolf pack algorithm，DWPA)[7]、离散布谷鸟算法(cuckoo search，CS)[8]、改进蛙跳算法(shuffled frog leaping algorithm，SFLA)[9]、果蝇优化算法(fruit fly optimization algorithm，FOA)[10]、混合鱼群算法(hybrid artificial fish swarm algorithm，HAFSA)[11]、人工蜂群算法(artificial bee colony algorithm，ABC)[12]等等，已经广泛应用于解决各种生产调度问题。

麻雀搜索算法[13](sparrow search algorithm，SSA)是一种新型的群智能优化算法，主要是受麻雀的觅食行为和反捕食行为的启发。针对SSA的研究表明，该算法在不同的搜索空间中具有良好的性能。在SSA的基础上，文中提出了基于生产环节生产线两段式麻雀搜索算法(two-vector sparrow search algorithm，T-SSA)，并将T-SSA实际应用于流水车间订单调度问题中，验证了该算法的有效性。

1 问题描述与建模

1.1 问题描述

1.2 模型的假设条件

(1)在初始时间(设置为0)，可以处理任何订单任务。

(2)同一生产线的同一时间只能加工1件产品。

(3)不同的订单任务之间没有先后约束。

(4)在生产过程中，订单前一个生产环节被处理完成后，会立即进入下一个生产环节进行处理；如果下一个生产环节生产线正在工作，则订单进行等待。

(5)每两个处理环节之间有足够的缓存空间，允许产品在处理环节之间停留和等待。

(6)订单调度过程为非抢占式调度。

(7)订单任务中各生产环节的交货时间和利润值均为已知量(交货时间从初始时间0开始计算)。

根据上述解释和假设，研究的问题是：确定订单的加工顺序和各生产环节的生产线分配，从而使加权订单完成时间最小化。

1.3 参数和变量说明

i：表示待加工工件编号。

j：表示待加工的生产环节序号。

k：表示每个生产环节的生产线编号。

Mj：第j个生产环节并行生产线的集合。

NMj：第j个生产环节并行生产线的数量。

MPij：工件i在第j个生产环节可用的生产线集合，MPij⊆Mj。

tijk：工件i的第j个生产环节在生产线k上的加工时间。

stijk：工件i的第j个生产环节在生产线k上的开始加工时间。

etijk：工件i的第j个生产环节在生产线k上的结束加工时间。

xijk：当工件i的第j个生产环节在生产线k上的加工时xijk=1；否则xijk=0。

rjk：第j个生产环节在生产线k上加工的第r个任务的工件编号。

Ti：工件i的各生产环节加工时间总和。

1.4 模型构建

根据问题描述，采用最小最大订单完成时间为目标函数，可转化为求解订单内工件集的最小化完成时间，即一个工件完成时间的最小值，模型构建具体如下：

(1)

模型描述如下：

etijk≤sti(j+1)k*；i=1,2,…,n;j=1,2,…,s;

k∈MPij;k*∈MPi(j+1)

(2)

etijk=stijk+tijk；i=1,2,…,n;j=1,2,…,s;

k∈MPij

(3)

(4)

r=1,2,…,Njk-1

(5)

若rjk=i，则：

其中：

k∈MPij，k-∈MPi(j-1)，r=1,2,…,Njk

(6)

(7)

xijk∈{0,1},xijk-=1,∀i,j,k,r

(8)

(9)

公式(1)是最小化工件完成时间的公式和目标函数；公式(2)表示在前一个生产环节完成后，才可以在下一个生产环节中进行加工；公式(3)表示每个工件的加工完成时间，其中每个生产环节的加工结束完成时间取决于该生产环节的开始时间和加工时长；公式(4)表示工件的每个生产环节只能选择该生产环节的一台生产线进行加工；公式(5)表示一条生产线同时只能加工一个工件；公式(6)表示当工件i是第j个生产环节在生产线k上处理的第r个任务时，生产环节开始时间取决于该工件前一个生产环节的结束时间与本生产线的前一任务结束时间；公式(7)表示每个工件的完成时间等于工件在最后一个生产环节中的完成时间；公式(8)为变量取值范围；公式(9)表示每个工件每个生产环节加工时间的计算关系，即工件的总加工时间。

2 麻雀搜索算法(SSA)

麻雀搜索算法是一种基于麻雀觅食行为和反捕食行为的新型群体智能优化算法，其仿生原理如下：

在麻雀觅食的过程中，将整个麻雀种群分为发现者和加入者两种角色，叠加了侦查预警机制。发现者在种群中负责寻找食物并为整个麻雀种群提供觅食区域和方向，而加入者则是利用发现者来获取食物。为了获得食物，麻雀通常可以采用发现者和加入者这两种行为策略进行觅食。种群中的个体会监视群体中其他个体的行为，并且该种群中的攻击者会与高摄取量的同伴争夺食物资源，以提高自己的捕食率。此外，当麻雀种群受到捕食者的攻击时会做出反捕食行为。

SSA算法的具体流程见图1。

图1 麻雀搜索算法流程

Step1：初始化麻雀种群。

Step2：设置发现者规模，将种群分为发现者和跟随者。

Step3：(发现者位置更新)当预警值小于安全值的时候，即觅食环境没有捕食者时，发现者位置随机更新；若预警值大于安全值，种群中的一些麻雀已经发现了捕食者，并向种群中其他麻雀发出了警报，此时所有麻雀都需要迅速飞到其他安全的地方进行觅食。更新方式如公式(10)：

(10)

上式表示种群中第t代中的第i个个体的第j维位置信息，α和Q是服从不同分布的随机数。itermax、R2、ST分别表示最大迭代次数、预警值和安全值。

Step4：(跟随者位置更新)若当前跟随者处于十分饥饿的状态，则需要飞往其他地方觅食，以获得更多的能量，进行位置更新；否则，跟随者是围绕最好的发现者周围进行觅食，期间也有可能发生食物争夺，使自己成为生产者。更新方式如公式(11)：

(11)

其中，Xp是目前发现者的最优位置，Xworst是当前全局最差的位置，n是种群大小。

Step5：(随机选择警戒者并更新位置)当任意麻雀意识到危险靠近时，它们会放弃当前的食物，即无论该麻雀是发现者还是跟随者，都将放弃当前的食物而移动到一个新的位置，处于种群外围的麻雀向安全区域靠拢，处于种群中心的麻雀则随机行走靠近别的麻雀。更新规则如公式(12)：

(12)

其中，Xbest是当前的全局最优位置，fg和fw分别是当前全局最佳和最差的适应度值，fi是当前麻雀的适应度值，ε、β、K是不同随机常数。

Step6：判断是否达到最大迭代次数，若达到，则输出最优适应度值，即所求问题的最优解，否则转到Step2。

3 基于T-SSA算法的模型求解

针对流水车间订单调度问题采用基于生产环节和生产线的两段式编码方式来表示麻雀种群中麻雀的位置。应用其设计的初始化种群方式初始化种群，对麻雀的智能行为进行重新设计；则基于两段式麻雀搜索算法的流水车间订单调度问题的具体操作如下：

3.1 编码方式

图2 两段式编码示意图

生产环节编码的编码长度为总生产环节数，基因位上的数字表示工件号，相同工件号出现的次数对应工件的第几个生产环节。图2中表示的工件加工顺序为：工件3→工件2→工件3→工件1→工件2→工件3→工件2→工件1→工件1，其中每个工件出现三次，即每个工件有3个生产环节，比如基因位1上的数字3，表示工件3的第一个生产环节，基因位3上的数字3，表示工件3的第二个生产环节，诸如此类。

生产线编码的编码长度与生产环节编码长度一致，也是总生产环节数，基因位上的数字代表前半段对应的生产环节可以选择的生产线集合中的第几条生产线。图2中表示选择的生产线顺序依次为：生产线M1→生产线M2→生产线M3→生产线M1→生产线M4→生产线M6→生产线M5→生产线M4→生产线M6，基因位10位上的数字1表示工件3的第一个生产环节选择生产线M1加工，基因位12上的数字1表示工件3的第二个生产环节上选择生产线M3加工，以此类推。

[3,2,3,1,2,3,2,1,1,1,2,1,1,2,2,1,2,2]整个整数段表示一只麻雀个体。

3.2 种群初始化

在麻雀搜索算法中，多样性好的初始解集能够有效提高运算效率，扩大搜索范围，避免局部收敛的情况发生。考虑到两段式编码的特点，先采用随机初始化方式产生足够多的麻雀个体，确保种群的多样性，然后使用轮盘赌选择机制选取所需数量的初始个体，确保种群的质量。采用权重法计算个体被选取的概率，优先选择收益高、交期紧、订单权重大的工件个体，工件选择概率越大，个体越容易被选用。

(13)

(14)

3.3 适应度函数

以最小化最大订单完成时间为目标函数求解流水车间订单调度问题，主要思想是订单内的每个工件的完成时间最优，可以将该问题转化为求解订单内工件集的最小化最大完成时间为适应度函数，工件最大完成时间越小，表示个体的适应度值越好，即fitness=min{Cmax(P)}。

3.4 智能行为设计

文中以最小化最大订单完工时间为目标函数来确定最优订单调度方案，即订单中工件的生产环节排序和生产线选择方案。结合HFSP的特性，对两段式麻雀搜索算法中的具体定义如下：

(1)最优最差麻雀选择机制。

记录第i只麻雀个体的适应度函数为Fiti，根据适应度值对麻雀个体进行排序，那么取全局最差适应度值为worseF=max(Fiti),i=1,2,…,n，worseF对应的全局最差位置为worseX；最优麻雀个体对应的适应度值为bestF1=min(Fiti),i=1,2,…,nbestF1对应的全局最优位置为bestX1。

(2)发现者移动机制。

根据设置麻雀发现者个体的比例PR，从种群中随机取出发现者的个体数量。将随机预警值R2与发现者警戒阈值ST进行比较，若R2

(3)跟随者跟随机制。

(4)侦察预警机制(警戒者)。

对意识到危险的个体称为警戒者，并不代表出现了真正的捕食者。随机指定个体j，取该个体的适应度值为Fitj，若Fitj>bestX1，表示此时的麻雀正处于种群的边缘，极其容易受到捕食者的攻击，位置跳跃性比较大，警戒者位置更新；若Fitj=bestX1，表明处于种群中间的麻雀意识到了危险，需要靠近其他的麻雀以此尽量减少它们被捕食的风险。

3.5 T-SSA算法迭代过程

根据智能行为设计的4大机制，可将使用T-SSA算法求解流水车间订单调度问题的步骤概括如下：

Step1：初始化算法相关参数。设置种群的规模大小为pop，最大迭代次数为itermax，发现者比例为PR，侦查者比例为SD，预警值为R2，发现者警戒阈值为ST。

Step2：根据初始化方案进行种群初始化，确定麻雀个体的位置编码。

Step3：依据设定的PR，将种群分为发现者和跟随者。计算个体的适应度值Fiti，进行排序，并取出种群最优位置bestX1和最差位置worseF对应的适应度值bestF1、worseF。

Step4：将预警值R2与警戒阈值进行比较，更新所有发现者位置，淘汰掉边缘个体，迭代并计算发现者的适应度值。取出发现者的最优位置bestX2对应的适应度值bestF2。

Step5：依据跟随者的编号，判断跟随者的状态，淘汰边缘个体，跟随者进行随机位置更换，或者抢夺最优发现者bestX2成为发现者。迭代，计算所有跟随者的适应度值。

Step6：判断随机警戒者所处位置是否在种群中心，若处在中心，向最差位置worseF个体移动位置，淘汰边界个体，更新警戒者的适应度值。

Step7：求解最新全局个体适应度值，替换最优位置bestX1及其响应的适应度值bestF1。

Step8：判断是否达到最大迭代次数，若达到，则输出最优适应度值，即所求问题的最优解，否则转到Step4。

4 算法验证与分析

实验仿真环境为操作系统Windows8、处理器Intel(R) Core(TM)i5-4210U CPU @ 1.70 GHz 2.40 GHz、内存12G，采用Matlab R2018a。

4.1 算法仿真验证

采用以下两种方式验证算法的有效性：

(1)实例验证一。

图3 TSSA算法测试甘特图

由图可知，两段式麻雀搜索算法甘特图调度结果显示46小时可完成6个工件的生产，与文献[13]中优化的SA-PSO-GA调度效果相同，均优于传统的PSO-GA算法。将T-SSA算法的迭代曲线与原文献比较，PSO-GA算法和SA-PSO-GA更易陷入局部最优，输出的解并非实际最优解。从运行时间上来看，由于T-SSA达到最优的迭代次数较少，运算时间为14-17S，在效率上明显高于原文中提到的算法。

(2)实例验证二。

设置9种不同规模的调度算例，随机生成订单数量、订单权重、订单收益，订单中的工件数量合计分别为20、50、100,生产环节数为2、4、8，生产线条数分别合计为5、10、20，工件交期根据EDD规则[15]与经验设置。数据结果与4.2中的数据格式类似。对生成的订单数据进行处理，得到算例规模n×s(m)，n表示工件数，s表示生产环节数，m表示生产线总数。

使用相同的算法参数和编码方式对人工蜂群算法(ABC)[12]、两段式麻雀搜索算法(T-SSA)进行9次实例验证比较。仿真结果如表1所示，在不同规模的算例中，T-SSA求解的最小值、平均值基本优于ABC算法，体现出了明显的搜索能力。

表1 实例运行结果统计(最小值、平均值单位：小时)

其中某一次的迭代曲线如图4所示，实验结果基本类似，ABC的最优解T-SSA均可在相近迭代次数到达，且最优解的消耗时长接近。结合表1和图5可以看出，T-SSA的最优解质量更好，表明该算法的搜索能力更强，更进一步证明了该算法的有效性和优越性。

图4 订单调度迭代图

4.2 订单调度实例应用验证

结合上海某西装定制企业的流水车间生产过程为实例作为研究对象，验证订单调度模型和两段式麻雀算法的有效性。该生产企业的西装定制生产过程可描述为有限并行生产线混合流水车间，所有西装定制产品从加工到结束，主要分为五个环节：裁剪有2条生产线(M1，M2)；缝制有3条生产线(M3，M4，M5)、手缝有3条生产线(M6，M7，M8)、整烫有2条生产线(M9，M10)，检验有2条生产线(M11，M12)。此处忽略不同工件的规格、生产工艺在每个加工环节的局部差异。本次选取该企业一次实际生产任务为实验对象，共有8个客户订单，合计20个待加工工件，订单权重、交货期、工件收益已知。假设所有订单在0时刻接受，且所有生产线环境运作正常，物料库存充足。模拟订单信息数据如表2所示，表3为订单对应的西装企业生产工时数据。

表2 订单信息

表3 上海某西装定制企业生产工时(单位：小时)

使用T-SSA算法进行实例调度，设置种群数量分别为30、60、100，最大迭代次数为500，发现者警戒阈值为0.8，发现者比例为20%，重复多次计算以上订单实例。

续表3

各种群规模随机取20次运算结果统计如表4所示，最优迭代次数均在150代以内，运算时间较短。实际结果表明，种群增大可以有效减少迭代次数，得到目标值。

表4 实例运行结果统计

目前该企业还是通过传统的Excel和人为经验制作订单生产排程，人工负荷调整工作量巨大，采用这种方式进行以上实例调度编排企业应用总共耗时450分钟，使用T-SSA算法运行实例，最差结果也是少于450分钟的，验证了两段式麻雀搜索算法结果流水车间订单调度问题的实用性和有效性。

5 结束语

针对流水车间订单调度问题，建立单目标数学模型，采用两段式双层编码的麻雀搜索算法进行问题求解，对发现者、跟随者、警戒者三种角色采用不同的机制更新策略。算法很好地挖掘了全局最优潜在区域的能力，从而有效地避免了局部最优问题。将T-SSA算法与文献[10,12]中的算法进行模拟比较，验证了算法的有效性和优越性。采用企业订单调度实例测试T-SSA，更近一步验证了T-SSA的有效性和实用性。不足之处是，T-SSA在求解大规模应用时，耗时稍微长一些，可对算法进行进一步的研究，将其扩展使用在更复杂的调度问题中，例如多目标调度问题。