0 引言

混合流水车间(Hybrid Flow Shop, HFS)广泛存在于冶金、石化、制药等流程工业生产系统中, 其生产调度方法具有重要的研究意义^[1]。1988年, Gupta证明了HFS调度属于NP难问题^[2]。HFS调度问题根据调度环境可分为静态调度和动态调度, 静态环境下的调度可预先计划, 任务、加工时间、机器或其他资源在调度周期内都是确定的、可知的。而动态环境下的调度是反应性调度, 任务到达时间可能是随机的, 系统中存在随机的、不可预知事件。在以往的研究中, 研究的重心主要集中在静态调度问题上, Li等^[3]将邻域搜索算法与启发式算法结合, 提出利用全优化信息并避免搜索过程陷入局部最优的邻域变换方法。文献[4-5]研究了具有特殊约束的HFS调度问题。在动态调度方面, Lee^[6]应用多种调度规则对考虑工件动态到来的HFS问题进行了仿真研究。针对机器故障下的HFS重调度问题, 李铁克等^[7]从约束变化的角度建立了动态约束满足模型, 提出了基于局部修复的重调度算法。Kundakci等^[8]将遗传算法与启发式算法, 调度规则结合, 提出混合遗传算法用以解决作业车间动态调度问题。针对工件动态到来的混合流水车间环境, Rahmani等^[9]考虑了重调度方案与原始调度差异带来的成本, 结合前后方案一致度和加权拖期时间建立问题模型。

现有的解决HFS问题的方法大多都基于集中的模型, 全部的计算都在集中的模型中完成, 而将机器和工件只是看作被动接收计算结果的客体, 而非参与调度过程的实体。然而实际的生产系统又是离散的、分布式的、动态的和随机的, 因此现有的方法缺乏灵活性并且在发生意外事件时难以及时响应作出调整。

分布式系统能够通过高效的信息传递及合作来解决复杂、动态的调度问题。因此, 分布式调度系统, 尤其是多Agent系统(Multi-Agent System, MAS)已受到越来越多学者的关注, Kouider等^[10]针对作业车间调度问题开发了多Agent系统, 系统将问题分解为多个子问题, 并由具有各自目标和知识库的独立Agent来解决; Martin等^[11]提出了一种通用的多Agent分布式框架, 每个Agent集成特定的元启发式算法, 用以解决置换流水车间调度问题和车辆路径问题; 李应等^[12]提出结合动态逻辑制造单元结构的分布式多Agent控制结构，研究了结合模糊数学规划与模糊合同网的作业车间调度方案; Zhang^[13]将多Agent技术与蚁群优化算法相结合, 研究了在动态环境中的柔性作业车间调度问题。

尽管HFS调度是一类重要的车间调度问题，并且在实际生产中各类动态事件时有发生, 但在作者掌握的范围内, 尚未找到利用多Agent技术解决HFS动态调度问题的公开发表文献, 因此本文设计了基于多Agent的HFS动态调度系统, 系统能够处理在线调度、机器故障重调度以及订单插入重调度。

1 混合流水车间动态调度问题

为了便于描述, 记i为工件序号, i∈I={1, 2, …, n}; j为阶段序号, j∈J={1, 2, …, s}; m为机器编号, m={1, 2, …, m_j}; p_ij为第i个工件在第j阶段的加工时间; s_ij为工件i在第j阶段加工的开始时间; c_{i j}为工件i在第j阶段的完工时间, c_i0=0;在HFS问题中, n个工件在流水线上进行s个阶段的加工, 每个阶段有m_j≥1个同速机, 且至少其中一个阶段的并行机数量m_j>1。在某一阶段各机器对同一工件的加工时间可能不同, 工件要经过所有阶段的加工, 但对于某一阶段, 工件可在该阶段的任意一台机器上加工, 已知工件各道工序在各机器上的处理时间p_ij, 问题的目标是把工件i指派到阶段j的机器m上, 并对各机器上的指派工件进行排序, 即确定工件的指派方案和排序方案。并确定工件i在阶段j的开工时间s_ij和完工时间c_{i j}, 以最小化最大时间表长C_max。在本文的动态调度研究中, 考虑了三类常见的动态调度问题:在线调度、机器故障和订单插入。

