衬衫吊挂流水线的自适应动态调度

谢子昂， 杜劲松,2， 赵国华

(1. 东华大学 服装与艺术设计学院， 上海 200051； 2. 东华大学 现代服装设计与技术教育部重点实验室，上海 200051； 3. 报喜鸟控股股份有限公司， 浙江 温州 325102)

由于服装大规模个性化定制模式下的订单到达时间、款式差异、插单返单等因素的影响，造成了生产调度的复杂性，因此企业有必要利用控制系统对生产线进行动态调度，确保生产的稳定性与连续性，提高生产调度的实时响应能力。

针对不确定条件下的车间动态调度问题，国内外学者提出了基于滚动时域的动态调度策略，通过对固定周期和事件驱动的重复调度，使生产线能够不断地根据车间实时情况进行调整[1-2]，并依托滚动调度的调度机制和调度算法研究来提高调度机动性[3-4]、减少重调度频次[5]、提高设备利用率[6]。由于影响服装生产效率的因素众多，如服装款式差异、加工设备差异、订单批量差异[7]、人员技能差异等，使得目前订单调度策略很难满足服装定制生产的需要。

本文针对衬衫定制的吊挂生产系统，利用吊挂流水线无物流浮余时间的特点，提出了适应吊挂生产方式的多目标自适应动态滚动调度模型，解决生产控制环节的不稳定问题。

1 生产动态调度模型

1.1 问题描述

1.1.1 调度问题描述

在服装批量化定制生产过程中，服装生产线调度的目标是将各工序分配至不同的加工工位上，其调度问题可以描述为：有n个订单(J1,J2,…,Jn)在m台设备(M1,M2,…,Mm)上加工，∀Ji由加工顺序已知的工序Oi={Oij,j∈(1,2,…,ni)}组成，订单i的第j道工序可选设备集合为Mij⊆{1,2,…,M},(1≤i≤n,1≤j≤ni)。将所有工序Oij分配在设备Mk生产，其中1≤k≤m，以实现最优生产计划安排目标。

1.1.2 生产不确定性描述

由于实际生产过程中订单到达时间和款式要求不确定，导致了生产计划的实时变更。其中，订单到达时间t、工序内容O是影响生产调度安排的主要因素，因此任意订单i可表示为二维变量(ti，Oi)。在生产排队理论中，任意前后到达的订单间隔服从参数λ的指数分布，其中λ为订单的平均到达率，分布函数如下

F(t)=1-e-λt

(1)

假定第1个订单到达时间t1=0，则第i个订单到达时间ti为

(2)

1.2 动态模型构建

1.2.1 优化目标

本文研究以最后订单完工的最小化时间f1和工位等待最小化时间f2作为优化目标，减少设备的闲置率。

f1=(maxCi|i=1,2,…,n)

(3)

(4)

式中：Ci为订单i的完工时间；Ci(j-1)为订单i的第j-1 道工序完工时间；Tijk为订单i的第j道工序在设备k上的可加工时间。

1.2.2 约束条件

服装订单生产约束条件包括工序加工时间、订单投放时间、工位选择约束、人员技能水平：

(5)

Sijk≥ti,k∈Mij

(6)

(7)

Cijk=max{Ci(j-1)k,Tijk}+Pijkh,k∈Mij

(8)

Cijk≤Si(j+1)k,k∈Mij

(9)

式中：Pijkh为工序的加工时间约束；Pijk为订单i第j道工序在设备k上加工时间；αh为不同技能等级的生产效率，人员技能等级为A、B、C，各等级生产效率比为αA∶αB∶αC=1.2∶1∶0.8；Xijk为订单i第j道工序在设备k上加工的判别条件，当工序选择设备k加工时候，则Xijk为1，反之为0；Sijk、Cijk分别为订单i第j道工序在设备k上的实际开工时间和完工时间。公式(5)表示工序的实际加工时间受人员的生产效率影响，对于相同工序，高效员工的实际加工时间较短；公式(6)表示只有在用户下单后才能对订单投产；公式(7)表示一道工序只能在一台设备上加工一次；公式(8)表示订单的完工时间约束；公式(9) 表示订单的加工顺序约束。

