服装企业包装订单分配排序优化模型及其快速非支配遗传算法求解

潘佳豪， 周其洪， 岑均豪， 李姝佳， 周申华

(1. 东华大学 机械工程学院， 上海 201620； 2. 东华大学 数字化纺织服装技术教育部工程研究中心， 上海 201620； 3. 广州盛原成自动化科技有限公司， 广东 广州 511400)

在制造业全球化程度不断加深，工业化以及信息化不断进步的背景下，从生产到出货的各个环节的细节入手，提高效率，缩短产品交付期将成为企业提高竞争力的有效手段。我国纺织服装行业经过近年来的发展，硬件自动化已趋成熟，部分企业正在向智能化迈进；但在软件方面，许多纺织服装制造企业的制造管理系统(MES)尚不成熟，计划和成本控制对象细化程度不足，与企业资源计划系统(ERP)的集成以及数据互联存在一定的问题[1]。

当前的市场环境下，客户需求逐渐多样化，对于款式更迭导致生产内容常变的服装生产企业更是如此。当下的服装生产企业采用订单式生产模式(MTO)，其运营模式具有多品种、多急单插单等特点[2]。订单包装是服装产品出货前的最后步骤，需结合订单与库存情况安排包装顺序，提取对应产品组合并送至包装线打包，在规定时间内完成出货。客户企业的包装需求组合多样，当一定时间内多个订单同时到达时，订单组成状况较为复杂。针对客户的需求整理订单、分配包装任务、优化订单排序就显得尤为重要。

并行机分配与订单排序问题涉及到任务分配、平衡、优化排序等多个方面，是一类NP-hard问题。在订单分批、分配、排序的思路方面，一般采用根据目标和约束条件建立混合整数规划模型(MILP)的方法建立合理的数学模型，以解决目标多种多样的分配调度问题[3]；基于精益生产(JIT)装配模式的思想可用于对大批量多品种订单次序进行优化，提高订单分拣的效率[4]。

在算法方面，遗传算法(GA)及其改进后的非支配遗传算法(NSGA-Ⅱ)[5-7]、果蝇优化算法[8]、多目标进化算法[9]、贪婪算法[10]等较常用的智能优化算法在解决以缩短交期或平衡排序为目标的订单排序动态优化问题方面得到了较多的应用；于此同时，新的算法也在不断提出。固定变量列表算法(FVLA)用于解决不能忽略与序列相关的设置时间的顾客订单调度问题，具有优秀的求解质量[11]；在杜鹃搜索算法(CSA算法)基础上改进的算法(ICSA)用于求解并行机最大完成时间问题，相对于多种常用算法都具有更优的求解性能[12]；在樽海鞘群优化算法(SSA算法)基础上改进的(SSAFA)算法用于求解以最小化最大完工时间的带启动时间非相关并行机调度问题(UPMSP)，在不同规模大小的算例求解上均有较好的性能[13]。从已有研究来看，将服装包装线订单分配与排序问题转换为相近的并行机调度问题，再应用收敛性好的智能优化算法进行排序求解是解决问题的关键思路。

本文针对纺织服装生产企业包装出货过程的优化需求，为解决包装车间中包装订单在包装线上分配以及排序问题，对服装产品订单包装出货过程中的问题特点与约束条件进行分析并建立相应的调度优化模型，运用NSGA-Ⅲ算法对其进行优化求解，以实现包装车间包装线工作平衡和出货时间优化。

1 服装企业包装订单排序优化模型

1.1 纺织服装生产企业订单包装排产现状

纺织服装生产企业采取面向订单为主，辅以部分面向库存(MTS)的生产方式进行产品的生产，发货时根据客户订单需求对相应数量种类组合的产品进行出库、装箱并发货。考虑到一定时间内到来的订单交货期不尽相同，当前企业常用交货期优先(EDD优先)规则对包装订单进行分配，即在接收到一系列包装出库订单时，首先采用EDD顺序对该组订单进行预先排序，然后从交货期最早的订单开始分配包装线，直到所有包装线均有一个订单在处理；当有包装线完成包装时，将未分配的EDD顺序最前订单分配到该空闲包装线，依次类推，直到该组订单全部完成。此分配与排序方式带有部分贪婪算法的性质，在一定程度上可保证交期，但无法尽可能缩短总处理时间，且部分订单可能出现物流无法弥补的长拖期时间。

1.2 服装企业订单包装出货过程问题描述

对于服装企业的包装车间，一般存在多条包装线可用，在一个时间段中的多条包装订单将按照一定策略被分配到可用的包装线上进行包装。此类订单分配与排序问题特点如下：n个订单分属于g个客户，需要分配到m条包装线上完成包装，每个订单可在任意1条包装线上进行包装。就企业当前生产实际情况而言，还需要满足以下约束条件：1)为便于包装时单个订单多个条目的后续整理，每个订单的所有包装条目需要在1条包装线上完成，不允许拆分；2)任意1条包装线同一时刻只能对1个订单进行包装；3)由于不同客户的条码识别方式不同，当同一条包装线上相邻的2个订单分属不同客户时，中间需要机器调整时间；4)每条包装线的运行速度基本相同。本文将以最小化最大完工时间以及最小化订单总拖期为目标，对短时间内到来的多条包装订单分配相应的包装线，确定每条包装线上订单的包装顺序。