1.1 在线调度

在经典调度问题中, 均是在已知所有作业信息的情况下进行调度, 即整个作业到达序列及每个作业的工时在调度时是已知的, 这被称为离线调度(off-line scheduling)。在线调度则是假设作业在未到来时其所有信息是未知的, 调度算法必须对每个到来的工件进行即时调度^[14]。对于在线调度, 主要考虑:

1) 初始时刻没有待加工工件, 工件随时间推移持续到来, 新订单在到来之前工件信息是未知的。

2) 订单到来的时间可能为生产开始时刻到结束前的任何时间, 新加入订单可能包含单个工件或者多个工件。

3) 以最小化Makespan作为调度目标。

1.2 机器故障

机器故障是实际生产过程中最常见的动态事件。本文在三元组FHs, ((PM^(k))_k=1^s)||C_max所表示的调度问题的基础上, 进一步考虑以下几点:

1) 机器空闲时不发生故障; 故障在执行加工的过程中随机发生, 持续时间为随机。

2) 被中断加工的工件必须重新加工。

3) 机器故障不仅会导致工件在机器故障发生之前对机器的占用时间失去意义, 并且机器需要占用时间来进行修复, 因此发生机器故障会导致Makespan增大, 重调度的目标是最小化Makespan。

1.3 订单插入

订单插入是指在初始调度执行的过程中有新的生产订单到来, 主要考虑:

1) 在初始时刻存在已知工件信息的若干待加工工件并且初始调度由MAS产生。订单在到来之前其包含的工件信息是未知的。

2) 订单加入的时间可能为生产开始时刻到结束前的任何时间, 新加入订单可能包含单个工件或者多个工件。

3) 新订单加入后的重调度目标是最小化Makespan。

2 基于MAS的调度系统 2.1 Agent模型

多Agent调度系统由管理Agent、策略Agent、工件Agent、机器Agent组成。系统结构如图 1表示。

2.1.1 管理Agent

管理Agent(Manage Agent, MA)由工件数据库、车间结构模块、黑板系统和调度管理模块构成, 管理Agent结构如图 2所示。

1) 工件数据库。在调度开始之前MAS的订单处理模块将已存在的订单所包含的所有工件信息记录在管理Agent的工件数据库中以便其他Agent在需要时查询工件相关信息。如果在生产的过程中有订单加入, 订单处理模块立即将新加入工件的信息记录在工件数据库。

2) 车间结构模块。该模块从工件数据库中读取所有工件的信息并从实际车间读取车间机器信息, 然后根据这些信息动态地生成与实际车间情况对应的工件Agent群和机器Agent群。

3) 黑板系统。即Agent之间交互通信所需的共享通信平台, 黑板系统存储各个Agent公共可见的动态数据, 如生产过程中机器的状态和释放时间、工件在各阶段的加工状态和释放时间等, 以便Agent在协调的过程中能够更加快速地查找所需的信息来求解自己的子问题。

4) 调度管理模块。其功能是在调度开始时激活所有Agent开始工作, 并且将所有机器的加工状态、当前加工工件及工件各阶段的开工和完工时间通过动态甘特图显示出来。

2.1.2 策略Agent

策略Agent(Strategy Agent, SA)是产生高效调度结果的核心一环。在生产开始或者发生动态事件时, 策略Agent会调用所选择的算法产生初始序列(在本文中, 将SA产生的工件序列称为Strategy序列), 随即工件Agent和机器Agent根据所产生的Strategy序列按照集成的行为逻辑进行协调并开始生产, 因此策略Agent产生排序方案的好坏直接影响了最终调度结果的质量。调度规则和启发式算法因为计算速度快、反应灵活, 被广泛用于解决调度问题, 因此本文将采用构造启发式算法指导SA的工件排序, 提出了一种针对混合流水车间环境的插值排序(HFS-aimed Interpolation Sorting, HIS)算法。除了HIS算法以外, SA也集成了NEH算法和多种调度规则作为产生Strategy序列的可选算法。

2.1.3 工件Agent

工件Agent(Job Agent, JA)是由管理Agent根据已到来的工件动态生成的, 每个工件对应一个JA, JA由数据模块、状态显示模块和行为模块组成, 如图 3所示。

