自动化集成电镀生产线的生产调度问题分析

生产调度是生产管理的核心内容和关键技术，其任务是在企业有限的资源约束下，确定工件在相关设备上的加工顺序和加工时间，以保证所选定的生产目标最优。系统、全面、合理的生产调度方案不仅有助于企业提高综合管理水平，而且可为之带来显着的经济效益[1-2].

　　    表面处理是包括电镀、化学镀、表面氧化等多种类型的表面加工技术。传统的表面处理生产线根据经验安排生产计划，在已有的生产计划和加工工艺条件下采用几何规划法绘制载料小车运动流程图来安排吊运任务[3-4],以防止设备任务冲突。该方法工作量大，而且不能优化生产周期。

　　    本文根据某厂的自动化集成电镀生产线实际工况，在满足设定的加工工艺参数和加工设备不冲突的约束下，利用遗传算法（genetic algorithms,GA）与模拟退火算法（simulated annealing, SA）的优势，采用遗传模拟退火算法（genetic simulated al-gorithms,GSA）排定生产线作业计划[5-10],求解各批工件在相应设备上的加工任务。

　　    1·问题描述

　　    在电镀生产中，不同品种的电镀种类可共用某些设备，比如前处理和一些后处理工艺等，因此在电镀生产线可以集成某些具有部分相同工艺的电镀种类，而不同产品的工序可能不同。但在生产线设计中根据工序集中的原则排列设备，使产品的加工工序方向一致。在某些对于加工时间严格控制的表面处理操作中，生产工艺要求中间产物在上一设备处理完毕后，立即转移到下一设备中加工，不能延误，以免破坏电镀膜，因此，该生产线采用了零等待（zerowaiting, ZW）方式。在生产线中，为了提高生产效率，在部分关键加工工位设有若干平行设备单元，如设备EL具有a个平行单元。图1为该生产过程示意图。

　　    由图1可知该电镀生产线是流水线生产，可简化为Flow Shop调度问题：N批工件在M个设备单元的流水加工过程。每批工件在各个设备上的加工顺序相同；每批工件在每个设备单元上只加工1次；在某一时刻每个设备单元只加工1批产品，每批产品只在一个设备单元上加工；各批工件在各台设备上的加工时间和准备时间已知；要求得到某种调度方案使得某项指标最优[2].

　　    设N批产品的加工序列为P={P1,P2,…，Pn};M个设备单元的序列为E={E1,E2,…，EL,…，EM};第i批被加工的产品在第j个设备上需要的加工时间为T（i,j）；产品Pi（i=1,2,…，N）的第1道加工开始时间为S（Pi,E0）；产品Pi在第k台设备的加工时间为T（Pi, k）， i=1,2,…，N, k=1,2,…，M;加工准备时间为A（Pi,k）；加工开始时间记为S（Pi,k）；加工完成时间记为C（Pi,k）。调度目标是确定产品的最优加工序列P={P1,P2,…，Pn},并求解产品Pi的在各个加工设备单元的加工开始时间S（Pi,k）和结束时间C（Pi,k），使得总加工完成时间即MakeSpan最小。

　　    2·数学模型的建立

　　    2.1虚拟工位的引入

　　    在加工工艺路线中引入虚拟工位[11],即当产品不在某一设备上加工时，设产品在该设备的加工时间为0,其辅助时间也为0.这样得出每批产品的虚拟加工工序相同，又可以反映生产工序设置的实际情况，同时方便数学模型的建立。设产品Pi在设备Ej不加工，则应该满足。

　　    2.2约束条件的建立

　　    2.2.1 加工开始时间和结束时间的约束

　　    对于电镀产品的加工过程，如果给定任一批次产品Pi（i=1.2,…，N）的第1道加工工序的开始时间S（Pi,0）、各个工位的加工时间T（Pi,k）和加工准备时间A （Pi, k） （k=1,2,…，M ），当T（Pi,k）=0时，表示产品Pi在第k个工位上的加工时间为0,即不需要在该工位加工，则Pi在各个设备的加工完成时间也就确定了，即

