Multi-Agent技术在生产调度中的应用建模

2023-06-20 理论教育版权反馈

【摘要】：现今，multi-agent 应用在许多方面，特别是在对NP 问题的求解方面。基于multi-agent 技术，建立了半导体生产线实时动态调度模型。管理agent不干涉其他agent 的自主决策。协商协议包括了工件agent 与设备agent 之间进行协商所必须遵循的原则及相应的协商决策过程。设备agent 为协商主动方，工件agent 为协商被动方。

基于大规模生产的瓶颈分解原理，首先将生产线按照瓶颈分解方法思想，将整个生产线按照不同工序进行分解。每个站点有自己的加工设备与在制品WIP 区域(还未加工的在制品放置等待加工)。本书提出一种基于multi-agent 的半导体ATM 任务动态调度方法。首先建立了MAS 任务调度模型，其中包括总调度、放料、工件和设备4 种agent，分别代表生产线状态数据、投料计划、工件和设备；然后设计了工件agent 与设备agent 的动态调度协商规则，以工件最小加权延迟为决策指标，设备agent 分为单个Lot 加工批加工设备，分别考虑设计了其中的报价算法。此外，还考虑在突然停机发生情况下的协商机制。

基于multi-agent 的半导体生产线实时调度模型multi-agent 是分布式人工智能(DAI)研究的热点之一。每一个agent 都是一个小智能体，有着代理性、自制性、主动性、反应性、社会性、智能性、合作性和移动性等特点。每个agent 有自己的特性，也有自己的决策能力。这决定了当许多个agent 组成一个系统(multi-agent system)时，他们能够发挥各自的决策能力，从而解决复杂的问题。现今，multi-agent 应用在许多方面，特别是在对NP 问题的求解方面。

基于multi-agent 技术，建立了半导体生产线实时动态调度模型。该模型包括管理、投料、工件和设备4 种主要的agent，分别对应实际生产线的生产线状态数据、投料计划、工件和设备。由于运输设备和操作人员在实际生产线中一般是充足的，因此本书未加以考虑。 agent 之间关系如图6-4 所示。

pagenumber_ebook=129,pagenumber_book=120

图6-4　agent 关系图

总调度agent 不是实体agent，它负责把已经生成的调度方案转化为各个工件agent 和设备agent 的初始信息表，对现有的调度方案进行优化，作为调度时的启发因子。在工件开始加工时刻，相应的工件agent 的优先权尽量保持最大，才能增加设备agent 选中进行加工的概率。按照投料文件生成工件agent、按照工件完工信息终止相应的工件agent、管理系统中所有agent 的信息。管理agent不干涉其他agent 的自主决策。实际生产中，管理agent 对应的是生产线数据库中对调度管理有用的那一部分数据。

1. 投料agent

投料agent 用于控制半导体生产线的投料。投料agent 也为非实体agent，它负责通过管理agent 得到工件agent 的状态，进而控制投料的时间。实际生产中，对应投料计划。

2. 工件agent

工件agent 是半导体生产线上工件实体的代表，属于实体agent。 Lot 是半导体封装测试生产线制造执行系统中的基本单位，因此一个Lot 工件对应为一个工件agent。工件agent 带有此Lot 工件的所有信息，包括： Lot 编号、产品版本、加工数量、交货期、加工路径、产品类型、当前位置，等等。工件agent 与设备agent通过协商协议来实现重调度。

3. 设备agent

设备agent 是半导体生产线上设备实体的代表，同样属于实体agent。一个设备agent 代表设备群中一台设备。设备agent 带有此设备的信息，包括：设备号、类型、名称、加工能力、状态、最近加工产品类型、维护信息，等等。设备agent 通过判断自身状态，提供给工件agent 所需信息。按照设备类型不同，相应的设备agent也可分为单Lot 加工设备agent 和批加工设备agent，各自的最早加工时间的算法各不相同。

下面详细介绍工件agent 与设备agent 之间的协商协议。

协商协议包括了工件agent 与设备agent 之间进行协商所必须遵循的原则及相应的协商决策过程。设备agent 为协商主动方，工件agent 为协商被动方。由于单Lot 加工设备agent 和批加工设备agent 在加工能力上的不同，使得报价算法又有所差异，因此分别进行考虑。设备agent 与工件agent 之间的带有时间约束的单步协商协议的过程如图6-4 所示。