1) 数据模块记录两部分数据：一部分是静态数据, 另一部分是生产中产生的动态数据。静态数据包括:工件的序号、各阶段的加工时间等信息。动态数据包括:工件的优先值、各阶段开工完工时间、各阶段分配机器、各阶段加工状态等。这些数据同样作为管理Agent中的黑板系统中的公用数据, 以便其他Agent能够快速查询到所需的信息。

2) 状态显示模块用状态图的形式显示出工件当前所处状态。

3) 行为模块集成了JA与其他Agent的协调逻辑。

2.1.4 机器Agent

机器Agent, 也称为资源Agent(Resource Agent, RA)是由管理Agent根据读取的实际车间信息而生成。每台机器对应一个RA。与JA相似, RA由数据模块、状态显示模块和行为模块构成, 如图 3所示, 但其中内容有所不同。

1) 数据模块中的静态数据包括:机器序号、机器类型; 动态数据包括:机器释放时间、已安排在机器上加工的工件和机器当前状态。这些数据同样作为黑板系统里的公用数据。

2) 状态显示模块用状态图的形式来显示机器当前的状态。

3) 行为模块集成RA与其他Agent的协调逻辑。

2.2 Agent间协调机制

HFS动态调度系统的四类Agent间协调机制如图 4所示, 具体描述如下:

1) 初始调度的生成与交互:调度开始时, SA调用指定的算法或者调度规则产生初始序列, 在本文中将SA产生的工件序列称为Strategy序列。SA在产生Strategy序列之后将通知MA, MA根据工件在Strategy序列中的位置, 对各JA赋予相应的优先值(在Strategy序列中靠前的工件优先值更大), 并通知RA和JA生产开始。

2) 在生产开始后每个RA和JA分别独立进行工作, 二者的协调机制如下:

生产开始时, 所有待加工工件都释放到第一阶段, 所有机器初始释放时间都为0。对于每个JA, 当工件释放时, 就请求安排到释放时间最早的空闲机器上。

当RA接收到JA的安排请求时, 如果同时只接到一个JA发出的请求, 则立即安排对应工件进行加工; 否则如果接收到多个JA同时发出的安置请求, 则选择其中优先值最大的工件安排加工, 并向被选择工件发送消息通知请求被接受, 对另外的工件则通知其请求被拒绝。

当JA接收到拒绝通知时, 则重新查询空闲机器, 如果有则向其RA发送安置请求。

每当有机器释放时, RA去查询当前已经释放到机器对应阶段但还未开始加工的等待工件, 如果有则安排其中优先值最大的工件开始加工。

每当工件完成一阶段的加工时就立即释放到下一阶段, 同时JA向下一阶段的机器发送安置请求, 直到所有阶段完成, 该工件完成加工。直到所有工件完成加工生产结束。

3 动态调度策略与算法

如2.1.2节中对策略Agent调度思想的描述, 本文提出的重调度方法在发生动态事件时, 只根据当前车间的状态调用插值排序算法HIS重新产生Strategy序列。在重新生成Strategy序列之后, 所有JA和MA能立即根据新的Strategy序列按照预先设定的协调机制继续进行工作。也就是说, 在重调度时不需要改变JA和MA之间的协调机制, 只需要SA调用HIS算法重新产生Strategy序列。因此, 即使在系统中存在多种动态事件, 或有动态事件多次连续发生的情况下, MAS系统都可以迅速地进行重调度并保证生产即刻继续进行, 具有较好的适应性和灵活性。本章将针对动态环境特征, 设计机器故障和订单插入的调度策略, 并给出HIS算法。

3.1 机器故障处理策略

当故障发生时, 故障机器RA更新机器信息:将其状态标为故障, 将中断工件从已安排工件队列中删除, 更新释放时间为当前时刻加上故障修复时间。随即向该工件JA发送故障消息, 当中断工件JA收到故障消息时, 更新工件信息, 该工件重新释放到故障阶段。管理Agent查询此时在第一阶段中所有已释放但未开始加工工件, 如果超过一个则调用HIS算法重新产生Strategy序列，否则Strategy序列不变。在策略Agent调用算法产生新的Strategy序列之后通知MA, MA根据新队列通知各JA更新优先值, 并通知所有JA和RA继续工作。处理过程各Agent的协调机制如图 5所示。

