基于直觉模糊集决策的多Agent敏捷车间调度

陈 曦，田文凯

(1.西安电子科技大学经济与管理学院，陕西西安 710126;2.西安电子科技大学数学与统计学院，陕西西安 710126)

车间调度策略是制造业研究的重点之一，近年来，随着供应网络的全球化及客户需求的不确定性发展，制造企业及其生产车间在车间调度的敏捷性方面有了更高的要求，“敏捷调度”已成为当前最主要的调度目标。敏捷调度的实质就是对迅速改变的市场需求和市场实际做出快速响应，通过一定的调度策略，选择、组织和管理各种制造性资源，完成复杂多变的车间加工任务，以获得最大的生产加工满意度和最优的客户满意度。

车间调度问题可分为静态调度问题和动态调度问题。对于静态调度问题，学者们已经提出了众多有效的启发式求解方法，主要有遗传算法［1］、粒子群算法［2］、模拟退火算法［3］、禁忌搜索［4］、蚁群算法［5］以及这些算法的混合算法等。而动态调度的研究在近几年也有了较新的发展，多代理技术［6］、人工智能技术［7］和模糊理论［8］便是其中比较重要的研究方案。然而，从现有文献可以发现，该方面的研究一般或侧重静态调度或侧重动态调度，在敏捷调度的研究上做得相对不足。为此，本文提出的敏捷车间调度方案，即是将静态调度与动态调度相结合，以多Agent系统作为敏捷制造的组织和运行模式，以新增一个紧急加工任务为例，研究了静态调度与基于直觉模糊集决策的合同网方法相结合的敏捷车间调度方案。

1 生产控制结构和调度方案

1.1 多Agent的敏捷调度生产控制结构

为满足敏捷调度的需求，根据制造车间的规模和任务需要，定义了3类基础Agent，即管理Agent、资源Agent和任务Agent，这3类Agent按照个体目标与系统全局目标相协调的原则，通过彼此间的协商和合作，共同完成工件的调度任务［9］。在分析的基础上，设计了如图1所示的多Agent敏捷调度生产控制结构。当加工任务到来时，产生任务Agent，一个加工任务对应一个任务Agent;管理Agent主要负责任务的整体调度和分配，对外其决定任务的接收，对内则安排任务的分配;资源Agent主要负责管理车间设备，记录各设备的加工能力状况，并为管理Agent的决策提供依据;各Agent也可以以临时任务为导向，组成动态的逻辑制造单元，通过彼此之间的合作来完成任务，任务完成后，则自行解散还原为松散结构［10］。

该结构中，管理Agent可以对全局数据库进行访问，数据库中包含有工件信息、设备信息和车间统计信息等。资源Agent与数据库相连，当资源发生变化时，数据库会自动更新，并将信息反馈给管理Agent，以便做出更好的决策。资源Agent对其下层资源Agent具有严格的控制与协调作用，如图1中资源Agent4控制其下层资源 Agent41、Agent42、Agent43，而资源 Agent1、Agent2、Agent3、Agent4、Agent5之间具有平等、合作的关系。

图1 多Agent敏捷调度控制结构

1.2 调度方案

在任务到来时，由管理Agent根据订单的交付时间、客户的重要性等因素来确定任务的优先级，优先级的确定与客户的重要性成正比，与交付时间成反比。管理Agent根据资源Agent提供的车间设备加工状况，对优先级高的任务优先分配资源。同时，任务Agent运用粒子群算法构造调度并将信息传递给相应的资源Agent，资源Agent将加工信息和机器状况等信息写入数据库，供管理Agent参考［11］。当生产任务发生变化或紧急情况下，整个系统通过基于直觉模糊集的合同网协议进行作业调度。

2 静态车间调度的粒子群优化算法

2.1 问题描述

敏捷车间调度属于典型的作业车间调度问题，作业车间调度问题研究n个工件在m台机器上的加工过程，确定所有工件在各机器上的加工次序、加工开始时间和完成时间等。下面是该问题的数学描述［12］

