基于MAS的机加工车间动态调度研究

涂晶鑫

摘要：在当今的制造环境下，大多数企业多为分布式制造，所以在研究分布式车间调度已然当今调度领域的热点。本文拟通过研究单机调度的情况，引入分布式调度的核心——MAS（Multi-agent system）。面向任务建立了基于MAS的调度控制系统模型。采用分布式调度将整个车间的调度问题分解成一系列的子调度问题，并将这一系列的子调度问题集成到拍卖机制中，满足了现代制造系统对复杂性的要求。最后以经典的调度问题验证了此方法的有效性。

Abstract： In today's manufacturing environment， most enterprises are distributed manufacturing， so the study of Distributed Shop scheduling has become a hot spot in the field of scheduling. This paper introduces the core ——MAS （Multi-agent system） of distributed scheduling by studying the single machine scheduling. A scheduling control system model based on MAS is established for tasks. The scheduling problem of the whole workshop is decomposed into a series of sub scheduling problems by distributed scheduling， and this series of sub scheduling problems are integrated into the auction mechanism to meet the requirements of the complexity of the modern manufacturing system. Finally， the effectiveness of this method is verified by the classical scheduling problem.

关键词：分布式车间调度；MAS；agent；拍卖机制

Key words： distributed job shop scheduling；MAS；agent；auction mechanism

中图分类号：TH164 文献标识码：A 文章编号：1006-4311（2018）33-0274-03

0 引言

在复杂、多变的生产制造环境中，生产扰动的随机性往往会影响车间生产的正常运行，生产调度人员需结合实时工况有针对性地制定解决方案，因此如何快速智能的解决生产扰动事件、恢复生产系统稳定性是车间智能调度问题的研究重点。目前，关于智能调度系统的研究，国内外学者进行了大量的研究，SNOO[1]和MIKKEL[2]等人通过建立不确定性因素的可靠性评价模型来评估扰动事件的影响程度，并根据评估结果结合调度阈值来确定重调度方法，但这种方法依赖于人的主观性，会导致评估结果的不准确；何伟[3]和喻明让[4]等人考虑设置调整时间，依据扰动事件发生的概率分布，实现车间调度与预防性维修的集成来达到预防目的，但是这样会造成前期成本投入高以及工件加工时间增加等问题；刘爱军[5]和李平[6]等人基于事件和周期驱动的混合调度策略，建立了自适应重调度框架，虽然这些方法得到的结果能够为实时解决智能调度问题提供一定的参考，达到智能响应扰动的目的，但仍存在以下不足：

①生产扰动事件具有很强的随机性和动态性，不断变化的动态生产环境，给调度人员在生产调度模型修订时带来极大困难，有时甚至不可能；而且模型过于简单、方法过于单一、适用范围狭窄。②随着求解问题的规模变大，寻求最优解的计算量呈指数增长，使得一些常规优化方法难以凑效，求解效率不高，陷入局部最优的问题。为了解决上述问题，提出了MAS（Multi-agent system）。它的基本思想是把大的复杂系统转化成小的、可以实现相互通信的、能够彼此协调工作的自治系统，逐渐的把生产调度系统由传统的集中式转化为分布式，以便于解决生产调度管理系统具有开放性，分布性。

1 MAS的结构特点与调度系统框架

1.1 单一agent的结构特点 图1所示的为单一agent的结构示意图，每一个agent都包括了知识库，推理决策工具和通讯功能模块。单一的agent有如下的特点：①尽可能使局部获得最大的利益，可以不考慮整体的目标。②单一agent可以使用通讯功能模块与其他的agent进行沟通。

1.2 0MAS的结构特点 虽然单一agent的功能定义具有特定的功能，可以很好地嵌入到调度系统中去，但是在现在中复杂的问题，只靠单个的agent是无法解决的，甚至是无法描述。如图2所示，为了很好地利用agent的特定的功能，因此，一个应用系统中往往包含了多个单一的agent，这些单一的agent不仅仅具有自己可以解决问题的能力，还可以通过相互协调通信，从局部最优达到最优，完成共同的目标。这样的系统称之为MAS（Multi-agent System）。

1.3 MAS的调度系统框架 如图3所示，MAS的调度系统一般由三个agent组成，分别为车间调度agent，任务agent和车间资源agent。当有扰动发生时，任务agent便会收到任务，与其他两个agent进行交互和合作，共同完成调度任务，最后输出调度结果。

2 基于MAS的单机调度问题问题描述与模型建立

本文采用0-1整数规划进行建模，传统的单机调度模型通过0-1整数规划构建是一个典型的集中式的模型，那么基于MAS的单机调度模型构建应该是一个分布式模型，把工件agent分开代表每一个工件。

则需要满足如下假设：

①工件的优先级相同。

②在t=0时刻所有的工件都可以被加工。

③忽略在加工过程中的扰动因素，加工一旦开始无法中断。

