基于多代理的敏捷制造单元调度研究

　　摘　要：在分析敏捷环境下敏捷制造单元调度特点的基础上，提出了基于多代理协作的敏捷制造单元模型，并根据该模型设计了一种混合遗传模拟退火(saga)单元调度算法。并给出saga和ga两种方法的比较结果。应用实例表明，该方法调度性能良好，调度过程快，支持任务的随机加入，为制造企业快速有效的响应市场，提高敏捷性提供了强有力的理论与技术支持。
　　关键词：敏捷制造单元；单元调度；多代理；遗传算法；模拟退火算法
　　敏捷制造的基本思想就是通过动态联盟方法，借助于信息通讯网络，建立能够对市场需求做出快速响应的开放性的制造体系[1]。敏捷制造并不单一的追求企业本身具有完备的先进的制造设备和技术，而是希望集中不同企业的优势，为特定的生产任务组建制造单元，任务完成，单元解体。具有上述特性的敏捷单元，称之为敏捷制造单元。由于制造单元是面向任务的，随着任务的生成而创建，随着任务的完成而解体。因而作为其核心功能的敏捷制造单元的调度问题也是不断变化的，并且具有以下特点[2]：复杂性、动态随机性、多目标。因此理论上求其解是非常困难的。
　　关于调度问题的研究主要有启发式方法、遗传算法、模拟退火算法、神经网络方法等。但由于敏捷制造单元调度问题是在动态变化的，使得由这些方法建立起来的数学模型也在不断的变化，因此在数学规划方法求解的时间和算法的健壮性等方面难以满足。近年来又有不少专家学者提出了基于多代理和合同网的单元调度方法[3，4]，该方法把敏捷制造单元调度模型看成是一种多代理协作模型，通过代理之间的合作及合同网的招投标协议完成生产任务的动态调度。但由于调度问题比较复杂，对于采用多代理招投标方式对任务进行资源调度，最终得到的调度结果是可行的解，并非最优解[5]。本文提出了一种基于多代理技术和混和遗传模拟退火算法的敏捷制造单元调度模型，来解决敏捷制造单元调度的复杂性，动态随机性和多目标等特性。
　　1　单元调度模型
　　敏捷制造单元的调度模型可以看作是一个多代理的协作模型，该模型的核心由一组制造资源代理和一组任务代理组成，并根据系统功能需要，引入管理代理，负责从生产计划系统接受生产任务，并负责根据工艺路线生成若干个任务代理，任务代理是可以动态生成和消亡的，能够随着任务的产生而产生，随着任务的完成而消亡。代理之间以一定的方式相互合作，来完成指定的加工任务。
　　为了便于描述问题，我们建立五元组{m，t，s，c，x}来表示敏捷制造单元调度模型。具体如下：
　　m={m1，m2，…，mm}表示制造资源代理的集合；
　　t={t1，t2，…，tn}表示加工任务的集合；
　　s是一个m×n矩阵，其元素sij表示在资源代理mi上任务tj的加工时间；
　　c是一个m×n矩阵，其元素cij表示在资源代理mi和mj之间的通讯时间；
　　x是一个m×n矩阵，其元素xij=1表示操作任务tj分配到资源代理mi上加工，否则xij=0；
　　目标函数：尽量保证各零件的工序操作时间和代理之间的通信时间之和最小。因此，目标函数可以表示为
　　约束条件：①机器约束，每一道工序加工只需要一种资源(设备)，
　　②一个设备在任何时刻只能加工一个零件(任务)，
　　③顺序约束，ti④时间约束，
　　(其中ｄi为零件的交货期)。
　　2　单元调度模型混合遗传模拟退火算法求解
　　2.1算法描述
　　由于遗传算法(ga)最佳个体保存选择算子会导致局部最优个体急速增加，进化有可能过早收敛，陷入局部最优解，而模拟退火法(sa)在搜索的过程中，能够随机地接受某些劣化解，因而具有较强的全局搜索能力，能够跳出局部极小点。故遗传算法与模拟退火算法的结合可以搜索整个空间，避免问题局部收敛。因此本文混合使用sa和ga来改善ga变异后的选择机制。下面是该算法的具体描述。
　　2.1.1　个体描述
　　文中用二维矩阵[xij]m×n表示个体，其中m表示资源代理的数量，n表示加工任务的数量。xij=1或者0，矩阵上每行非零元素表示资源代理上任务安排的情况，其从左到右的顺序表示任务在该资源代理上的加工顺序。矩阵每列有且仅有一个非零元素，表示安排任务生产的资源代理的情况。文中给出了一个6工件4工序，由4台加工机床组成的敏捷制造单元作业调度问题。随机生成一个任务分配矩阵集如表1所示。
　　表1任务分配矩阵
　　对于上述的任务分配矩阵我们采用一个[log2m]×n的二进制串表示，每[log2m]位称为一节，从左到右第i节表示任务ti所在的资源代理的情况。表1中的任务分配矩阵可以表示为
　　s=10　00　01　11　00　10　01　11　01　00　11　00　10　01　11　00　00　10　01　11　10　00　11　00。
　　因为有四个资源代理，所以两位一节，00，01，10，11分别表示任务被分配到资源代理m1，m2，m3和m4上执行。
　　2.1.2确定目标函数
　　2.1.3　遗传算子
　　(1)选择。选择算子是从上一代群体中选择较优秀的个体参与到繁殖下一代群体的行列中。本文采用“最优保存”策略与“转轮”相结合的方式产生子代种群。我们把上一代群体中适应值最大的10%的个体不进行复制，交换和变异三种操作，而直接进入到下一代群体中。另外90%的个体由“转轮”方法择出。“转轮”方式下个体复制的比例由适应度决定，即
　　(2)交叉。从整个任务分配方案集中以一定的百分比随机选出一个供交叉的子集，由于本文采用两位一节的编码方式，因此在进行交叉变异时，要考虑到编码的有效性及合理化问题。为了保证工序加工的顺序关系，两个染色体进行交叉的时候，从左右面每偶数位各随机选择一个基因，把这两个基因之间的基因组合看成是最佳个体，遗传给下一代。同理，匹配的染色体也应把相应的两个基因之间的基因组合遗传给下一代染色体，交叉这两个基因组合，完成交叉操作，实现遗传杂交。
　　(3)变异。以某个较小的概率选择一个子集进行变异，变异的方法有多种，可以对上述的二进制串的某些位直接取反，也可以互换一方案集中几个资源代理所处理的任务等方法。本文采用对二进制的某些位直接取反的方法，该种变异方法仅使其资源代理号增加或者减少1。
　　2.1.4评价
　　在本文的仿真实例中，设置初始温度为t0，tk=αtk-1，上标k表示第k次迭代，同时也指遗传算法中的第k代个体。在每一次极小化的步骤中，系统都会产生一个新的任务分配方案。计算新方案的目标函数f，并令δf=新方案之f3/旧方案之f。这时会出现两种情况：
　　(1)δf<0表示新方案优于旧方案，将新方案加入到新任务分配方案集中；
　　(2)δf>0表示原方案优于旧方案，此时计算概率值：prob=eｘp{-δf/b·tk}，这时b是玻尔兹曼常数，t是当前温度，k是迭代次数。由系统随机产生一个(0，1)上的随机数rand，如果prob>rand，则将新方案加入到新任务分配方案集中，如果prob
　　2.2基于多代理的制造单元调度算法流程
　　(1)初始化。随机产生一个任务分配矩阵集。先设定一个全零的任务分配矩阵x，然后在x中的每一列由系统随机产生一个元素1，保证每列有且仅有一个元素为1。xij=1或者0。确定初始群体规模ｎ=100，初始温度t0=1，温度调整系数α=0.9；
　　(2)迭代次数ｋ=1；
　　(3)按(1)式给定的目标函数，计算初始群体的所有个体的适应值；
　　(4)按适应值，取10%的个体直接复制到下一代中，其余个体按式(2)计算生存概率，由“转轮”方法择出，进入下一代群体中。
　　(5)产生下一代解群。选择两个任务分配集xi(k)　i=1，2，…，n，对xi(k)进行独立交叉随机变异，产生新的任务分配集x′i(k)，计算其适应值f′k。
　　(6)计算δf=f′i-fi，如果δf<0，接受x′i(k)，否则若概率eｘp{-δf/b·tk}>r，接受x′i(k)，若概率小于r，则保留原方案。
　　(7)如果k<最大迭代次数，k=k+1，降低温tk=αtk-1，重复步骤(3)～(6)。
　　(8)结束。
　　3应用实例
　　这里以一个已形成的敏捷制造单元为例说明基于多代理的，采用混和遗传模拟退火算法(saga)进行优化调度的求解过程及其调度结果。该单元拥有四台加工设备，编号分别用m1，m2，m3和m4来表示，因此制造单元代理集合可表示为{m1，m2，m3，m4}。加工工件集合为{p1，p2，p3，p4，p5，p6}，每个工件均由四道工序组成。工件的工艺计划表如表2所示。
　　表2　工艺计划表
　　仿真实例的群体规模ｎ=100，收敛判据ｋ=100代，交叉概率=0.9，变异概率=0.05。调整系数ｗ=1000，采用saga方法和ga方法的仿真结果见图1和图2所示(甘特图内的数字表示工序号，上面的数字表示工件号)。
　　图1　saga方法的甘特图　　图2　ga方法的调调度度甘特图
　　saga和ga的两种仿真结果的比较见表3(cpu时间表示得到最优解时在奔腾586上所需的时间)。
　　表3　saga和ga的比较结果
　　从仿真结果可以看出，通过混和遗传模拟退火算法saga得到的最优方案所需的加工时间以及代理之间通信时间的总和要小于单纯使用遗传算法ga得到的优化路线所需的时间，但是saga的收敛速度要劣于ga的收敛速度。此外由于本文将多代理技术引进到敏捷制造单元优化调度中，故系统具有动态调度的特点，能够及时响应外界环境的变化。如当有急件任务加入时，管理代理根据需要产生一个带有特殊标志的任务代理，并赋予它最高的优先权，资源代理识别到此标志后，不做任务排序，直接将该任务插到队列的最前面进行处理。而当某个设备损坏时，表现为资源代理的突然关闭，此时资源代理通知管理代理，由管理代理根据工艺路线重新选择可替代的资源代理，进行任务的重新分配和优化调度。由此可见该调度模型及其算法能够有效的解决敏捷制造单元的调度问题。
　　4　结论
　　(1)将多代理技术引入到敏捷制造单元中，面向一定的任务，通过代理的动态生成和消亡，系统能够快速重构，满足了敏捷制造环境下对敏捷制造单元的可重构、可扩展、可集成、可配置的要求。
　　(2)将sa与ga相结合，改进了ga的选择机制，不易陷入局部收敛，同时改善了ga的收敛性能，但是收敛速度较慢。
　　(3)应用实例表明，该方法调度性能良好，调度过程快，支持任务的随机加入，为制造企业快速有效的响应市场提高敏捷性提供了有力的理论与技术支持。
　　[参考文献]
　　[1]　彭观，傅勇辉，李春雄.敏捷制造环境下制造单元的控制研究[j].机床与液压，1999，(3)：9～11
　　[2]　张书亭，杨建军，邬学礼.敏捷制造执行系统的调度策略研究[j].机械设计与制造工程，2001，30(3)：40～42
　　[3]　sandholmt.animple mentation of the contract net prototal based on marginal costcalculation[a]. in：eleventh national conference on artificial intelligence[c]，jan，1993：256～262
　　[4]　石柯，李培根.基于多agent和合同网的敏捷制造单元调度[j].华中科技大学学报，2001，29(7)：32～34
　　[5]　韦文斌，杨建军，曾波.基于多代理的分布式车间控制系统的研究[j].机械设计与制造工程，2001，30(1)：28～30