定制件柔性工艺路线的车间调度优化研究*

周 珂，吕 民，夏自祥,3，李小冬

(1.济宁学院 机械工程系,山东 曲阜 273155;2.哈尔滨工业大学 机电工程学院,黑龙江 哈尔滨 150001;3.中国矿业大学 机电工程学院,江苏 徐州 221116)

0 引 言

随着我国智能制造水平不断提升，定制化生产得以实现，定制化产品需求越来越旺盛[1]。在生产中，临时件、加急件的存在经常扰乱正在执行的制造任务，定制产品的增多使得车间调度更加复杂。频繁更换工件种类的调度方案在一定程度上降低了生产效率。在大规模生产和定制生产共存的环境下，如果定制产品只利用大规模生产排产后的设备空闲时间进行加工，将会延长定制品的市场响应周期，降低产品的市场竞争力。

在大规模生产环境下，机械产品的工艺设计主要考虑采用哪种工艺能够保证制造精度，以当前的生产批量使用哪些设备能够达到成本最低的目的。在能够满足精度要求的前提下选择制造成本最低的设备，制订工艺路线，编制工艺卡片，并据此进行车间调度，组织生产。

在智能制造环境下，定制产品比非定制产品的利润高，与成本相比，市场响应能力是企业争取订单的关键。因此，定制化产品工艺设计的目的，是在保证制造精度和其他产品工期的基础上，充分利用现有设备和各种工艺方案，尽量缩短定制产品工期。不同加工方法和加工设备对应不同的工艺路线，而工艺路线直接影响车间调度。由于制订工艺路线时只参考了设备空闲率，可能导致无法同时满足定制品和非定制品交货期。因此，需要将工艺路线和车间调度同时考虑进行制造过程优化。

近年来，国内外很多学者对车间调度优化进行了研究；张浩[2]采用改进型启发式搜索算法对板材长度可变的二维矩形排样优化问题展开研究，采用基于叠板数分层的多叉树递归搜索算法解决了考虑叠板组批的切割与排样协同优化问题；胡东方等[3]利用改进的信息熵免疫算法对复杂产品定制设计的柔性化和智能化展开了研究；潘瑞林等[4]针对冷轧企业大批量生产模式与多品种、小批量的市场需求之间存在的矛盾，构建了基于改进粒子群的模糊聚类算法并进行求解；赵桂芝等[5]采用改进免疫克隆算法对农机转向器生产车间对突发事件调度不及时及车间调度问题进行了研究；汤洪涛等[6]采用了混合布谷鸟搜索求解算法对不确定的动态事件干扰混流生产车间预先调度实施的问题进行了研究；解潇晗等[7]采用目标加权法对柔性作业车间低能耗调度问题展开了研究，并在MATLAB中对生产实例进行了仿真；鲁宏浩等[8]利用分布估计—蚁群混合算法对柔性作业车间调度问题及其优化方法进行了研究；张源等[9]利用改进差分进化算法对于混合流水车间调度问题进行了研究；Chaudhry I A等[10]对一般柔性作业车间调度的算法进行了综述。

在以上研究中，前提条件是工序已知且加工顺序固定，而定制件存在柔性工艺路线。因此，在当前大规模生产和定制生产并存的环境下，迫切需要一种考虑定制件柔性工艺路线的车间调度优化方法。

笔者针对定制件生产周期长难以排产的问题，建立柔性工艺路线车间调度数学模型。

1 问题描述

笔者建立考虑定制件柔性工艺路线的车间调度数学模型，其符号及说明如表1所示。

表1 符号及说明

考虑定制件柔性工艺路线的车间调度问题可描述为：车间中存在N个待加工非定制工件PN={PNi|i=1,2,…,N}，M个待加工定制工件PC={PCi|i=1,2,…,M}，L台可用加工设备M={Ml|l=1,2,…,L}。

工件Pi(i=1,2,…,N+M)的加工过程由Ni个工序PPi1,PPi2,…,PPiNi组成，其中，非定制件的工艺路线固定(即工序及其顺序固定)，定制件的工艺路线存在柔性(即定制件的工序存在若干种不同方案)，工序PPij可在{Mk|k=1,2,…,K}中任何一台设备上完成(K为能够完成工序PPij的设备总数)。工序PPij的加工等待时间为TWij，使用设备Ml时工序PPij加工时间为TMijl，工序PPi(j-1)至工序PPij的运输时间为TTij，工序PPij加工前的装夹时间为TAij，工序PPij加工结束的拆卸时间为TDij。设备Ml单位时间能耗为ECl。工件Pi(i=1,2,…,N+M)的工序须符合工艺路线要求，即PPi1→PPi2→…→PPiJ。

另外，工件在同一时刻只有一台设备对其加工，设备同一时刻只能加工一个工件，即：加工过程须满足不可中断约束、工件唯一性约束和设备唯一性约束：

(1)工件Pi(i=1,2,…,N+M)的工序PPij，可在预先给定的设备集{Mk|k=1,2,…,K}的任一台设备上加工，且∃PPij，使|Mij|>1；

(2)每个工件Pi(i=1,2,…,N+M)的工序须符合当前工艺路线要求，即PPi1→PPi2→…→PPiJ；

(3)工件的工艺路径多样(不同工件的工艺路线可能相同或不同)，即∃Pk,Pj(k≠j),l，使得Mkl≠Mjl；

(4)工件不可重入，即对∀PPij,PPik(j≠k)，Mij∩Mik=φ。

2 数学模型

求解考虑定制件柔性工艺路线的车间调度问题，即是在满足非定制件工期的约束条件下，确定定制件的工艺路线，安排全部工件的每道工序的加工设备及加工顺序，以达到最小化定制件完工时间Tmax、能耗EC和成本C的目的，具体为：