除上述约束条件外，本文研究规定了如下假设：1台机器只能加工1道工序；不同订单的加工顺序没有先后约束等。

2 滚动调度策略

2.1 自适应滚动调度构建

服装个性化订单利用滚动调度可对服装计划排产过程进行多静态区间划分，隔离扰动因素带来的负面影响，实现生产流水线畅通。滚动调度包括待加工工序集合Sa、正在加工工序集合Sw、已完工工序集合Sc等，并驱动窗口内各集合实时更新生产数据。窗口外未加工订单集合Su记录了动态到达的订单信息，设备集合Sm记录了所有设备的可用时间、工作状态等。执行滚动调度的过程包括：1)在初始时刻从Su中取出未加工订单，并拆分成工序放入Sa；2)经过Sm查询各设备加工状态，调用算法为Sa中的工序分配设备，若出现扰动事件则重复步骤1)；3)当到达重调度周期时，则清空Sc，重复步骤1)、2)。

由于不同订单工艺要求不同，导致设备因换线产生调整时间，为了减少设备频繁换线、设备待机过长现象，滚动调度窗口增加单次调度的订单数量，提升调度性能[8]。当任意设备完工并能投入下周期生产时，生成自适应滚动调度窗口，此时待调度工序集合Sa包括了周期内积累的未加工订单集Su所拆分出的工序和上一周期内未加工工序集合。滚动调度窗口在保证设备连续生产的同时，自动调整调度窗口大小，避免设备闲置对尽可能多的订单进行调度。自适应动态调度流程如图1所示。

图1 滚动调度流程Fig.1 Rolling Scheduling flow chart

其中Tq为第q周期工件窗口Wq的生成时间；生产中，数据采集窗口持续采集订单i的到达时间ti和对应的工序集合Oi；若ti1时)周期的未完工工序合与Owq合并生成待调度工序集合Sa，并依据设备集合Sm生成调度方案。当调度方案执行后若有设备加工完该周期的所有工序，并能立刻开始下一周期生产时，则生成下一周期的工件窗口进行调度。

2.2 非支配遗传算法

调度过程中需要同时优化多个不可比较的目标函数，导致传统目标线性加权的方法求解质量不高，目前常基于pareto支配关系对多目标问题进行求解，该方法能够兼顾多个目标之间的均衡[9]，本文研究在遗传算法基础上采用pareto选择机制对滚动窗口内的订单工序进行调度。

2.2.1 编码解码

染色体采用工序链/机器链的二层编码结构，每层染色体的长度实时调整，即为本次调度的工序数量。第1层为工序编码，染色体中的基因代表对应订单在该滚动调度窗口内的编号，数字出现的次数代表对应工序序号。第2层为对应工序所选择的设备，工序必须满足可选设备约束。

2.2.2 交叉变异

在染色体交叉过程中，工序链需要满足订单工序数量的约束，即子代C相同基因的数量与父代P相同，因此为满足交叉的合法性，本文采用基于工件的POX(precedence operation crossover)交叉方法，交叉过程如图2所示。

图2 POX交叉示意图Fig.2 Diagram of POX

首先随机选择2个非空子集J1、J2，存储工件编号，将P1中对应J1的工件序列复制到C1中，剩余位置的染色体由P2中对应J2的工件填充得到完整的C1；C2则与C1相反，由P2中对应J1的工件序列复制到C2中，剩余位置的染色体由P1中对应J2的工件填充得到完整的C1。

机器链必须满足工序的可选设备约束，采用MPX(multi-point preservative crossover)的多点交叉方法，如图3所示。

图3 MPX交叉示意图Fig.3 Diagram of MPX