由以上可以数学模型可以看着这是一个典型的0-1整数规划模型。为了把MAS的模型引入其中，则本文将原先的集中式的建模进行分解为多个单一的agent，即每个工件和机器分别代表工件agent和机器agent。在分解数学模型下，我们必须要保障分解之后的数学模型必须要有意义，因为单一agent结构要求必须将交织的数据和约束关系分解到各个独立的agent中，而单一的agent又必须具有一定的交互能力，这样才有可能达到全局最优。

故本文采用拉格朗日松弛法去分解0-1整数规划模型：

每一个工件都有独立的数学模型。

针对单机作业问题的机器agent，？姿k作为违反机器能力约束的惩罚项并不是一个常数，反而？姿k的值是由每个工件的完工时间确定的，有两个及两个以上的工件需要同一段时间进行加工时，？姿k的值就会变大。为了得到可行的调度方案，需要最大化惩罚项来约束机器的能力。那么机器agent的目标函数表示为：

在这里，就已经完成了对集中式的数学模型进行了分解，得到了每个工件agent和机器agent的0-1数学规划模型。

3 数学模型的解答流程

3.1 确定模型的迭代方向

在不断的迭代的过程中，每迭代一次都在向最优解不断的靠近，则迭代的方向选择正确那么可以大大的加快收敛速度，本文采用的是常见的最速下降法，则它的搜索方向为负梯度方向。由推论可得：

3.2 确定模型的迭代步长

步长设计只要满足他提出的设计要求，基本是可以满足求解的收敛性，在实际中常用的步长计算公式为：

在上述公式中，Zup（t）是原问题的一个上界。Zlb（t）是原问题的下界。βc的取值一般为：0≤βc≤2。一般在初始化时，取β0=2。当M（？姿）的值上升时，βc不变。为了计算简单，在文中把原问题的上下界用前后两次的迭代值代替。

3.3 确定模型的收敛条件

在确定了迭代方向和迭代步长之后，需要确定迭代停止的条件，也就是收敛条件，在实际运算中，设定迭代的停止条件为：当迭代过程中，前后两次迭代的差小于一个极小的常数，则认为M（？姿）已经收敛，迭代结束。

其中，μ是一个极小的常数。

4 实例验证

整个调度时域是20个时间单位。所有的工件在时刻0时都可以开始加工。目标函数为完工成本最小。假设每个工件的完工成本是由加工成本还有提前和拖期完工的惩罚组成。（为了方便计算，则每个工件在机器上加工的成本一般是固定的，故完工成本只由加工成本进行衡量）每个工件的参数如表1所示。

计算第一轮出价，在机器没有开始任何加工任务时，所以机器把1-20个时刻都作为拍卖品发起拍卖。在开始拍卖时，每个工件agent为了自己的完工成本最低，故此次在第一个时刻，惩罚值为0，经过求解，出价表如表2所示：图4为3个工件出价的甘特图。

从甘特图中可以看到，这三个工件的加工需求时间有重叠，则在这段时间内，工件agent的模型得到的出价违反了机器能力约束，在机器在下次拍卖的迭代过程中会提高发生冲突时间段的机器价格，以便于消除冲突。

在后续的迭代中，在经历的c=68时，目标函数收敛，形成了良好的调度方案，用图5表示在68次出价之后的甘特图；得到出价表如表3。

为了验证基于MAS的调度算法的求解质量，让本文的求解结果与一些常用的调度规则在次问题的结果上做一些对比。

5 结果分析

从以上的结果中可以看出来，基于MAS的分布式调度有能力去更好的解决这些调度问题，在求解质量上要比这些常用规则的结果要高出27%。该实验可以说明了基于MAS的分布式调度有一定的可行性。但是目前仅仅只做到了基本的单机调度问题，所以在后续的研究中，会逐渐把车间的复杂程度加大，进行更为复杂的研究。

参考文献：

[1]SNOO C DE， WEZEL W V， WORTMANN J C， et al. Coordination activities of human planners during rescheduling： case analysis and event handling procedure[J]. International Journal of Production Research， 2011， 49（7）： 2101-2122.

[2]MIKKEL T， JENSEN. Robust and flexible scheduling with evolutionary computation[D]. PhD Dissertation， Department of Computer Science University of Aarhus， 2001， Denmark.

[3]He W， Sun D H. Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies[J]. International Journal of Advanced Manufacturing Technology， 2013， 66（1-4）：501-514.

[4]喻明讓，张英杰，陈琨.考虑调整时间的作业车间调度与预防性维修集成方法[J].西安交通大学学报，2015，49（6）：16-21.

[5]刘爱军，杨育，邢青松，陆惠，张煜东，周振宇，吴光辉，赵小华.柔性作业车间多目标动态调度[J].计算机集成制造系统，2011，17（12）：2629-2637.

[6]李平，唐秋华，夏绪辉，陈平和.基于双层遗传编码的柔性作业车间自适应重调度研究[J].中国机械工程，2013，24（16）：2195-2201.