基于混合蚁群算法的多模式下模具车间调度系统研究

摘　要：

摘　要：针对多模式下模具车间调度问题，设计了一种混合蚁群算法进行求解。最后在企业信息系统的基础上，基于该算法模块设计了模具车间调度系统的框架。

关键词：

关键词：多模式　调度系统　模具车间　蚁群算法

     模具制造企业属于离散制造行业，客户订单随机下达，并且模具的工序复杂，返修现象随机出现，使得模具车间调度问题越来越复杂，人工制定作业计划变得越来越困难，亟需一套适用的模具车间调度系统来解决该类问题。模具车间是典型的柔性作业车间，而柔性作业车间调度问题是比经典作业调度问题更复杂的NP-hard 问题[1]。目前，针对该类调度问题，已经提出了很多求解算法。Pezzella等人[2]采用多种交叉方法和多种变异方法相混合的遗传算法对该调度问题进行了求解，取得了较好的优化结果；ZHANG等人[3]设计了一种混合粒子群算法。本文为求解多模式下的模具车间调度问题，设计一种混合蚁群算法。最后，在企业应用系统的基础上嵌入该算法模块，设计了模具车间调度系统的框架结构和总体流程。

1　多模式下模具车间调度问题描述

　　模具车间通常是生产模具产品的某一类零件，车间由若干个加工中心组成，每个加工中心包含若干台同等并行机。每一个模具零件需要经过多个加工工序，并且零件的加工顺序是预先确定的。根据零件所属产品类型和加工精度要求的不同，每道工序可以由若干个（一个或者多个）加工中心加工。当选择不同的加工中心，所需要的加工时间也不相同。

　　该类车间是一类典型的柔性作业车间，在实际生产过程中，采用并行加工的思想，首先将大的模具零件分割成若干个小工件，然后并行加工，最后再组装，以缩短零件的加工周期。当零件的某个工序选定了加工中心之后，配置不同数量的机器时，整个零件的加工时间是不同的。图1表示某一类模具零件分割成3个工件加工，单个工件在某加工中心的加工工时为T，该加工中心包括3台同等并行机，则该类情况下模具零件具有3种加工模式可选。当为零件分别配置1、2、3台机器时，模具零件的加工时间分别为3T、2T和T，称该类现象为多模式现象。为了更加准确地制定生产作业计划，就不得不考虑此类问题。

2　混合蚁群算法设计

2.1　利用蚁群算法配置模具零件的加工中心和加工模式

2.1.1　结点构造过程

　　模具零件首先需要配置加工中心和加工模式，可以把问题描述为如图2所示的有向结点图。图中的每一行对应模具零件的每道加工工序，而每一列对应加工中心。O0表示起始结点，Oij表示第i个零件的第j道工序，Oijk表示第i个零件的第j道工序选择了加工中心Wk。图中的椭圆表示工序可以配置的加工中心，椭圆内的圆圈表示相应工序可以配置的加工模式，都是蚂蚁需要爬离的障碍物。图中的黑圆球和黑实线表示蚂蚁选择了相应的加工中心和加工模式。

2.1.2　结点选择规则

     虚拟起始结点为所有蚂蚁的出发点，当模具零件的某个工序选择了相应的加工中心之后，需要再为该工序选择一种加工模式，的选取按照以下规则进行：

(1)

     式（1）中，表示结点在时刻的信息素浓度，表示期望程度。为随机数，以参数确定蚁群在决策时对知识探索与利用的权重。在搜索的过程中，蚂蚁以概率选择值最大的加工模式，并且又让蚂蚁以的概率来探索其它路径，其它路径的选择概率可以设置为公式（2）：

  (2)

2.1.3　更新信息素浓度的规则

　　在算法更新信息素浓度的过程中，文献[4]设计了一种只对历史最优解进行奖励的精英策略，文献[5]设计了一个动态蚁群种子集。本文将采用双向收敛策略，设定当前算法迭代中最好个解的蚂蚁和最差个解的蚂蚁分别构成蚂蚁种子集和。在更新信息素浓度的时候，集合中的所有蚂蚁都有权利强化其爬行路径上的结点信息素浓度，，而集合中的所有蚂蚁将弱化其爬行路径上的结点信息素浓度，更新规则分别为公式(3)和公式(4)：

          (3)                                                   (4)

　　其中，初始化信息素浓度设定为1；为信息素挥发系数，D为常数； 则通过完整的调度结果来获得。

2.2　利用优先级配置模具零件的加工顺序

　　在利用蚁群算法配置了每一道工序的加工中心和加工模式之后，下一步则需要配置模具零件在相应加工中心的加工顺序。

　　在模具生产车间的相应加工中心中，决定模具零件加工顺序的因素主要包括模具零件的重要系数和模具零件所属客户订单的重要系数。因此，本文对模具零件的优先级将采用向量来表示，该向量的优先级决定了加工中心中模具零件的加工顺序。在优先级向量中，表示模具零件的重要度系数，关键模具零件的重要度系数高于非关键模具零件的重要度系数；为模具零件的交货紧急程度系数，零件的交货期越靠前，该系数越高；表示模具零件所属订单的重要度系数，包括产品类型、客户重要度和订单总额，令。根据优先级向量可确定模具零件加工顺序的具体步骤：第一，对按照递减排列；第二，若相同，则对递减排列；第三，若仍然相同，则对递减排列；第四，如果三个优先级相等，则随机排列。

3　系统总体框架设计

     某模具企业已经运行了一套ERP系统，该ERP系统可以提供的数据为：零件数据，主要包括模具的所有零件、新零件到达信息、零件交货期更改信息和紧急零件插入信息；车间设备数据，包括车间所有加工设备的负荷信息和设备状态信息；工件加工数据信息，包括工件的加工状态（正在加工、未加工）；零件工艺数据，主要包括零件的工序信息、零件清单信息。以该ERP系统所提供的这部分数据作为数据源，以混合蚁群算法模块作为求解算法，建立了基于混合蚁群算法模块的多模式下模具车间调度系统框架如图3所示。该系统将充分调用ERP系统中的零件投放模块数据、车间反馈模块数据和工艺管理模块数据，利用混合蚁群算法模块进行运算，生成新的车间调度计划。

     为了使系统生成的车间作业计划能够顺利执行并且实时滚动更新，通过对应用企业的业务流程分析，设计了模具车间调度系统的总体流程如图4所示。该流程主要包括零件加工资源配置、调度参数调整和调度结果显示三部分内容。

     车间任务池中存放着到达的正常订单和紧急订单，对于任务池中的所有零件，系统将基于零件所属产品类型，根据资源配置模板自动配置加工资源信息，包括工艺路线、可选加工中心和可选加工模式。配置完成以上信息之后，系统将利用混合蚁群算法模块基于车间现有负荷来排产。若对排产的结果不满意，可以调整相应系统参数，然后再重新触发系统运行。允许调整的参数主要有零件优先级、零件的资源配置数据、部分零件作业计划以及占用加工资源的冻结、蚁群算法涉及的参数和加工中心的计划负荷。完成排产之后，系统以甘特图显示各零件的作业计划，利用柱状图显示车间各加工中心的负荷信息。对于系统排产的触发机制，设计了人为触发和定时触发两种方式。

4　结语

　　综上所述，笔者针对模具车间调度问题，考虑了模具零件加工多模式的现象，设计了一种混合蚁群算法对问题进行求解；并在企业应用系统的基础上嵌入该算法模块，设计了模具车间调度系统的框架结构以及总体流程。