3.2 新订单加入的处理策略

当生产的过程中有订单插入或者当在线调度订单到来时, 到来工件立刻释放到第一阶段, 管理Agent查询此时在第一阶段中已释放未加工工件, 如果有两个或以上则通知策略Agent调用HIS算法重新产生Strategy序列。策略Agent产生新的Strategy序列之后通知MA, MA根据新队列通知各JA更新优先值, 并通知所有JA和RA继续进行工作。处理过程各Agent的协调机制如图 6所示。

3.3 HIS算法

调度规则和启发式算法因为计算速度快、反应灵活, 被广泛用于解决调度问题。目前, 已有多位学者对混合流水车间下的多种构造启发式算法进行了比较研究。文献[15]研究了5种Flowshop的启发式算法运用于HFS问题以期最小化Makespan和Mean Flow Time, 结果表明NEH算法在所有指标上更优；文献[16]以最小化Makespan和拖期时间为目标研究了5种启发式算法和多种调度规则在HFS问题中的应用, 结果同样表明NEH法的表现明显优于其他算法。为了能在敏捷生产要求下产生良好的调度效果, 本文针对混合流水车间环境, 基于NEH算法的设计思路, 提出了HIS算法。

3.3.1 主算法——插值排序法

与NEH相似, HIS算法同样对所有待安排加工工件进行迭代插入并计算C_max, 最终将所有工件插入后形成Strategy序列。区别在于, NEH针对置换流水车间的环境计算C_max, 并且只用于静态调度; HIS则针对混合流水车间环境, 考虑了在多Agent系统的协调机制下的机器分配机制和机器上的工件排序机制。根据Strategy序列, 按照多Agent系统协调机制下的机器分配策略和机器上的工件排序策略, 产生工件的分配和在机器上的排序, 在工件的分配和排序确定后, Strategy序列对应的C_max就被确定下来。并且在进行动态调度时, HIS算法将考虑当前车间的加工状态——即在各工件和机器当前加工状态的基础上, 根据Strategy序列对当前尚未开始加工的工件进行机器分配和排序, 进而计算出Strategy序列对应的C_max。因此, HIS算法能有效地解决动态环境下的混合流水车间调度问题, 同时也很容易扩展到静态调度问题。

HIS算法表述如下:

Step1  将所有当前在第一阶段已安排加工的工件按开工时间s_i1由小到大排列建立序列Q₁(如果几个工件s_i1相同则按其优先值排列先后顺序), 将所有当前在第一阶段尚未安排加工的工件按各阶段总加工时长$ \sum\limits_{j = 1}^s {{p_{ij}}} $从大到小排序建立序列Q′₂。对于初始调度时, 显然Q₁为空。

Step2  对Q′₂中的前两个工件(设它们为i₁和i₂), 将i₁、i₂按不同顺序放入Q₁之后形成序列{Q₁, i₁, i₂}以及{Q₁, i₂, i₁}, 随后算出若Q₁、i₁、i₂为全部工件, 分别以这两个序列作为Strategy序列, 在多代理的协调机制下, 根据Strategy序列确定工件指派方案和各机器上的工件排序方案, 进而得到C_max。选择更优C_max对应的队列。

Step3  将Q′₂中第k个(k=3, 4, …, |Q′₂|)工件分别插入Q₁后的k个可能的位置, 选择最优C_max对应的序列, 直到Q′₂最后一个工件插入完毕并建立序列{Q₁, Q₂}, 此序列即为HIS产生的Strategy序列。产生Strategy队列中前部分Q₁决定的是已经在第一阶段开始加工工件在接下来的阶段的优先顺序, 后部分Q₂决定的是已在第一阶段已释放但未安排加工的工件在第一阶段安排的优先顺序。

3.3.2 机器分配及排序子算法

HIS算法针对混合流水车间各阶段的多机环境, 在Strategy序列确定后, 按照多Agent系统的机器分配机制和机器上的工件排序机制将工件分配到机器上, 一旦工件的机器分配和排序确定, Strategy序列对应的Makespan就确定下来。

机器分配机制和机器上的工件排序机制的调度思想如下。

对于工件:

IF(工件在释放时如果有空闲机器)