　　    工件在加工前的辅助时间A（Pi,k）主要是指载料小车将该批从上一槽位提取上升到高位，停止一段时间滴去依附在工件上的水和药液以减少药液交叉污染后行走到下一个工位，然后放置在夹具上的时间。提取、滴水和放置过程固定，行走时间根据需要加工的下移工位与当前工位的距离来计算的。根据生产实际情况，上升时间、下降时间和滴水时间各为5 s,基本行走世间为6 s,每多移动一个工位增加1 s.虚拟工位的辅助时间为0,非虚拟工位的辅助时间为：

　　    2. 2. 2 加工工序的约束

　　    为了计算一个确定产品加工序列P中各批工件的加工开始时间，将生产线划分为2类：即不具有平行设备单元的生产线段和具有平行设备单元的生产线段。

　　    当生产线不存在平行工位的时候，为避免设备的任务重叠，即在某一工位，前一个加工任务没有完成时后一个加工任务已经到来，文献[12]提出如下的约束条件：

　　    2.2.3 平行设备单元的约束

　　    在产品序列P下，当产品Pi加工到具有平行设备单元工位的时候，如果保证产品在该工位不发生设备任务冲突，则必须满足在当前时间下，该工位至少有一个平行设备单元空闲，即Pi的加工开始时间至少应大于在Pi之前加工的、在工位L的加工时间不为0且与Pi最相邻的a个工件加工完成时间的最小值，即：

　　    2.2.4 生产周期的计算

　　    若给定产品加工序列P=（ P1,P2,…，PN），采用一种离散-回缩策略计算其MakeSpan,即在Gantt图（图2）上已知Pi的S（Pi,E0），离散Pj的S（Pj,E0）一个足够大的值能使任何一台设备的任务都不会重叠，然后开始回缩S（Pj,E0）到极限位置，即刚好不发生设备任务重叠位置。离散的时间可选择为Pi在单个加工单元上的最大加工时间。这种离散-回缩策略能够有效避免设备任务冲突，计算出总生产完成时间。生产线作业计划的优化排序可采用遗传模拟退火算法求解出。程序设计模块如图3所示。

　　    2. 3数学模型的建立

　　    以最大流程时间MakeSpan最小为调度指标，则具有若干平行单元的零等待顺序多目的电镀自动化集成生产线生产优化调度的数学模型可表达如下：

　　    3·生产线作业计划的优化

　　    3. 1 优化算法的选择

　　    遗传算法[5-10]因其高度的并行处理能力和全局搜索能力而被广泛地应用于诸多领域。理论上遗传算法依"概率1"收敛于问题的最优解，然而实践应用中，遗传算法会出现过早收敛现象、局部寻优能力较差等不足[5].模拟退火具有较强的局部寻优能力，它依据Metropolis准则接受新解，能使搜索过程避免陷入局部最优解，但把握整个搜索过程的能力不够，不便于使搜索过程进入最有希望的搜索区域，从而使得模拟退火的运算效率不高[5].

　　    针对遗传算法和模拟退火算法存在的问题，本文选择一种基于遗传算法和模拟退火算法的遗传模拟退火算法。在算法中采用基于工件加工顺序的编码，通过遗传模拟退火算法搜索解空间，找出一个最优的工件加工序列以使MakeSpan最小，其程序流程如图4所示。

　　    由图3可知，该混合策略本质上是一个2层并行搜索结构。内部层次上，混合算法在各温度下串行的依次进行SA和GA搜索，是一种2层串行结构，其中SA的初始解来自GA的进化结果，SA经Metropolis抽样过程得到的解又成为GA进一步进化的父代种群。外部层次上，GA提供了并行搜索结构，使SA转化成为并行SA算法，因此混合算法始终进行种群并行优化。通过退温历程（即初温、退温函数、抽样次数）控制混合策略的搜索行为。遗传模拟退火算法在温度较高时表现出较强的概率突跳性，体现为对种群的"粗搜索",温度较低时演化为趋化性局部搜索算法，体现为对种群的"细搜索".这种混合不仅是算法结构上的结合，而且是搜索机制和进化思想上的相互补充，为较好解决复杂优化问题提供了有利的途径。

　　    3. 2 GSA算法的设计

　　    1）初始化控制参数，设置种群规模popsize、交叉概率pc、变异概率pm,初始化遗传代数计数器gen=0,初始化种群个体计数器pop=2.