其中，i，j=1，2，…，n;h，k=1，2，…，m。式(1)是目标函数，即最小化最大完工时间;式(2)表示各工件操作的先后加工顺序以及加工各工件的机器的先后顺序。式中，cik和pik分别为工件i在机器k上的完工时间和加工时间，M是足够大的正数，aihk和xijk满足以下约束

2.2 粒子群算法设计

粒子群算法的具体流程如下［13］:

Step1初始化相关参数和种群。

Step2利用适应度函数对所有粒子进行评价，找出各子群内的最优解pbesti和总群体内的最优解gbest。

Step3对每一个粒子，根据式(3)计算速度向量，根据式(4)计算位置向量［14］

其中，pbesti代表当前代第i个粒子的历史最优位置;gbest表示当前代整个粒子群的历史最佳位置;w表示惯性权重;r1，r2是处于(0，1)之间的随机数;c1，c2是加速常数，一般取 c1=c2=2［15］。

Step4若某个粒子的当前适应度优于其历史适应度，则记当前适应度为历史最优适应度，同时记当前位置为该粒子历史最优位置。

Step5分别找出当前各子群和总群体的最优解，若该最优解优于历史最优解，则更新pbesti和gbest。

Step6迭代次数小于规定迭代次数，转Step3;否则，输出结果并结束。

3 基于直觉模糊集的合同网动态调度

3.1 合同网调度策略

合同网由一组可以互相发送消息的Agent组成，当一个Agent有任务需要其他Agent帮助解决时，就向其他Agent发出任务通告，即招标［16］;接到招标信息的Agent考虑自身的能力和当前状态，决定是否参与竞标，若参与则提交标书;最后由发出招标信息的Agent选出中标者并授予任务。整个过程按照市场中的招标—投标—中标机制来完成的。

敏捷车间调度的合同网模型将调度方案的生成和调整看作是管理Agent对资源Agent进行招投标及谈判协商，进而保证加工任务的合理分配与按期完成。在这种机制下，资源Agent为签约方，管理Agent为管理方，管理Agent接收任务Agent的请求进行招标，资源Agent进行投标，即加工设备之间通过相互竞争来获得加工任务。

考虑到在多属性决策时可能出现的“非此非彼”性，本文提出的合同网调度策略在合同网调度的基础上加入了直觉模糊集算法，利用隶属度与非隶属度来刻画模糊性，能够更加有效地处理车间调度中的不确定性，使得决策结果更加合理、可信和可用。

3.2 合同网调度流程

当车间内发生异常情况，例如有紧急加工任务插入时，将基于直觉模糊集的合同网调度策略表示为如下过程:由各任务Agent根据具体的作业情况发出投标请求;管理Agent接到从任务Agent传来的招标请求，将该招标请求发送给资源Agent，资源Agent考虑其设备加工能力和当前状态，对收到的招标请求做出是否参与投标的决定并提交标书;管理Agent收集相关的标书，运用基于直觉模糊集的多属性模糊决策模型对提交的标书进行评价，将加工任务承包给提供最佳标书的资源Agent;资源Agent选择适合的分派规则，对承包的加工任务进行局部调度［17］。

3.3 多属性模糊决策模型

在多个资源Agent中，如何选择一个能够同时满足一组属性的资源Agent，属于多属性的模糊决策问题。设资源 Agent集 X={x1，x2，…，xn}为决策方案集，C={c1，c2，…，cm}为属性集。在信息不完全确定的模糊环境下，直觉模糊集的μij和υij表示决策方案xj的第i个指标的评价值。其中，μij表示决策方案xj满足属性cj的程度，υij表示属性方案xj不满足属性cj的程度。

理想方案A+指100%满足决策者要求的候选方案，负理想方案A－指100%不满足决策者要求的候选方案，则［18］:对于直觉模糊理想方案

对于直觉模糊负理想方案

候选方案xj与直觉模糊理想方案A+、直觉模糊负理想方案A－的欧几里得距离［19］分别为

各候选方案的综合评价指数［19］为

为此，将直觉模糊集多属性决策的算法过程归纳如下:

Step1计算加权直觉模糊集决策矩阵。

Step2利用式(5)和式(6)确定直觉模糊集正、负理想解。