由于生产线上在生产运行后，资源大部分时间都是比服务对象要少，本书提出的协商策略就是基于公司招聘员工的思想，由设备agent 寻找优良的工件进行加工，根据工件的到达时间、紧急程度、产品种类进行筛选。首先，设备agent 向工件agent 发出任务招聘公告，公告主要包括设备agent 当前的状态，可加工的产品类型，已接收的工件agent 的信息，正在加工的产品信息或者刚刚完成的加工产品的信息，设备最早完工时间和当前等待加工工件的信息，以及要求应聘的工件agent 需要做出的响应的最后期限和达成协议的最后期限。设备agent 总是挑选工件加工优先权最高的工件进行加工。工件agent 接收到设备agent 任务招聘公告信息后，对自身情况按照要求做出评估进行报价，反馈给设备agent。报价中包括工件的产品种类，到达时间(可以计算出等待加工的时间)，紧急程度，也规定了设备agent 回复的最后期限以及最早可以开工的时间。设备agent 不停接收到达的工件，比较工件的产品类型，等待时间和紧急程度来进行动态时间排程。因此，每一个工件都能在加工同种类型的设备上找到自己的最早加工时间，从而计算出完成时间来择优选择设备进行加工。设备agent 一直做好准备接收工件agent 的回应，对收到的工件agent 做出评估，选择最合适的工件，并在该工件规定的时间内做出回复，向其发送接收通知信息，同时生成相应的合同文件。使用该协议能够很快得到协商的结果，并且可以进行多次协商，可以避免设备agent 没有选中优良工件agent的事件。如图6-5 所示。

协商决策模型。设备agent 协议决策模型主要包括两方面的内容：一是设备agent 发布的初始任务招聘信息；二是设备agent 评价工件agent 的报价信息。工件agent 的协商决策模型用于生成自己的反报价。

设备agent 的初始招聘信息由三部分组成：工件到达当前在制品等待加工区的时间，紧急程度，产品类型以及工件agent 回复的最后期限。首先选择优先权最高的工件进行排程。在相同紧急(优先权)情况下，设备agent j 的当前代加工工序k 的初始信息为：

pagenumber_ebook=131,pagenumber_book=122

pagenumber_ebook=132,pagenumber_book=123

图6-5　设备工件协调图

其中， pagenumber_ebook=132,pagenumber_book=123 为设备agent 要求工件agent 做出回应的最后期限。priorityj为紧急程度(优先权)， productdevice 为产品类型， Tcurrent 为当前时间，Tarrived 为工件到达时间。工件agent 的生成自己的反报价协商决策模型：

其中，aij 为工件agent 要求设备agent 做出回应的最后期限， Tcurrent为当前时间，∑RPTk 为在设备j 前排队列的工件与正在加工的工件共计完成的时间，RP pagenumber_ebook=132,pagenumber_book=123 为正在加工已经完成的时间。

单个工件agent 与加工设备agent 之间的协商机制及调度算法如图6-6 所示，图中的箭头表示相应步骤中信息的传递。

pagenumber_ebook=133,pagenumber_book=124

图6-6　混合Agent 协调图

对于封装测试生产线，有两种加工方式进行加工，一种是单个Lot(一个批次)加工，另一种是组批量加工方式，如环氧树脂固化、电性能测试等。两种方式的调度算法有所差别。对于批加工，还需做如下讨论。带有批加工设备的生产线动态调度主要是基于启发式规则的。对于批加工设备调度规则，既考虑了批加工设备本身的负载情况，又考虑了其下游设备的负载情况，还要考虑了上游设备的工件加工情况。下面主要探讨工件的批规则。

当批加工设备规则处于可用状态，就选择工件加工。组批工件不能超过最大加工能力。当缓冲区具有相同工艺的工件数超过最大加工批量时，要确定如何组批；当工件数小于最大加工量时，还要考虑正在上游设备加工的下一步加工将要使用此批量加工设备的工件或已经完成加工还没有到达缓冲区的工件。工件的组批实现方法如下：

(1)确定批加工设备对应的缓冲区中是否有紧急工件，如果有，则转至(2)，否则转至(3)；

(2)判断紧急工件agent 是否具有相同工艺。若存在多个相同工艺紧急工件agent，直接选出最紧急的工件组批，如果小于最大加工批量，检查是否还有使用相同工艺的紧急工件agent；

(3)判断批加工设备的上游设备加工或者刚完成加工下一步要使用批加工设备agent 的工件agent 是否为紧急工件，若存在，转至(4)，否则转至(5)；

(4)等待紧急工件agent 的到来，按照第(2)步组批加工优先级判断；

(5)判断批加工设备agent 的负载，如果该设备处于瓶颈，转至(6)，否则转至(7)；

(6)根据相同工艺的工件，按照等待加工时间的长短进行排队组批和优先级判断，不能超过设备agent 的最大加工能力；

(7)判断现有设备agent 是否处于空闲状态，判断下游设备是否处于空闲状态，如果是，转至(8)，否则暂时不组批，等待新工件的到来再开始组批；

(8)判断是否存在下一步加工要到下游空闲设备等待加工的工件agent，如果存在，转至(9)，否则等待新工件到来；

(9)在工艺相同的原则下，对多个零散工件agent 进行分组和优先级判断。