1.3 问题假设与参数定义

从问题实际情况和抽象化数学模型的需求出发，模型的假设条件如下：

1)一个订单在包装进行时不中断，且不允许分割到多条包装线上处理；

2)由于不同客户的条码识别方式有差异，订单按客户的不同划分类别，对于不同类别订单，包装线需要对应类别的机器调整时间，且当前时间段内每条包装线上安排的第1个订单默认需要调整时间；

3)订单上线包装前的准备工作可与机器调整同时进行，在包装1个订单其中1个条目的同时可以进行其他条目的准备工作，从而忽略单个订单之内准备相关的时间；

4)订单分配方案确定后，不考虑紧急订单的插单。

1.4 包装订单分配排序数学模型

基于以上参数，同时考虑包装线机器分配及机器调整时间，本文以最小化最大完工时间、最小化订单总拖期为优化目标，针对包装订单分配排序问题建立数学模型。

1)目标函数:

F1=min(Cmax)

(1)

(2)

其中，式(1)表示第1个优化目标为最小化最大完成时间；式(2)表示第2个优化目标是最小化被安排的所有订单总拖期。

2)数学关系和约束条件。为对订单数据进行简化处理，需要确定1条订单的整体处理时间，订单j的包装处理时间计算式：

pj=ajta+bjtb

(3)

机器调整决策约束：

(4)

(5)

订单安排不重复约束：

(6)

(7)

(8)

(9)

其中：式(8)与式(9)表明2个决策变量均为0～1决策变量。

包装线i上第h位置包装的订单对应的机器调整时间、处理时间和完成时间：

(10)

(11)

C(h)i=C(h-1)i+S(h)i+P(h)i

(12)

C(0)i=0

(13)

完成时间、交货期、延误变量、拖期时间的数学关系：

(14)

C(h)i-d(h)i≤LU(h)i

(15)

T(h)i=U(h)i(C(h)i-d(h)i)

(16)

最大完成时间和总拖期时间：

Cmax=max(C(h)i)

(17)

(18)

2 基于NSGA-Ⅲ算法的模型求解

2.1 NSGA-Ⅲ算法

NSGA-Ⅲ算法是在NSGA-Ⅱ算法基础上改进的多目标优化算法，是基于参考点非支配排序方法的进化多目标优化算法[14]，其强调非主导但接近一组提供的参考点的总体成员，在多目标测试问题上能得出较好的结果。本文中使用的NSGA-Ⅲ算法流程如图1所示。

图1 NSGA-Ⅲ算法流程图Fig.1 NSGA-Ⅲ algorithm flow chart

2.2 个体编码与解码方法

从订单分配排序模型中需要兼顾订单顺序与机器次序的角度出发，本文使用随机正数序列与自然数映射的方法进行个体编码,如图2所示。将顺序排列大小为n的订单序列与同样大小但顺序随机的正数序列{rn}一一对应，此正数序列{rn}即为单一个体的编码。与此编码方法相应的一维排序方面的解码方法，即是对编码的正数序列{rn}按照大小顺序重新排序，则与其相对应的订单序列也将得到对应调整，从而得到一组订单排序序列。为得到伴随包装线分配的订单序列，还需要结合轮盘赌选择法对上述一维排序订单序列进行再处理，方法如下。

图2 个体编码与排序解码Fig.2 Individual encoding and sort decoding

1)记顺序排序后的正数序列为{rrn}，对∀1≤j

(19)

(20)

2)将区间[0,1]按照包装线数量均分为m个区间，每条包装线对应的选择取值li为

(21)

当订单对应的累积概率q(j)∈(li-1,li]时，订单j即被分配到包装线i上，由此可对每个订单进行相应分配，得到可行的分配与排序方案。

2.3 交叉策略

结合上述随机正数序列编码方式的特点考虑，本文采用单点的部分匹配交叉方式(PMX)进行染色体的交叉操作。交叉操作的过程示例如图3所示。图中提供了两父代个体的订单序号(第1行)与其对应的随机数编码序列(第2行)。假设订单数量n=8，两父代染色体在第3个位置起发生交叉。由于编码的随机性，从图中可看出，仅单点交叉即可产生与父代有显著差异的子代个体，另外，由于交叉点位置选取的随机性，交叉点越接近染色体两端，子代个体与父代个体之间的差异就越小，因此在对所有参与交叉的父代个体随机选择交叉位置的情况下，交叉操作将产生与父代接近程度不同的子代。

图3 单点PMX交叉操作示例及交叉效果Fig.3 Example and effects of single-point PMX crossover

2.4 变异策略