首先随机生成1条与机器链等长的0、1序列Rand，然后将P1、P2中在Rand=1的位置交换基因得到C1、C2。工序链采用2点变异的方式，在染色体上随机选择连续的2道工序，对应基因进行交换完成变异；机器链通过随机选择1道工序，并选择其中1个可加工该工序的设备作为替换完成变异操作。

2.2.3 选择操作

Pareto支配关系的选择机制是解决多目标优化问题的常用方法，对于n(n>1)个目标的F=(fk|k=1，…，n)，任意染色体i、j，若对∀k有fk(i)≤fk(j)，且∃fk(i)

3 实例仿真

3.1 参数设置

衬衫吊挂生产线人数为13人，1人1工位，每个工位上安置1台或2台设备。根据衬衫各工艺加工的时间比设置设备16台，其中平缝机、烫台、五线车、链式机、锁眼机、钉扣机的配置比例为7∶4∶2∶1∶1∶1。设定订单的平均到达率设定为90 s，产前到达订单数量为60个。

衬衫可定制的款式为8种，衬衫款式的配置设计部件包括2种领型、2种贴袋型、2种克夫。各款式的加工时间如表1所示。

表1 不同款式加工时间Tab.1 Procedure process time of different styles

图4示出吊挂生产流水线示意图，图中w1～w13代表工位编号，工位内的人员等级(A、B、C3个等级)和设备配置均有显示。A级人员完成复杂的缝制工序；B级人员完成较复杂的缝制工序；C级人员只能完成简单工序，如小烫等。

图4 服装吊挂产线布局Fig.4 Hanging production line layout

为提高求解的效率，尽量保证种群规模与最大迭代数的最大化，设定种群规模N=100，最大迭代数为500代，交叉率Pc=0.8，变异率Pm=0.02，交叉率Pc∈ (0.4，0.9)，变异率Pm∈(0.005，0.1)[10]。

3.2 仿真结果分析

仿真实验分为固定周期调度和自适应滚动调度2种方案。固定调度周期设置一般根据企业生产条件而定，通常固定调度周期越小，设备闲置时间就越少，但生产线的快速反应效率会下降，而固定调度周期越大，会提升生产线的在制品率和调度的复杂性。自适应滚动调度是通过寻找生产前端工序设备的闲置时刻，自行判断调度周期窗口，实现生产线的自适应性。

生产前已到达订单数量为60件，根据上文的约束条件公式(1)～(9)进行计划排产仿真。如图5所示，图中1#～8#分别代表款式1#-8#的款式编号，粗实线为生产前端工序出现闲置设备的时刻4 558 s，即为自适应滚动调度窗口位置。本实验设定固定调度周期分别为3 600、7 200 s，如图中虚线所示。固定调度周期为3 600 s的第1次滚动调度结果如图6所示。自适应滚动调度的第1个周期如图7所示。图6、图7的款式编号与图5一致。

图5 调度前计划排产方案Fig.5 Advanced scheduling sequence

图6 T=3 600 s的第1次滚动调度Fig.6 First rescheduling cycle under rolling scheduling of T=3 600 s

图7 自适应第1次滚动调度Fig.7 The first rescheduling cycle of adaptive rolling schedule

实验结果表明，完成288件衬衫所需要的生产时间和设备利用率分别为：固定调度周期(T=3 600 s)

为26124和63%；固定调度周期(T=7 200 s) 为32 104 s和57.8%；自适应调度为24 894 s 和67%。

4 结束语

基于多目标动态调度算法的自适应滚动窗口能够解决现有服装大规模定制生产的自主适应性能差的问题。针对实时性的订单导入，自适应滚动调度窗口机制利用现有生产条件进行实时生产排程，最大限度地提高设备的使用率，实现生产线的效率提升。实验表明自适应滚动调度相对固定周期调度(T=3 600 s)的完工时间减少4.9%，设备等待时间减少18.2%。