THEN请求安排到释放时间最小的空闲机器上;

ELSE加入等待队列;

IF(工件被拒绝安排到机器上)

THEN

{IF(此时还有空闲机器)

  THEN请求安排到释放时间最小的空闲机器上;

  ELSE加入等待队列;

}

对于机器:

IF(有工件请求安排到机器上)

THEN

{ IF(接收到的是单个工件请求)

  THEN将工件安排到机器上;

  ELSE选择优先值最大的工件安排加工, 拒绝其他工件的请求;

}

IF(机器释放)

THEN

{ IF(等待队列不为空)

  THEN从等待队列选择优先值最大的工件安排加工;

具体步骤为:

Step1  初始化。读取所有工件在各阶段的加工状态, 对于j=1, 2, …, s建立在阶段j尚未安排加工的工件的集合C_j, 定义c_{i, j-1}为工件j阶段的释放时间, 对于j=2, 3, …, s, 如果工件i在j-1阶段已安排加工则读取c_{i, j-1}, 对于j=1, 对于所有在初始调度时已存在工件在阶段j的释放时间c_i0=0。令阶段数j=1。

Step2  若此时${C_j} \ne \emptyset $, 则

1) 找到此阶段释放时间最小的机器m, 记录其释放时间t_m。

2) 查看所有工件在j阶段的释放时间即c_{i, j-1}, 若对于所有工件有c_{i, j-1}>t_m，即如果在机器释放时所有工件尚未释放, 则转到3);否则转到4)。

3) 选择c_{i, j-1}最小的工件i, 如有多个工件c_{i, j-1}相同, 则根据在Strategy序列中的相对位置选择优先值最大的工件(Strategy序列中靠前的工件优先值更大)设其为i, 将i安排到机器m上, 更新工件的此阶段完工时间即令c_{i j}=c_{i, j-1}+p_ij, 更新机器释放时间t_m=c_{i, j-1}+p_ij, 将工件i从C_j中删除。

4) 若只有一个工件满足c_{i, j-1}≤t_m, 即在机器释放时只有一个工件i已释放, 则将此工件安排到机器上, 更新工件此阶段的完工时间c_{i j}, 更新机器的释放时间t_m, 将工件i从C_j中删除; 否则若有多个工件满足c_{i, j-1}≤t_m, 即在机器释放时有多个工件已释放, 则根据Strategy序列选择优先值最大的工件i安排到机器上, 更新工件此阶段的完工时间c_{i j}, 更新机器释放时间t_m, 将工件从未安排集合C_j中删除。

5) 若$ {C_j} \ne \emptyset $则转到1);否则转到Step3。

Step3  若此时j=s, 则转到Step4;否则j= j+1并转到Step2。

Step4  检查所有工件在最后一阶段完工时间c_is, 最大值即为此Strategy序列对应的C_max。

4 仿真实验

采用Anylogic7.3.6作为多智体(multi-Agent)建模工具。实验环境为CPU Intel Core I5 CPU @ 2.20 GHz/RAM 8 GB。

4.1 在线调度

在线调度的仿真中, 仿真了不同的工件到来频率下和不同工件总数的在线调度, 工件在各阶段的加工时间p_ij∈[5, 30], 共5个阶段, 每个阶段有3台同速并行机, 0时刻到达10个工件, 第一组测试随后每隔20个时间单位到达10个工件; 第二组随后每隔30个时间单位达到10个工件。两组测试分别仿真了总共到来100个工件和共到来200个工件的情况。策略Agent分别选择HIS算法以及常用的调度规则产生Strategy序列, 随后工件Agent和机器Agent根据Stretegy序列进行协调并完成生产, 对比各自对应的最大完工时间C_max, 参与对比的调度规则包括:最短加工时间优先(Shortest Processing Time first, SPT)、最长加工时间优先(Longest Processing Time first, LPT)、最大剩余加工时长优先(Most Work Remaining First, MWRF)、最小剩余加工时长优先(Least Work Remaining First, LWRF)、最大总加工时长优先(Most Total Work First, MTWF)、最小总加工时长优先(Least Total Work First, LTWF)。实验结果如表 1所示。

