-
文中研究的是离散生产车间虚拟制造单元继承性重构调度问题,其应用背景是传统的柔性作业车间。与传统柔性作业车间调度问题相同点为:(1)均涉及n种订单
${J}_{i}(i={1,2,}\cdots,n)$ 、m台设备;(2)每一种工件$ {J}_{i} $ 的加工均需要经过一系列具有严格顺序的工序,$ {O}_{ij} $ 表示订单$ {J}_{i} $ 的第j道工序;(3)每一道工序都可以由一台或者多台设备进行加工,因此每一个订单$ {J}_{i} $ 都有多个可选工艺路线。与传统柔性作业车间调度问题不同的是,每个订单均有一定的批量
${N}_{i}(i=\mathrm{1,2,}\cdots,n)$ ,还要考虑原虚拟制造单元的构成。从订单的角度看,文中研究的问题需要为每一个订单安排加工设备,实现关重/紧急订单在虚拟制造单元中的流水式生产;从运行时间的角度看,该问题涉及的虚拟制造单元的构成随着订单结构的变化而持续性变化。因此文中研究的虚拟制造单元继承性重构调度问题涉及3个子问题:分配、排序和单元重构,从而达到订单的最大完工时间($ {C}_{max} $ )最小,并且重构前后虚拟制造单元构成差异性最小化。为了更好地解决问题,文中提出一些假设:(1)所有的设备均在0时刻可用;
(2)所有的工件都可以在0时刻开始被加工;
(3)同一工序在不同设备上加工所需的处理时间相同;
(4)属于不同工件的工序之间没有顺序约束;
(5)一台设备在同一时刻只能加工一道工序;
(6)任意一道工序在加工时不能被打断,直到该工序加工结束;
(7)不考虑设备故障的情况;
(8)不考虑工序周转需要的时间;
(9)所有设备的加工日制一致。
-
文中涉及的虚拟制造单元继承性重构调度的数学模型所用的相关符号定义和说明如下:
$ {J}_{i} $ :订单$ i $ ,$i=\mathrm{1,2,}\cdots, n$ ;$ {N}_{i} $ :订单$ i $ 的数量;$ {O}_{ij} $ :订单$ i $ 的第$ j $ 道工序,$j=\mathrm{1,2},\cdots, {R}_{i}$ ;$ {T}_{ij} $ :订单$ i $ 的第$ j $ 道工序的单件工时;$ {ST}_{ij} $ :订单$ i $ 的第$ j $ 道工序的实际开始时间;$ {ET}_{ij} $ :订单$ i $ 的第$ j $ 道工序的实际开始时间;$ K $ :设备类型的数量,$k=\mathrm{1,2,}\cdots, K$ ;$ {M}_{l} $ :设备$ l $ ,$l=\mathrm{1,2}\cdots, m$ ;$ {count}_{l-l\text{'}} $ :设备$ l $ 和设备${l}'$ 之间的距离;$ L $ :一个足够大的常数;${IK}_{lk}=\left\{\begin{array}{l} 1,\;设备{\rm{l}}属于类型{{k}}\\ 0,\;否则\end{array}\right.$ ;$ OC $ :重构前的原制造单元数量;$ {OC}_{a} $ :第$ a $ 个原制造单元,$a=\mathrm{1,2},\cdots, OC$ ;$ {AM}_{{OC}_{a}} $ :第$ a $ 个原制造单元中包含设备的数量,$a=\mathrm{1,2},\cdots, OC$ ;${IOC}_{la}=\left\{\begin{array}{l}1,\;设备{\rm{l}}属于单元{OC}_{a}\\ 0,\;否则\end{array}\right.$ ;${IOC}_{ka}=\left\{\begin{array}{l}1, \;设备类型{{k}}属于单元{OC}_{a}\\ 0,\; 否则\end{array}\right.$ ;$ {OC}' $ :重构后的制造单元数量;${IOC}'_{la}=\left\{\begin{array}{l}1,\;设备{\rm{l}}属于单元{OC}'_{a}\\ 0,\;否则\end{array}\right.$ ;$ {PJ}_{{OC}_{a}} $ :制造单元$ {OC}_{a} $ 中的零件族;$ {PM}_{{OC}_{a}} $ :制造单元$ {OC}_{a} $ 中包含的设备组;$ {PMK}_{{OC}_{a}} $ :制造单元$ {OC}_{a} $ 中包含的设备组种类;$ {W}_{iq} $ :订单$ i $ 的可选加工路径,$q=\mathrm{1,2},\cdots, WO$ ;$ {S}_{{W}_{iq}{OC}_{a}} $ :订单$ i $ 的选择加工路径是$ {W}_{iq} $ 时与原制造单元$ {OC}_{a} $ 的相似度值;$ {S}_{{W}_{iq}{PJ}_{{OC}_{a}}} $ :订单$ i $ 的选择加工路径是$ {W}_{iq} $ 时与原制造单元$ {OC}_{a} $ 中的零件族$ {PJ}_{{OC}_{a}} $ 相似度值;$ {S}_{{W}_{iq}{PM}_{{OC}_{a}}} $ :订单$ i $ 的选择加工路径是$ {W}_{iq} $ 时与原制造单元$ {OC}_{a} $ 中的设备组$ {PM}_{{OC}_{a}} $ 相似度值;$ {AQ}_{{W}_{iq}{PJ}_{{OC}_{a}}} $ :订单$ i $ 的选择加工路径是$ {W}_{iq} $ 时在原制造单元$ {OC}_{a} $ 中的零件族$ {PJ}_{{OC}_{a}} $ 中的加工工序总数量;$ {AQ}_{{PJ}_{{OC}_{a}}} $ :原制造单元$ {OC}_{a} $ 中的零件族$ {PJ}_{{OC}_{a}} $ 中的加工工序总数量;$ {TQ}_{{W}_{iq}{PJ}_{{OC}_{a}}} $ :订单$ i $ 的选择加工路径是$ {W}_{iq} $ 时在原制造单元$ {OC}_{a} $ 中的零件族$ {PJ}_{{OC}_{a}} $ 中的加工工序总工时;$ {TQ}_{{PJ}_{{OC}_{a}}} $ :原制造单元$ {OC}_{a} $ 中的零件族$ {PJ}_{{OC}_{a}} $ 中的加工工序总工时;$ {X}_{ijl}=\left\{\begin{array}{l}1,\;如果设备{\rm{l}}是工序{O}_{ij}的可选加工设备\\ 0,\;否则\end{array}\right. $ ;${Y}_{ijl}=\left\{\begin{array}{l}1,\;工序{O}_{ij}在设备{\rm{l}}上加工\\ 0,\;否则\end{array}\right. $ ;${B}_{ijl-i'j'l}= \left\{\begin{array}{l}1,\;如果工序{O}_{ij}紧接着工序{O}_{i'j'}在设备{\rm{l}}上加工\\ 0,\;否则\end{array}\right.$ ;${U}_{ij-(j+1)}=\left\{\begin{array}{l}1,\;工序{{O}}_{{i}{j}}和工序{{O}}_{{i}({j}+1)}之间流水生产\\ 0,\;否则\end{array}\right.$ ;$ {C}_{max} $ :所有工序的最大完工时间;$ \stackrel{-}{\delta } $ :重构前后制造单元间的平均差异度;$ \;{\beta }_{a} $ :重构后制造单元与对应原制造单元的差异度;$ \varepsilon $ :常数,订单和原有制造单元对应零件族间相似度权重系数;$ \tau $ :常数,订单和原有制造单元包含的设备集合间相似度权重系数。$$ min:{C}_{max} $$ (1) $$ min:\;\overline{\delta } $$ (2) 公式(1)和公式(2)表示问题的两个调度目标,即最小化所有工序的最大完工时间,最小化重构前后制造单元间的平均差异度。
$$ {C}_{max}=\mathit{max}\left({ET}_{ij}\right),\forall i,j $$ (3) $$ {ET}_{ij}={S T}_{ij}+{T}_{ij}\times {N}_{i},\forall i,j $$ (4) 公式(3)和公式(4)描述了工序最大完工时间的具体计算方法,其中公式(4)描述了工序的开始时间、结束时间、单件工时和订单数量之间的关系。
$$ \stackrel-{\delta }=\frac{{OC}'}{OC}\times \frac{\displaystyle\sum \nolimits_{a}^{{OC}'}{\beta }_{a}}{{OC}'},\forall a $$ (5) $$ \begin{split} {\beta }_{a}=& \frac{{AQ}_{{PJ}_{{OC}'_{a}}}}{{AQ}_{{PJ}_{{OC}_{a}}}}\times \frac{{TQ}_{{W}_{iq}{PJ}_{{OC}'_{a}}}}{{TQ}_{{W}_{iq}{PJ}_{{OC}_{a}}}}\times \frac{\displaystyle \sum _{l=1}^{m}{M}_{l}\times {IOC}'_{a}}{\displaystyle \sum _{l=1}^{m}{M}_{l}\times {IOC}_{a}}\times \\ & \frac{\displaystyle \sum _{k=1}^{K}\displaystyle \sum _{l=1}^{m}{M}_{l}\times {IOC}'_{a}\times {IOC}'_{ka}\times {IK}_{lk}}{\displaystyle \sum _{k=1}^{K}\displaystyle \sum _{l=1}^{m}{M}_{l}\times {IOC}_{a}\times {IOC}_{ka}\times {IK}_{lk}} \end{split} $$ (6) 公式(5)和公式(6)描述了重构前后制造单元间的平均差异度的具体计算方法,其中公式(5)表示两个方面:(1)重构后存在的制造单元总数量与重构前存在制造单元总数量的差异;(2)重构后的各个制造单元与原制造单元的间的差异。公式(6)描述了公式(5)的重构后的各个制造单元与原制造单元的间的差异度的计算方法,主要包括4个方面:(1)重构后对比重构前的制造单元对应零件族的总加工工序数量的差异度;(2)重构后对比重构前的制造单元对应零件族的加工工序总加工工时的差异度;(3)重构后对比重构前的制造单元所包含设备数量的差异度;(4)重构后对比重构前的制造单元所包含设备种类的差异度。
$$ \sum\nolimits _{l=1}^{m}{X}_{ijl} > 0,\;\forall i,j $$ (7) $$ {X}_{ijl}-{Y}_{ijl}\geqslant 0,\;\forall i,j $$ (8) $$ \sum \nolimits _{l=1}^{m}{Y}_{ijl}=1,\;\forall i $$ (9) $$ {S T}_{i(j+1)}\geqslant {ET}_{ij},{U}_{ij-(j+1)}=0,\;\forall i,j $$ (10) $$ {S T}_{i(j+1)}\geqslant {S T}_{{i}'{j}'}+{T}_{{i}'{j}'},{U}_{ij-(j+1)}=1,\;\forall i,j $$ (11) $$ {ET}_{i(j+1)}\geqslant {ET}_{ij}+{T}_{i(j+1)},{U}_{ij-(j+1)}=1,\; \forall i,j $$ (12) $$ {S T}_{ij}+\left(1-{B}_{ijl-{i}'{j}'l}\right)\times L\geqslant {S T}_{{i}'{j}'}+{T}_{i'j'}\times {N}_{i'} $$ (13) 公式(7)~(9)为排产设备约束。公式(7)表示任意一道工序都必须至少有一台可选设备,公式(8)表示工序必须在其可选设备上选择一个安排,公式(9)表示任意一个工序的加工设备仅有一台,且属于其可选设备集合,公式(10)表示工序间离散生产时,后一道工序必须在前一道工序全部结束之后才能开始,公式(11)和公式(12)表示工序间流水生产时,后一道工序的开始时间和结束时间应同时满足的约束,公式(13)保证了每一台设备在同一时刻最多只能加工一道工序。
-
从排产结果的角度看,虚拟制造单元可以在排产结束后自然形成。在一定的调度规则下,只要改变工序的安排顺序,虚拟制造单元就会随着任务的变化发生改变。文中从原制造单元以及新订单信息为输入依据,判断新订单和原制造单元的零件族、原制造单元的设备能力间的相似度,并根据新订单集合的相似度进行聚类分析,通过对原有制造单元进行继承性重构,最终得到随着新订单任务结构变化而变化的新制造单元的构型。文中设计了一种针对持续性变化的订单需求的柔性离散车间虚拟制造单元调度问题处理机制,该机制以改进的遗传算法为核心,基于继承性重构的解码策略,实现虚拟制造单元构型随着订单结构变化的持续重构以及订单任务的持续调度。
文中所提的基于继承性重构的改进遗传算法流程如图2所示,其步骤如下:
步骤1:对输入的订单信息和原制造单元的信息进行相似性分析;
步骤2:根据计算的得到的相似度进行排序,并组装成订单的相似单元链;
步骤3:初始化算法的种群个体;
步骤4:基于继承性重构解码规则进行解码,并计算个体的适应度值;
步骤5:判断是否满足算法终止条件,若是,则转到步骤8,否则转到步骤6;
步骤6:对种群进行交叉、变异操作;
步骤7:对种群进行选择操作,转到步骤4;
步骤8:输出种群的排产方案和制造单元重构方案。
-
文中采用基于工序的编码方式生成染色体个体,染色体的每一个基因表示对应的订单的编号,相同的基因表示属于同一个订单的不同的工序,按照顺序依次生成。
图3所示为一个具有3个订单的染色体编码示意图,其表示所有工序的安排顺序为
$ {O}_{11}\to {O}_{21}\to {O}_{12}\to {O}_{31}\to {O}_{32}\to {O}_{33}\to {O}_{22}\to {O}_{23}\to {O}_{13}\to {O}_{24} $ 。 -
在单元的构建过程中常常需要将订单相似性聚类为一个零件族,并对其合理分配设备资源,实现制造单元的构建。这种将订单相似性聚类,对具有相似性的订单零件族在单元内加工生产可减少生产准备时间,增加工人的技术熟练程度,从而提高车间的生产效率,有效保证生产质量的一致性。在已有制造单元构型的时候,面对新订单结构的差异,原有制造单元的组织构型可能不再适应新订单的生产,必须对其进行调整重构来满足新产品的高效生产。所以在针对既有制造单元构型的制造单元重构调度问题研究中,需要对新订单和原有制造单元对应的零件族、包含的设备组进行相似性分析,通过量化相似性以判断原有制造单元对新订单的适用程度,对适用度低的制造单元进行继承性重构,以达到对制造单元的低成本的持续性重构。现有的一些相似系数的计算都是应用在制造单元的构建时期,已经不能满足已知制造单元构型、对其进行重构的问题。因此,文中在参考文献[18]基础上进行改进,并参考文献[19]进行优化,形成一种针对已经存在的制造单元和新订单的相似性系数计算方法,这种新的相似性系数主要是针对新订单和原有制造单元适用的订单产品族、原有制造单元包含的设备集合进行的相似性分析,从而量化新订单与已存在的各个制造单元集合之间的相似关系。其对应的表达式如公式(14)~(16)所示:
$$ {S}_{{W}_{iq}{OC}_{a}}=\varepsilon \times {S}_{{W}_{iq}{PJ}_{{OC}_{a}}}+\tau \times {S}_{{W}_{iq}{PM}_{{OC}_{a}}},\forall a,i $$ (14) $$ {S}_{{W}_{iq}{PJ}_{{OC}_{a}}}=\frac{{AQ}_{{W}_{iq}{PJ}_{{OC}_{a}}}}{{AQ}_{{PJ}_{{OC}_{a}}}}\times \frac{{TQ}_{{W}_{iq}{PJ}_{{OC}_{a}}}}{{TQ}_{{PJ}_{{OC}_{a}}}},\forall a,i $$ (15) $$ \begin{split} {S}_{{W}_{iq}{PM}_{{OC}_{a}}}= & \frac{\displaystyle\sum _{j=1}^{{R}_{i}}\displaystyle\sum _{l=1}^{m}{X}_{ijl}\times {IOC}_{la}}{{PM}_{{OC}_{a}}}\times \\ & \frac{\displaystyle\sum _{j=1}^{{R}_{i}}\displaystyle\sum _{k=1}^{K}\displaystyle\sum _{l=1}^{m}{X}_{ijl}\times {IOC}_{ka}\times {IK}_{lk}}{{PMK}_{{OC}_{a}}},\forall a,i \end{split}$$ (16) 公式(14)表示订单
$ {J}_{i} $ 和原制造单元$ {OC}_{a} $ 的相似度值的计算方法,其主要包括两部分:(1)订单$ {J}_{i} $ 和原制造单元$ {OC}_{a} $ 对应的零件族之间的相似度$ {S}_{{W}_{iq}{PJ}_{{OC}_{a}}} $ ;(2)订单$ {J}_{i} $ 和原制造单元$ {OC}_{a} $ 包含的设备集合之间的相似度$ {S}_{{W}_{iq}{PM}_{{OC}_{a}}} $ 。通过公式可看出,相似度值越大,相似关系越强。其中公式(15)描述了
$ {S}_{{W}_{iq}{PJ}_{{OC}_{a}}} $ 的具体计算方法,其包含了:(1)订单$ {J}_{i} $ 可在制造单元$ {OC}_{a} $ 中加工的工序数量和制造单元$ {OC}_{a} $ 对应零件族在单元中的平均加工工序数量比值;(2)订单$ {J}_{i} $ 可在制造单元$ {OC}_{a} $ 中加工的工序总时长和制造单元$ {OC}_{a} $ 对应零件族在单元中的平均加工工序总时长比值;公式(16)描述了
$ {S}_{{W}_{iq}{PM}_{{OC}_{a}}} $ 的具体计算方法,其包含了:(1)订单$ {J}_{i} $ 可选设备且属于制造单元$ {OC}_{a} $ 的数量和制造单元$ {OC}_{a} $ 包含的设备数量比值;(2)订单$ {J}_{i} $ 可选设备种类且属于制造单元$ {OC}_{a} $ 的数量和制造单元$ {OC}_{a} $ 包含的设备种类比值;通过对订单和制造单元间相似分析并量化为相似度值,可将其递减排序,并与订单绑定、组装为订单-原制造单元相似链,方便后续的计算。
-
基于继承性重构解码策略保证在对工序进行设备选择时优先选择相似程度高、最早开工的制造单元中的可选设备,对制造单元进行最大程度的继承的同时,减少了订单延期的风险。基于继承性重构解码策略如图4所示。
基于继承性重构解码策略的具体步骤如下:
步骤1:根据种群个体的基于工序的编码获得待排产工序集合R;
步骤2:令i=0;
步骤3:判断i是否大于待排产工序集合的上限,若是,则转到步骤12,否则,转到步骤4;
步骤4:找到
$ {R}_{i} $ 对应的订单$ {O}_{j} $ 及其对应的制造单元相似链集合C;步骤5:令h=0;
步骤6:判断h是否超过相似链集合C的上限,若是,则令i=i+1,转到步骤3,否则转到步骤7;
步骤7:判断
$ {C}_{h} $ 中是否包含工序$ {R}_{i} $ 的可选设备,若是则转到步骤8,否则,令h=h+1,转到步骤6;步骤8:计算选择该设备时工序
$ {R}_{i} $ 的最早开始时间t,并更新$ {ET}_{i}=\mathrm{m}\mathrm{a}\mathrm{x}(t,{ET}_{i}) $ ;步骤9:判断工序
$ {R}_{i} $ 的最早开始时间是否未被更新,若是,则转到步骤10,否则,转到步骤11;步骤10:在工序
$ {R}_{i} $ 的可选设备中选择具有最早开始时间的设备,令i=i+1,转到步骤3;步骤11:选择与工序
$ {R}_{i} $ 相似度高、包含可选设备的制造单元中的设备,令i=i+1,转到步骤3;步骤12:输出排产结果并退出流程。
-
文中研究的虚拟制造单元继承性重构调度问题具有两个目标函数:最小化工件的最大完工时间和最小化重构前后虚拟制造单元构成之间的差异。由于解码操作中已经对重构前后虚拟制造单元构成的差异进行了控制,此处仅以
$ {C}_{max} $ 的值作为个体的适应度值。 -
文中的交叉算子采用传统的POX交叉产生可行子代,图5所示为POX交叉算子示意图。
文中的变异算子通过随机交换染色体中的两个基因来实现个体的变异,图6所示为变异操作示意图。
-
文中结合某企业光电观测产品的机加零件生产车间,对文中所提的虚拟制造单元继承性重构调度问题的算法与策略进行了验证。该光电观测产品零件生产具有较高的加工精度,为了保证加工效率同时兼顾加工柔性,采用针对部分零件进行逻辑制造单元的构建,并随任务的结束与解散,同时支持新订单组合模式下制造单元的继承性演变,提高系统的动态优化配置能力。下面以该车间规模为
$ 12\times 8\times 4 $ 的一组数据为例说明文中所提模型的建立和算法的求解过程。该车间共有8种类型的共12台加工设备,各个设备种类与加工设备之间的映射关系如表1所示。
表 1 各设备种类与加工设备映射关系
Table 1. Mapping relationship between each equipment type and processing equipment
Type $ {K}_{1} $ $ {K}_{2} $ $ {K}_{3} $ $ {K}_{4} $ $ {K}_{5} $ $ {K}_{6} $ $ {K}_{7} $ $ {K}_{8} $ Number $ {M}_{2},\; {M}_{7}$ $ {M}_{5} $ $ {M}_{8} $ $ {M}_{4} ,\;{M}_{6}$ $ {M}_{11} $ $ {M}_{9},\;{M}_{12} $ $ {M}_{1} ,\;{M}_{10}$ $ {M}_{3} $ 统计了车间原有的制造单元的信息与各个设备之间距离信息,如表2、表3所示。原有制造单元对应的零件族的基本信息如表4所示。文中所涉及的需要排产的新订单的基本信息如表5所示。
表 2 各个设备之间的距离
Table 2. Distance of each equipment
Equipment number $ {M}_{1} $ $ {M}_{2} $ $ {M}_{3} $ $ {M}_{4} $ $ {M}_{5} $ $ {M}_{6} $ $ {M}_{7} $ $ {M}_{8} $ $ {M}_{9} $ $ {M}_{10} $ $ {M}_{11} $ $ {M}_{12} $ $ {M}_{1} $ 0 - - - - - - - - - - - $ {M}_{2} $ 3 0 - - - - - - - - - - $ {M}_{3} $ 10 8 0 - - - - - - - - - $ {M}_{4} $ 12 11 2 0 - - - - - - - - $ {M}_{5} $ 10 13 4 3 0 - - - - - - - $ {M}_{6} $ 8 9 13 15 15 0 - - - - - - $ {M}_{7} $ 10 12 9 12 9 3 0 - - - - - $ {M}_{8} $ 8 7 12 14 11 4 2 0 - - - - $ {M}_{9} $ 19 16 23 26 25 17 14 12 0 - - - $ {M}_{10} $ 17 15 19 16 17 9 11 14 23 0 - - $ {M}_{11} $ 5 8 10 12 13 8 7 10 15 17 0 - $ {M}_{12} $ 18 20 13 14 16 6 7 9 19 26 5 0 表 3 原有制造单元信息
Table 3. Original manufacturing unit information
Manufacturing
cellCell 1 Cell 2 Part family $ {J}_{1} $,$ {J}_{5} $ $ {J}_{2} $,$ {J}_{3} $,$ {J}_{4} $,$ {J}_{6} $ Machine $ {M}_{2} $,$ {M}_{3} $,$ {M}_{7} $,$ {M}_{10} $,$ {M}_{11} $ $ {M}_{4} $,$ {M}_{6} $,$ {M}_{9} $,$ {M}_{12} $ 表 4 原制造单元对应的零件族的基本信息
Table 4. Basic information of the part family corresponding to the original manufacturing unit
Order Count Process Can use machine Time $ {J}_{1} $ 39 $ {O}_{11} $ $ {M}_{1} $/$ {M}_{2} $ 152 $ {O}_{12} $ $ {M}_{3} $/$ {M}_{4} $/$ {M}_{5} $ 222 $ {O}_{13} $ $ {M}_{6} $/$ {M}_{7} $/$ {M}_{8} $ 277 $ {O}_{14} $ $ {M}_{10} $ 207 $ {O}_{15} $ $ {M}_{11} $ 126 $ {J}_{2} $ 54 $ {O}_{21} $ $ {M}_{3} $/$ {M}_{4} $/$ {M}_{5} $ 150 $ {O}_{22} $ $ {M}_{6} $/$ {M}_{7} $/$ {M}_{8} $ 223 $ {O}_{23} $ $ {M}_{9} $ 171 $ {J}_{3} $ 45 $ {O}_{31} $ $ {M}_{3} $/$ {M}_{4} $/$ {M}_{5} $ 190 $ {O}_{32} $ $ {M}_{6} $/$ {M}_{7} $/$ {M}_{8} $ 260 $ {O}_{33} $ $ {M}_{9} $ 168 $ {O}_{34} $ $ {M}_{12} $ 216 $ {J}_{4} $ 138 $ {O}_{41} $ $ {M}_{3} $/$ {M}_{4} $/$ {M}_{5} $ 100 $ {O}_{42} $ $ {M}_{6} $/$ {M}_{7} $/$ {M}_{8} $ 130 $ {O}_{43} $ $ {M}_{9} $ 150 $ {J}_{5} $ 75 $ {O}_{51} $ $ {M}_{1} $/$ {M}_{2} $ 260 $ {O}_{52} $ $ {M}_{3} $/$ {M}_{4} $/$ {M}_{5} $ 340 $ {O}_{53} $ $ {M}_{6} $/$ {M}_{7} $/$ {M}_{8} $ 204 $ {J}_{6} $ 36 $ {O}_{61} $ $ {M}_{3} $/$ {M}_{4} $/$ {M}_{5} $ 279 $ {O}_{62} $ $ {M}_{6} $/$ {M}_{7} $/$ {M}_{8} $ 126 $ {O}_{63} $ $ {M}_{12} $ 457 $ {O}_{64} $ $ {M}_{9} $ 105 $ {O}_{65} $ $ {M}_{11} $ 568 表 5 新增订单的基本信息
Table 5. Basic information of new order
Order Count Process Can use machine Time $ {J}_{7} $ 45 $ {O}_{71} $ $ {M}_{1} $/$ {M}_{2} $ 176 $ {O}_{72} $ $ {M}_{3} $/$ {M}_{4} $/$ {M}_{5} $ 470 $ {O}_{73} $ $ {M}_{6} $/$ {M}_{7} $/$ {M}_{8} $ 300 $ {O}_{74} $ $ {M}_{11} $ 324 $ {J}_{8} $ 32 $ {O}_{81} $ $ {M}_{1} $/$ {M}_{2} $ 386 $ {O}_{82} $ $ {M}_{3} $/$ {M}_{4} $/$ {M}_{5} $ 160 $ {O}_{83} $ $ {M}_{6} $/$ {M}_{7} $/$ {M}_{8} $ 145 $ {O}_{84} $ $ {M}_{10} $ 78 $ {O}_{85} $ $ {M}_{11} $ 237 $ {J}_{9} $ 98 $ {O}_{91} $ $ {M}_{3} $/$ {M}_{4} $/$ {M}_{5} $ 90 $ {O}_{92} $ $ {M}_{6} $/$ {M}_{7} $/$ {M}_{8} $ 190 $ {O}_{93} $ $ {M}_{9} $ 93 $ {O}_{94} $ $ {M}_{12} $ 264 -
所用算法使用C#进行编程,在64位windows操作系统、 Intel(R) Core(TM) i5-7600处理器、16 GB运行内存的环境中运行。算法参数设置为:初始种群规模为100,最大迭代次数为100,取
$ \varepsilon $ =0.57,$ \tau =0.43 $ 。 -
由表6可看出订单
$ {J}_{7} $ 的制造单元相似链为单元1→单元2,订单$ {J}_{8} $ 的制造单元相似链为单元1→单元2;订单$ {J}_{9} $ 的制造单元相似链为单元2→单元1。在执行基于继承性重构解码策略时,针对每一个订单的任意一个工序的安排设备时,优先考虑相似性大的单元。表 6 订单与原制造单元的相似性分析
Table 6. Similarity analysis between order and original manufacturing unit
Original manufacturing cell Orders $ {J}_{7} $ $ {J}_{8} $ $ {J}_{9} $ Cell 1 0.49 0.31 0.13 Cell 2 0.22 0.04 0.89 -
将新增订单
$ {J}_{7} $ ,$ {J}_{8} $ ,$ {J}_{9} $ 的基本信息、原制造单元的基本信息及其对应的零件族的基本信息等信息作为算法的输入,使用文中所提算法进行求解,最终得到的排产结果甘特图如图7所示,对应的重构后的制造单元结果如表7所示,其继承关系如图8所示。算法运行的收敛图如图9所示。表 7 制造单元继承性重构对比
Table 7. Comparison of manufacturing cell inheritance reconstruction
Manufacturing cell Content Cell 1 Cell 2 Cell 3 Original manufacturing cell Part family $ {J}_{1} $,$ {J}_{5} $ $ {J}_{2} $,$ {J}_{3} $,$ {J}_{4} $,$ {J}_{6} $ - Devices $ {M}_{2} $,$ {M}_{3} $,$ {M}_{7} $,
$ {M}_{10} $,$ {M}_{11} $$ {M}_{4} $,$ {M}_{6} $,$ {M}_{9} $,$ {M}_{12} $ - Reconfigurable cell Part family $ {J}_{5} $ $ {J}_{2} $,$ {J}_{3} $,$ {J}_{4} $, $ {J}_{1} $,$ {J}_{7} $, $ {J}_{9} $ Devices $ {M}_{2} $,$ {M}_{3} $,
$ {M}_{7} $,$ {M}_{10} $$ {M}_{4} $,$ {M}_{6} $,$ {M}_{9} $ $ {M}_{1} $,$ {M}_{5} $ 通过对比原制造单元和重构后制造单元,可以看出制造单元的构成形态具有较大的相似性,重构后的单元1和单元2对原制造单元具有完全的继承性,只是在具体设备方面具有一定的调整,这样不仅实现对原制造单元构成的继承,同时也继承了原制造单元所具有的协同团队生产的经验,对于支持精密光电观测产品零件的精密生产的精度一致性保证以及单元化生产效率的提升具有重要的促进作用。
Research on inheritance reconfiguration scheduling of virtual manufacturing cell based on improved genetic algorithm
-
摘要: 针对多品种变批量生产下效率与柔性兼顾的需求以及既有制造单元难以支持碎片化订单下的关键零件高质量一致性和高效率生产的问题,建立了以最小化
$ {C}_{max} $ 和最小化重构前后的虚拟制造单元构成差异性为目标的数学模型,提出了一种基于继承性重构解码策略的改进的遗传算法,同时设计了一种已知单元构型下的订单与原制造单元之间的相似性计算方法,并通过量化对原制造单元重构的继承程度,保证了制造单元的最大化的继承原制造单元的构型而进行重构,最后结合某光电观测产品零件的实际生产数据,验证了所提模型与算法的有效性与可行性。Abstract: Aiming to the demand for efficiency and flexibility under multi variety and variable batch production and the problem that existing manufacturing units were difficult to support high quality consistency and efficiency of key parts under fragmented orders, a Cmax and minimizing the difference of virtual manufacturing cell composition before and after reconfiguration, an improved genetic algorithm based on inherited reconfiguration decoding strategy was proposed, and a similarity calculation method between orders under known cell configuration and the original manufacturing cell was designed. It ensures the maximization of the manufacturing cell and carries out reconstruction by inheriting the configuration of the original manufacturing cell. Finally, the validity and feasibility of the proposed model and algorithm are verified by the actual production data of a photoelectric observation product. -
表 1 各设备种类与加工设备映射关系
Table 1. Mapping relationship between each equipment type and processing equipment
Type $ {K}_{1} $ $ {K}_{2} $ $ {K}_{3} $ $ {K}_{4} $ $ {K}_{5} $ $ {K}_{6} $ $ {K}_{7} $ $ {K}_{8} $ Number $ {M}_{2},\; {M}_{7}$ $ {M}_{5} $ $ {M}_{8} $ $ {M}_{4} ,\;{M}_{6}$ $ {M}_{11} $ $ {M}_{9},\;{M}_{12} $ $ {M}_{1} ,\;{M}_{10}$ $ {M}_{3} $ 表 2 各个设备之间的距离
Table 2. Distance of each equipment
Equipment number $ {M}_{1} $ $ {M}_{2} $ $ {M}_{3} $ $ {M}_{4} $ $ {M}_{5} $ $ {M}_{6} $ $ {M}_{7} $ $ {M}_{8} $ $ {M}_{9} $ $ {M}_{10} $ $ {M}_{11} $ $ {M}_{12} $ $ {M}_{1} $ 0 - - - - - - - - - - - $ {M}_{2} $ 3 0 - - - - - - - - - - $ {M}_{3} $ 10 8 0 - - - - - - - - - $ {M}_{4} $ 12 11 2 0 - - - - - - - - $ {M}_{5} $ 10 13 4 3 0 - - - - - - - $ {M}_{6} $ 8 9 13 15 15 0 - - - - - - $ {M}_{7} $ 10 12 9 12 9 3 0 - - - - - $ {M}_{8} $ 8 7 12 14 11 4 2 0 - - - - $ {M}_{9} $ 19 16 23 26 25 17 14 12 0 - - - $ {M}_{10} $ 17 15 19 16 17 9 11 14 23 0 - - $ {M}_{11} $ 5 8 10 12 13 8 7 10 15 17 0 - $ {M}_{12} $ 18 20 13 14 16 6 7 9 19 26 5 0 表 3 原有制造单元信息
Table 3. Original manufacturing unit information
Manufacturing
cellCell 1 Cell 2 Part family $ {J}_{1} $ ,$ {J}_{5} $ $ {J}_{2} $ ,$ {J}_{3} $ ,$ {J}_{4} $ ,$ {J}_{6} $ Machine $ {M}_{2} $ ,$ {M}_{3} $ ,$ {M}_{7} $ ,$ {M}_{10} $ ,$ {M}_{11} $ $ {M}_{4} $ ,$ {M}_{6} $ ,$ {M}_{9} $ ,$ {M}_{12} $ 表 4 原制造单元对应的零件族的基本信息
Table 4. Basic information of the part family corresponding to the original manufacturing unit
Order Count Process Can use machine Time $ {J}_{1} $ 39 $ {O}_{11} $ $ {M}_{1} $ /$ {M}_{2} $ 152 $ {O}_{12} $ $ {M}_{3} $ /$ {M}_{4} $ /$ {M}_{5} $ 222 $ {O}_{13} $ $ {M}_{6} $ /$ {M}_{7} $ /$ {M}_{8} $ 277 $ {O}_{14} $ $ {M}_{10} $ 207 $ {O}_{15} $ $ {M}_{11} $ 126 $ {J}_{2} $ 54 $ {O}_{21} $ $ {M}_{3} $ /$ {M}_{4} $ /$ {M}_{5} $ 150 $ {O}_{22} $ $ {M}_{6} $ /$ {M}_{7} $ /$ {M}_{8} $ 223 $ {O}_{23} $ $ {M}_{9} $ 171 $ {J}_{3} $ 45 $ {O}_{31} $ $ {M}_{3} $ /$ {M}_{4} $ /$ {M}_{5} $ 190 $ {O}_{32} $ $ {M}_{6} $ /$ {M}_{7} $ /$ {M}_{8} $ 260 $ {O}_{33} $ $ {M}_{9} $ 168 $ {O}_{34} $ $ {M}_{12} $ 216 $ {J}_{4} $ 138 $ {O}_{41} $ $ {M}_{3} $ /$ {M}_{4} $ /$ {M}_{5} $ 100 $ {O}_{42} $ $ {M}_{6} $ /$ {M}_{7} $ /$ {M}_{8} $ 130 $ {O}_{43} $ $ {M}_{9} $ 150 $ {J}_{5} $ 75 $ {O}_{51} $ $ {M}_{1} $ /$ {M}_{2} $ 260 $ {O}_{52} $ $ {M}_{3} $ /$ {M}_{4} $ /$ {M}_{5} $ 340 $ {O}_{53} $ $ {M}_{6} $ /$ {M}_{7} $ /$ {M}_{8} $ 204 $ {J}_{6} $ 36 $ {O}_{61} $ $ {M}_{3} $ /$ {M}_{4} $ /$ {M}_{5} $ 279 $ {O}_{62} $ $ {M}_{6} $ /$ {M}_{7} $ /$ {M}_{8} $ 126 $ {O}_{63} $ $ {M}_{12} $ 457 $ {O}_{64} $ $ {M}_{9} $ 105 $ {O}_{65} $ $ {M}_{11} $ 568 表 5 新增订单的基本信息
Table 5. Basic information of new order
Order Count Process Can use machine Time $ {J}_{7} $ 45 $ {O}_{71} $ $ {M}_{1} $ /$ {M}_{2} $ 176 $ {O}_{72} $ $ {M}_{3} $ /$ {M}_{4} $ /$ {M}_{5} $ 470 $ {O}_{73} $ $ {M}_{6} $ /$ {M}_{7} $ /$ {M}_{8} $ 300 $ {O}_{74} $ $ {M}_{11} $ 324 $ {J}_{8} $ 32 $ {O}_{81} $ $ {M}_{1} $ /$ {M}_{2} $ 386 $ {O}_{82} $ $ {M}_{3} $ /$ {M}_{4} $ /$ {M}_{5} $ 160 $ {O}_{83} $ $ {M}_{6} $ /$ {M}_{7} $ /$ {M}_{8} $ 145 $ {O}_{84} $ $ {M}_{10} $ 78 $ {O}_{85} $ $ {M}_{11} $ 237 $ {J}_{9} $ 98 $ {O}_{91} $ $ {M}_{3} $ /$ {M}_{4} $ /$ {M}_{5} $ 90 $ {O}_{92} $ $ {M}_{6} $ /$ {M}_{7} $ /$ {M}_{8} $ 190 $ {O}_{93} $ $ {M}_{9} $ 93 $ {O}_{94} $ $ {M}_{12} $ 264 表 6 订单与原制造单元的相似性分析
Table 6. Similarity analysis between order and original manufacturing unit
Original manufacturing cell Orders $ {J}_{7} $ $ {J}_{8} $ $ {J}_{9} $ Cell 1 0.49 0.31 0.13 Cell 2 0.22 0.04 0.89 表 7 制造单元继承性重构对比
Table 7. Comparison of manufacturing cell inheritance reconstruction
Manufacturing cell Content Cell 1 Cell 2 Cell 3 Original manufacturing cell Part family $ {J}_{1} $ ,$ {J}_{5} $ $ {J}_{2} $ ,$ {J}_{3} $ ,$ {J}_{4} $ ,$ {J}_{6} $ - Devices $ {M}_{2} $ ,$ {M}_{3} $ ,$ {M}_{7} $ ,$ {M}_{10} $ ,$ {M}_{11} $ $ {M}_{4} $ ,$ {M}_{6} $ ,$ {M}_{9} $ ,$ {M}_{12} $ - Reconfigurable cell Part family $ {J}_{5} $ $ {J}_{2} $ ,$ {J}_{3} $ ,$ {J}_{4} $ ,$ {J}_{1} $ ,$ {J}_{7} $ ,$ {J}_{9} $ Devices $ {M}_{2} $ ,$ {M}_{3} $ ,$ {M}_{7} $ ,$ {M}_{10} $ $ {M}_{4} $ ,$ {M}_{6} $ ,$ {M}_{9} $ $ {M}_{1} $ ,$ {M}_{5} $ -
[1] Gao J, Sun L, Gen M. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems [J]. Computers & Operations Research, 2008, 35(9): 2892-2907. [2] Altom R J. Costs and savings of group technology, Research Re-port[R]. Dearborn: Society of Manufacturing Engineers, 1978. [3] Nomden, Slomp J, Suresh N C. Virtual manufacturing cells: A taxonomy of past research and identification of future research issues. [J]. International Journal of Flexible Manufacturing Systems, 2006, 17(2): 71-92. [4] Ratchev S M. Concurrent process and facility prototyping for formation of virtual manufacturing cells [J]. Integrated Manufacturing Systems, 2001, 12(4): 306-315. doi: 10.1108/09576060110393406 [5] Safaei N, Saidi-Mehrabad M, Jabal-Ameli M S. A hybrid simulated annealing for solving an extended model of dynamic cellular manufacturing system [J]. European Journal of Operational Research, 2008, 185(2): 563-592. doi: 10.1016/j.ejor.2006.12.058 [6] Deep K, Singh P K. Dynamic cellular manufacturing system design considering alternative routing and part operation tradeoff using simulated annealing based genetic algorithm [J]. Sādhanā, 2016, 41(9): 1063-1079. [7] Gert Nomden, Durk-Joukevan der Zee. Virtual cellular manufacturing: configuring routing flexibility [J]. International Journal of Production Economics, 2008, 112(1): 439-451. doi: 10.1016/j.ijpe.2007.04.010 [8] Kesen S E, Das S K, Güngör Z. A genetic algorithm based heuristic for scheduling of virtual manufacturing cells (VMCs) [J]. Computers & Operations Research, 2010, 37(6): 1148-1156. [9] Gorkemli, Latife, Baykasoglu, et al. Dynamic virtual cellular manufacturing through agent-based modelling [J]. International Journal of Computer Integrated Manufacturing, 2017, 30(6): 564-579. doi: 10.1080/0951192X.2016.1187294 [10] Delgoshaei A, A Ariffin M K, Gomes C, et al. A multi-period scheduling of dynamic cellular manufacturing systems in the presence of cost uncertainty [J]. Computers & Industrial Engineering, 2016, 100: 110-132. [11] Azadeh A, Elahi S, Farahani M H, et al. A genetic algorithm-taguchi based approach to inventory routing problem of a single perishable product with transshipment [J]. Computers & Industrial Engineering, 2017, 104: 124-133. [12] Bayram H, Sahin R. A comprehensive mathematical model for dynamic cellular manufacturing system design and linear programming embedded hybrid solution techniques [J]. Computers & Industrial Engineering, 2016, 91(1): 10-29. [13] Hu J, Gu X, Gu W. Robust optimization approach for short-term scheduling of batch plants under demand uncertainty [J]. Kybernetes, 2011, 40(5/6): 860-870. [14] Aksoy A, Öztürk N. Simulated annealing approach in scheduling of virtual cellular manufacturing in the automotive industry [J]. International Journal of Vehicle Design, 2010, 52(1/2/3/4): 82-95. doi: 10.1504/IJVD.2010.029637 [15] Sakhaii M, Tavakkoli-Moghaddam R, Bagheri M, et al. A robust optimization approach for an integrated dynamic cellular manufacturing system and production planning with unreliable machines [J]. Applied Mathematical Modelling, 2015, 40(1): 1-13. [16] Jiang Y, Zhou P, Zhan R, et al. An artificial bee colony with self-adaptive operators and alterable search depth approach for intercell scheduling [C]//2016 IEEE Congress on Evolutionary Computation (CEC), 2016: 112–119. [17] Tang J, Wang X, Kaku I, et al. Optimization of parts scheduling in multiple cells considering intercell move using scatter search approach [J]. Journal of Intelligent Manufacturing, 2010, 21(4): 525-537. doi: 10.1007/s10845-008-0236-8 [18] Di Tong. Study on virtual cellular dynamic formation and scheduling with new task insertion [D]. Zhenjiang: Jiangsu University of Science and Technology, 2015. (in Chinese) [19] 徐雨. 离散型生产线的制造单元重构技术研究[D]. 贵州大学, 2019. Xu Y. Research on manufacturing cell reconfiguration techno-logy of discrete production line[D]. Guiyang: Guizhou University, 2019. (in Chinese)