(1)

Tmax=max{Ti|i=1,2,…,M}

(2)

(3)

(4)

式中：Ti—第i个工件的完工时间；M—定制件包括的工件数量；TMl—第l台加工设备Ml的总加工时间。

本文的调度优化目标是定制件的完工时间短、总能耗和总成本低，目标函数为：

minf=min(Tmax+EC+C)

(5)

约束条件是满足非定制件工期要求，约束表达为：

Ti≤DLi(i=1,2,…,N)

(6)

在考虑定制件柔性工艺路线的车间调度问题中，存在3个决策过程：(1)确定定制件的工艺路线，即加工工序及顺序；(2)按照当前的工艺路线将全部工件(包括定制件和非定制件)对应的工序，分配给具备加工能力的设备(即Mij={Mk|Mij=k=1,2,…,K}中的某台机床设备)进行加工；(3)确定设备Ml(l=1,2,…,L)上相应工序Pij的加工顺序。

3 分层协同进化算法设计

针对考虑定制件柔性工艺路线的车间调度问题，本文设计了分层协同进化算法，将确定定制件的工艺路线作为第一层，将按照当前定制件工艺路线分配加工设备并安排加工顺序作为第二层，协同迭代进行求解。

分层协同进化算法流程如图1所示。

图1 分层协同进化算法流程

采用二元组(i,)对第一层染色体进行编码，进入第二层优化时，采用第一层当代(i,)组成三元组(i,,)对第二层染色体进行编码；三元组(i,,)表示第i个工件的第j个工序i，安排在机器k上加工，基因从左到右的排列顺序表示全部工序的加工顺序。因此，第二层优化中每条染色体都是由所有工序组成的一个有序序列，染色体的长度等于全部工件的工序总数。

在迭代中，笔者采用POX交叉算子进行交叉来保证工件出现的次数和工序之间的顺序约束关系[11]。其具体步骤为：

步骤1：初始化算法参数。进化代数g=0，h=0。基于定制件加工时间反向搜索生成第一层初始种群，PL=PL(0)，J(0)=J1+J2+…+JN+M，J=J(0)；

步骤2：染色体长度LL(g)=J，基于负载均衡生成第二层初始种群；

步骤3：计算种群个体适应度值f；

步骤4：判断是否满足终止条件1，若满足则执行步骤10，若不满足则执行步骤5；

步骤5：选择第二层进化种群染色体中的两个父代个体生成差分矢量，选择另一个体与差分矢量求和生成实验个体；

步骤6：解码实验个体，判断生成的调度方案是否有效。若方案有效，则进入步骤8；若方案无效，则进入步骤7进行实验个体修正；

步骤7：修正无效方案对应的实验个体，检查并修正：数量大于N+M或存在重复工件编号的个体；解码后Mij∉{Mk|k=1,2,…,K}的个体；设备编号数量大于L的个体等；

步骤8：父代个体与实验个体交叉生成新个体；

步骤9：基于适应度选择个体；第二层进化代数h加1，返回步骤3；

步骤10：判断第一层进化代数是否为0，若为0则用0代f最小值为f赋值f=f(0)；若不为0则将g代f最小值(minf(g))与当前f值比较，并取其中更小者保留在f中；

步骤11：判断是否满足终止条件2，若满足则输出工艺路线及调度方案，若不满足则g=g+1，h=0，PL=PL(g)，J=J(g)，执行步骤2。

4 实例验证及分析

某工业集团25车间中共有正常排产的10批非定制工件和新加入排产的2批定制工件，涉及11台可用设备。

实例中涉及的非定制件部分工序如表2所示。

实例中涉及的定制件部分工序如表3所示。

表2 非定制件部分工序

表3 定制件部分工序

定制件生产任务下达前，原非定制件调度方案如图2所示。

图2 原非定制件调度方案

定制件生产任务下达后，将所有工件生产任务合并。非定制件优先的调度方案如图3所示。

图3 非定制件优先的调度方案

定制件优先且不考虑柔性工艺路线的调度方案如图4所示。

图4 定制件优先且不考虑柔性工艺路线的调度方案

在满足非定制件工期约束下，以最小化定制件完工时间、总能耗、总成本为目标，考虑柔性工艺路线的工件调度方案如图5所示。

图5 考虑柔性工艺路线的工件调度方案

在定制件优先，且不考虑柔性工艺路线的调度方案中，工件1～10总完工时间为136 d，定制件11、12合计完工时间为30 d，全部工件总完工时间为166 d；

在定制件优先，且考虑柔性工艺路线的调度方案中，工件1～10总完工时间为133 d，定制件11、12合计完工时间为14 d，全部工件总完工时间为147 d。

对比两种方案发现：考虑定制件柔性工艺路线的调度方案，在满足非定制件工期约束的前提下，定制件完工时间缩短了53%。

5 结束语

本文建立的考虑定制件柔性工艺路线的车间调度数学模型，描述了包含可变工艺路线的定制件的车间调度问题。实例验证表明，文中设计的分层协同进化算法，求解考虑定制件柔性工艺路线的车间调度问题可行且有效；对比不同方案发现，考虑定制件柔性工艺路线的调度方案，在满足非定制件工期约束的前提下，能够更加快速地完成定制件订单，提高定制件的市场响应速度，提升产品市场竞争力。

从优化后的方案可以看出，要进一步缩短生产周期，需要对批量较大的工件批次进行合理分解，下一步研究中，笔者将根据瓶颈设备集优化工件批次，建立考虑柔性加工批次和工艺路线的调度模型进行优化。