Step3利用式(7)和式(8)计算各方案与直觉模糊集正、负理想方案的欧几里得距离。

Step4通过式(9)计算各方案的综合评价指数ζj，由小到大对 ζj进行排序，ζj越大，所对应的方案越优，从而确定出各候选方案的优劣排序与最优方案。

4 实例分析

假设某工厂车间有6台加工机器A、B、C、D、E、F，同时加工6个工件，每个工件有6个工序。各工件不同工序加工时间如表1所示，加工机器如表2所示，以最小化最大流程时间作为调度目标。

表1 各工件不同工序的加工时间

表2 各工件不同工序的加工机器

对于首次到达的批量任务，利用上述数学优化模型建模，用粒子群算法求解调度计划。粒子群算法参数选取如下:种群规模为50，惯性权重w=0.729，学习因子c1=c2=2，最大速度vmax=0.01，最小速度vmin=－0.01，停止迭代阈值设为1e－25，最大迭代次数取为1 000。求解得到最优调度Gantt图如图2所示。

图2 最优解的调度Gantt图

由此可以确定工件在各机器上的加工顺序以及各工件的开始加工时间和完工时间，得出最优流程时间为55 min。执行上述调度方案进行加工，当时间为37 min时，插入新的紧急加工工件7，工件7的加工机器依次为 B、D、A、F、C、E，对应的加工时间依次为 4、6、6、7、3、5 min。

对于机器上已开始的加工继续执行直至加工完成，对于尚未进行的加工，即工件1在机器E、F上的加工，工件2在机器E、F上的加工，工件3在机器F上的加工，工件4在机器F上的加工，工件5在机器D、E、F上的加工，工件6在机器E、F上的加工，取消原调度方案，与新任务一起，采用基于直觉模糊集的合同网方法进行再调度。

已知直觉模糊集决策中的属性集为{设备状况c1，产品质量c2，技术水平c3}，运用粒子群算法计算得出新的3种调度方案x1、x2、x3，由管理Agent对这3种调度方案进行评价，得到直觉模糊集权重向量 w=(＜0.4，0.2＞，＜0.3，0.3＞，＜0.3，0.2＞)，直觉模糊集决策矩阵如表3所示。

表3 直觉模糊集决策矩阵

首先，计算加权直觉模糊集决策矩阵，结果如表4所示。

表4 加权直觉模糊集决策矩阵

接着计算直觉模糊集正理想解A+与直觉模糊集负理想解A－的直觉模糊集向量分别为A+=(＜0.32，0.28＞，＜0.21，0.44 ＞，＜0.18，0.28 ＞);A－=(＜0.16，0.52＞，＜0.12，0.65＞，＜0.15，0.52＞)。

然后计算方案x1、x2和x3与直觉模糊集正、负理想解的欧几里得距离分别为 D1+(x1，A+)=0.064，D+(x，A+)=0.204，D+(x，A+)=0.248，D－(x，223311A－)=0.280，D2－(x2，A－)=0.235，D3－(x3，A－)=0.126。各方案的综合评价指数为 ζ1=0.814，ζ2=0.535，ζ3=0.337。

由于 ζ1＞ζ2＞ ζ3，故方案 x1、x2和 x3的优劣排序为x1≻x2≻x3，从而最优调度方案是x1，对应的最优调度Gantt图如图3所示。

图3 新工件加入情况下的最优调度Gantt图

当插入新的紧急加工工件时，传统动态调度方法对全部加工任务均采用PSO算法进行调度。将传统动态调度方法与本文提出的敏捷车间调度方法进行敏捷性对比，仿真结果如表5所示。

表5 仿真结果对比

观察表5可知，运用本文提出的敏捷车间调度方法，工件1、3、4、5、7 交货期均达到完全满意，工件 2、6交货期满意度也较高。而运用传统动态调度方法，只有工件2交货期达到完全满意，工件1、4不能在交货期间完成。对比实验结果表明，本文提出的敏捷车间调度方法明显优于传统的调度方法。

5 结束语