仿真结果表明, 在两种不同的订单到来频率下, 在不同数量工件的情况下, 本文提出的多Agent调度系统, 能够迅速地在订单到来之时及时对未安排加工的工件进行重调度, 实验结果表明在HIS算法产生排序方案的基础上最终的C_max明显优于其他调度规则产生的排序方案的基础上完成加工的C_max。

4.2 故障重调度

在故障重调度的仿真中, 工件数量为20个, 共计3个阶段, 每个阶段有3台同速机, 工件在各阶段的加工时间服从均匀分布, p_ij∈[5, 30], 在调度开始时, 策略Agent调用HIS算法产生静态调度下的Strategy序列, 随后所有工件Agent和机器Agent根据Strategy序列进行协调并开始生产。故障随机产生, 故障参数如表 2所示。

同时将调度规则与HIS算法进行重调度结果对比。运用调度规则进行重调度时, 在发生故障后根据选择调度规则赋予工件在各阶段的优先值, 各Agent根据优先值进行协调并完成加工。

根据故障参数产生实验算例, 共进行20次故障重调度仿真。故障发生阶段、发生时间、持续时间、中断前工件已加工时间如表 3所示, 初始调度C_max、调用HIS算法及调度规则重调度后的C_max如表 4所示。在多代理调度系统的生产过程中发生故障的即时重调度机制下, 能够在故障发生时迅速重新计算Strategy队列, 各Agent根据新的Strategy队列能够立刻重新开始协调工作并且使生产得以继续进行。在20次实验中仿真结果表明在多Agent调度系统下, 调用HIS算法产生新的Strategy序列并根据新序列完成重调度, 初始调度和重调度C_max的时间相似度为97.6%, 实验结果表明HIS算法的调度效果优于调度规则, 能够很大程度消除故障对于最大完工时间的影响。图 7为算例3故障前后的甘特图, 其中:图 7(a)是调用HIS算法形成的初始调度甘特图, 初始调度Makespan为155;图 7(b)是在初始调度基础上, 在阶段2发生故障时调用HIS算法进行重调度后的甘特图, 其中故障发生时间为26, 持续时间为12, 机器发生故障前已加工时间为19, 重调度后Makespan为156。

4.3 订单插入动态调度

在订单插入动态调度仿真中, 工件数量为20, 阶段数为3, 工件加工时间服从均匀分布p_ij∈[5, 30], 插入订单到来时间T=U[0.1, 0.9]* C_max, 插入订单包含工件数量为随机1~5。为了对比HIS算法的重调度效果, 将HIS算法与调度规则进行对比实验。订单插入发生后, 在调用HIS算法重调度时, 会产生新的Strategy序列, 随后各Agent根据产生的序列继续协调并完成生产。在调用调度规则进行重调度时, 根据所选择的调度规则赋予工件在各阶段的优先值, 随后各Agent根据工件优先值进行协调并完成生产。实验结果如表 5所示, 算例7插单前以及插单后用两种方法进行重调度甘特图对比如图 8所示。

图 8中：图 8(a)为初始调度甘特图；图 8(b)为初始调度基础上在t=22时刻插入工件j₂₀、j₂₁、j₂₂, 调用HIS算法重调度形成的甘特图, Makespan为167；图 8(c)为在订单插入后将新到工件插入到Strategy序列末尾, 即运用先进先出(First In First Out, FIFO)规则完成加工后的甘特图, Makespan为178。

5 结语

大多数现有的解决HFS问题的算法都集中于模型, 所有的计算都集中在模型完成, 将机器和工件当作接受调度结果的客体, 缺乏灵活性。本文设计了基于Agent的混合流水车间调度系统, 设计了各Agent之间的协调机制, 从而将工件和机器视为参与调度过程的实体。基于NEH算法的设计思路, 针对混合流水车间问题以及动态调度问题的特点, 提出了系统的核心算法(HIS), 该算法适用于静态调度和多种动态调度问题。在发生动态事件时, 系统能迅速根据当前车间中机器和工件的加工状态由策略Agent调用HIS算法产生新的排序方案, 根据新的排序方案, 工件Agent和机器Agent能即刻继续协调工作以完成工件在机器上的分配和排序。最终仿真结果表明, 此MAS产生的调度效果比多种调度规则更优, 能够适应多种动态事件同时并存的动态生产环境。