本文采取针对个体编码的基因值进行均匀变异的方法，基于变异概率选择一定数量的父代个体变异生成子代个体。变异的操作方法如图4所示。1)随机选择个体编码序列{rn}的1个基因值；2)随机生成位于[rmin-δ,rmax+δ]区间内的1个新实数，以此替换原先的基因值。其中：rmin、rmax分别为染色体编码序列的最小值、最大值，δ为一个小量，此处取δ=0.01(rmax-rmin)，用于保证变异后的基因值有概率在重排后位于重排序列的两端。

图4 变异操作示例Fig.4 Example of mutation

3 实例求解验证

3.1 数据来源与部分模型参数设置

本文收集浙江一个围巾生产企业数据库中部分待包装订单数据，订单种类(客户种类)分为3种(1*、2*、3*)。该企业包装车间目前有2条包装线，各包装线上机器的配置相同，3种类型订单对应的机器调整时间Sg=[0.6 0.5 0.4](单位：h)，包装线上单条围巾的平均装箱时间ta=8 s，包装过程平均换箱时间tb=15 s。选取一定时间内到达的15个包装订单，根据式(3)，利用数据表中的装箱数量与围巾包装数量并结合ta、tb，计算出各订单的包装处理时间。各订单对应类型、数量、交货期、包装处理时间等数据如表1所示。其中部分订单包含装箱数不同的多种装箱类型，此处假设系统在读取单条订单数据时可自动处理多种装箱类型的变化，将改变造成的时间影响限定为一个较小值，保证订单处理时间仍可按照式(3)近似处理。

表1 模型验证算例数据Tab.1 Data of model validation examples

将此15个订单数据按照现阶段企业常用的EDD优先规则进行分配排序，得到的方案、完成时间、拖期情况如表2所示。可看出，EDD优先规则排序能够尽可能满足大部分订单的交期需求，但2号订单有11.393 5 h的较长拖期，14号订单也有3.919 7 h的拖期，较长的拖期将对后续物流发货造成影响，导致客户收货推迟。

表2 EDD优先规则分配排序方案Tab.2 Assignment sorting scheme according to EDD rule

3.2 优化参数设置与结果分析

本文采用MatLab R2016a编译软件编写与执行NSGA-Ⅲ算法程序，NSGA-Ⅲ的各项参数设置如下：种群大小NP=100，交叉概率Pc=0.9，变异概率Pm=0.1，参考点划分数为10，NSGA-Ⅲ的最大迭代次数为150。对上述算例运行1次NSGA-Ⅲ，得到的最大完成时间和总拖期进化情况分别如图5所示。

其中种群最优时间表长度在算法执行初期快速收敛，种群最小总拖期也在50代之前即趋于稳定，为更直观地显示2项目标函数的综合进化情况，此处设定以下函数作为个体的综合适应度函数：

(22)

图6为本次优化运行过程相应的综合适应度进化情况。可看出该算法在前期快速收敛，且直到第80代都有优化解涌现，第80代后种群达到相对最优。

图6 综合适应度迭代图Fig.6 Integrated fitness iteration diagram

经150代进化与选择后，最终输出的最优前沿种群2目标函数值集中于1条线(Pareto前沿)上的多个点，如图7所示。表3示出几种对应的分配排序方案与拖期情况。

图7 优化后种群两目标函数值分布Fig.7 Values distribution of two objective functions of optimized population

表3 优化后结果对应方案Tab.3 Schemes corresponding to optimized results

与按EDD规则分配排序相比，根据本文数学规划模型输出的结果在缩短了最大完工时间的同时有效地控制了拖期，几种优化方案的平均最大完工时间相较于按EDD规则的方案缩短了4.7%，且所有解的拖期均小于4 h。由于模型中所指订单的交货期实质上是订单应当发货的时间，对于延误时间在数小时内的情况可在物流上设法弥补，尽可能保证客户收货时间在客户要求范围内，因此NSGA-Ⅲ求解出的方案均为可行方案，实际选择时可根据物流等条件进行抉择。

4 结束语

本文针对服装企业订单包装出货过程中的包装任务分配与排序问题进行了研究，建立了以最小化最大完成时间和最小化订单总拖期时间为目标、考虑机器分配及调整时间的包装订单分配排序数学模型，并采用基于参考点的快速非支配遗传算法(NSGA-Ⅲ)求解出优化的订单分配排序方案。将该模型与求解方法应用于相关企业具体案例的分配排序方案求解，验证了该方法相较于当前企业常用的EDD规则分配排序法能够给出在最大完成时间和订单拖期情况2个方面都更具优越性的方案。

该模型可通过调整设备数量、设备速度、求解订单数量，用于解决不同包装车间规模的纺织服装生产企业的包装出货订单分配排序问题，而且可通过完善与企业ERP系统、数据库的数据获取过程，取得更准确的计算数据，集成到企业MES系统中，减少企业在排产、库存、物流等方面的管理成本，提高生产效率。

FZXB