本文针对敏捷制造模式的特点，建立了多Agent生产控制结构，该控制结构兼具Agent的自治性和阶梯结构的协调性。考虑到敏捷车间的动态特性和模糊性，研究了静态调度与动态调度相结合的敏捷车间调度策略，该调度策略能够对迅速改变的市场需求和市场实际做出快速响应，并做出最佳决策。最后，使用该方法进行了车间调度实例分析，结果表明本文提出的调度策略在敏捷车间调度问题的应用上是有效的。该调度策略还可进一步应用于物流企业配送车辆调度、虚拟供应链环境下的协同运作等问题中。

［1］Phanden R K，Jain A，Verma R.A genetic algorithm －based approach for job shop scheduling［J］.Journal of Manufacturing Technology Management，2012，23(7):937 －946.

［2］Li Junqing，Pan Yuxia.A hybrid discrete particle swarm optimization algorithm for solving fuzzy job shop scheduling prob-lem［J］.The International Journal of Advanced Manufacturing Technology，2013，66(1):583 －596.

［3］Rojas Santiago M，Damodaran P，Muthuswamy S，et al.Makespan minimization in a job shop with a BPM using simulated annealing［J］.The International Journal of Advanced Manufacturing Technology，2013，68(9 －12):2363 －2391.

［4］Nasiri M M，Kianfar F.A guided tabu search/path relinking algorithm for the job shop problem ［J］.The International Journal of Advanced Manufacturing Technology，2012，58(9):1105－1113.

［5］Korytkowski P，Rymaszewski S，Wisniewski T.Ant colony optimization for job shop scheduling using multi－attribute dispatching rules［J］.The International Journal of Advanced Manufacturing Technology，2013，67(1):231 －241.

［6］Nejad H T N，Sugimura N，Iwamura K，et al.Multi agent architecture for dynamic incremental process planning in the flexible manufacturing system ［J］.Journal of Intelligent Manufacturing，2010，21(4):487 －499.

［7］Cao Yan，Yabg Yanli，Wang Huamin，et al.Intelligent job shop scheduling based on MAS and integrated routing wasp algorithm and scheduling wasp algorithm［J］.Journal of Software，2009，4(5):487 －494.

［8］Deming Lei.Co － evolutionary genetic algorithm for fuzzy flexible job shop scheduling［J］.Applied Soft Computing Journal，2012，12(8):2237 －2245.

［9］Song Juan.An agile job shop scheduling system with hybrid control architecture［C］.China:Proceeding of 2004 Chinese Control and Decision Conference，2004:735 －781.

［10］李应，杨善林，郑加强.敏捷制造系统的基于Agent的混合调度［J］.系统仿真学报，2009，21(12):3763 －3767.

［11］张仁锋.基于蚁群算法的车间动态调度方法研究［D］.天津:河北工业大学，2008.

［12］Feng－Tse Lin.Constructing a job－shop scheduling model based on imprecise data［C］.USA:IEEE，The IEEE International Conference on Fuzzy Systems，2003:1374 －1379.

［13］谷峰，陈华平，卢冰原，等.粒子群算法在柔性工作车间调度中的应用［J］.系统工程，2005，23(9):20－23.

［14］Eberhart R C，Shi Y.Particle swarm optimisation:developments，applications and resources［C］.NJ:IEEE Press，Proceedings of the 2001 Congress on Evolutionary Computation Piscataway，2001:81 －86.

［15］张慧霞，张焱，高兴宝.求解作业车间调度问题的粒子群优化算法［J］.河南科技大学学报:自然科学报，2008，29(6):49－52.

［16］Li Ying，Zhang Jiaqiang，Yang Shanlin.Multi－ agent－ based fuzzy scheduling for shop floor［J］.The International Journal of Advanced Manufacturing Technology，2010(49):689 －695.

［17］王太江.基于多代理技术的敏捷车间无线调度系统研究［D］.重庆:重庆大学，2004.

［18］王毅，雷英杰，路艳丽.基于直觉模糊集的多属性模糊决策方法［J］.系统工程与电子技术，2007，29(12):2060 －2063.

［19］李登峰.直觉模糊集决策与对策分析方法［M］.北京:国防工业出版社，2012.