　　    2）初始化种群P（gen），采用基于工件的编码，随机产生初始加工序列；计算初始种群的适应度值fP1,fP2,…，fPM.由于调度的目标是求最大流程时间的最小值，所以适应度函数形式如式（9）所示[13]:

　　    f（x）=MakeSpan.为了减小程序运行中的舍入误差，取c=0,k=10 000.

　　    3）设定初温T0.初温选择的主要思想是为了平稳分布中每一状态的概率相等，这样容易估计一个值为T0=kδ，k充分大，δ=max{f|c∈D}-min{f|c∈D},其中D为状态空间。可令δ为初始化种群中个体间MakeSpan最大值和最小值之差。

　　    4）对现有种群采用如下操作，直至产生下一代新的种群：

　　    ①从父代路径中选择复制子代。PS（gen）←select[P（gen）].本算法采用轮盘赌选择法，同时将父代最佳个体直接复制给子代。

　　    ②进行子代路径交叉操作。根据交叉概率pc由PS（gen）中第i个个体PSi（gen）和第j个个体PSj（gen）交叉得到新个体Pci（gen）和Pcj（gen），并计算Pci（gen）和Pcj（gen）的适应度值。

　　    ③采用Metropolis机制确定的接受概率p来确定是接受还是拒绝新个体Pmi（gen）和Pmj（gen）。

　　    ④进行子代路径变异操作。根据变异概率pm由Pc（gen）中第i个个体Pci（gen）和第j个个体Pcj（gen）变异得到新个体Pmi（gen）和Pmj（gen），计算Pmi（gen）和Pmj（gen）的适应度值，并采用Metropolis机制确定是否接收新个体。

　　    ⑤判断子代是否已经生成完毕，即pop是否达到popsize.若不等于，则： P （gen+ 1）=Pm（gen），pop=pop+2;转步骤①；若等于则转步骤④。

　　    5）算法终止条件判断，若不满足，则P（gen）=Pm（gen），pop=2,按降温表更新温度参数T,转步骤4）；若满足，则停止计算，输出最优解。采用基于不改变规则的控制法和温度控制法，即当一定迭代次数内没有改变最优解或者当前温度低于设定温度时，就认为达到算法终止条件，停止循环，输出计算结果。

　　    4·仿真实验分析

　　    在某厂家的表面处理车间排列2条自动化生产线，各有21个加工设备单元，其编号为101~121, 201~221,其中103酸锌镀锌和217氰化镀镉有3个平行设备单元，每条生产线上各有1台自动载料小车转运工件，采用1个地轨车在生产线1和生产线2之间转运工件。应用上述调度算法，采用C++Builder开发了生产调度系统，并嵌入其自动化生产线的控制程序中。

　　    根据实际的加工工艺，对该算法进行仿真。当随机选择10批产品和20批产品，分别采用SA和GSA计算10次，其计算结果如下： GA交叉概率为0·9,变异概率为0. 03,种群数量为20,根据产品批次选择不同的遗传运行次数Run; GSA参数为退火的初温为2* （Max_MakeSpan-Min _MakeSpan），退火的速度为0. 9,最大运行次数为200,交叉概率为0·9,变异概率为0. 15,种群数量为20,当连续30代其最优解没有发生变化时退出该循环。

　　    5·结束语

　　    本文分析了自动化集成电镀生产线的生产调度优化问题，在实际加工工序的基础上引入虚拟工位将之转化为改进的Flow Shop问题，在设备加工任务不能重叠和工件加工零等待的情况下，考虑了各批工件在不同工位间的加工辅助条件，分析了生产线的加工约束条件，采用离散-回缩策略求解在一定的工件加工顺序下的总加工完成时间以及在各个设备上的加工时间，给出了生产调度的数学模型。对遗传算法和模拟退火算法的有机结合，构造了一种遗传退火混合算法。该算法采用了基于工作的编码，因而保证了遗传进程中生成个体的可行性，有效地解决了工件机器顺序的约束限制。根据生产线的实际加工情况，对算法进行了测试，结果表明，该算法具有良好的收敛性和鲁棒性。实践表明，该调度模块能够提高生产线的加工质量，保证生产线的安全，提高生产效率。