基于多Agent的板坯出/入库协同调度系统

张琦琪,刘 鹏,张 涛

(1.上海财经大学信息管理与工程学院,上海200433;2.上海科学技术职业学院,上海201800)

基于多Agent的板坯出/入库协同调度系统

张琦琪1,2,刘 鹏1,张 涛1

(1.上海财经大学信息管理与工程学院,上海200433;2.上海科学技术职业学院,上海201800)

针对板坯库管理中的协同运输问题,以最小化板坯出/入库总运输时间为目标,建立数学模型。构建一个包括出库板坯、入库板坯、行车和台车等在内的板坯出/入库协同调度无主控多Agent系统,以统一的结构封装任务和资源,同时考虑板坯入库作业和出库作业2种任务,提出在Agent之间建立投标/仲裁机制,设计评价函数协调Agent之间的资源冲突,提高系统的柔性、并行性和自适应能力。通过系统仿真,将出/入库协同作业、完全出库作业和完全入库作业3种场景进行比较。实验结果表明,出/入库协同管理系统可有效提高板坯库的运输吞吐率,且在投标/仲裁机制的协商作用下,运输设备利用率也显著提高且保持均衡。

板坯出/入库协同调度;多Agent系统;黑板模型;投标/仲裁机制;协同运输;系统仿真

1 概述

钢铁企业中的板坯库处于上游工序(连铸)与下游工序(热轧)之间,板坯出/入库管理一方面需要缓冲来自上游连铸工序的板坯进行入库运输作业;另一方面,还要根据下游热轧生产的需求,对已经存放在库中的板坯进行出库运输作业。在实际操作中,考虑到人工经验和操作灵活性,多采用出库与入库分时段静态作业的方式;另外,出库作业还受到热轧工序批次的影响,作业随时间分布不均匀,这些因素大大增加了板坯库内设备空载等待时间。因此,如何使库中的大型运输设备(辊道、行车和台车等)得以合理利用、动态配置,实现出/入库协同,是提高板坯库物流系统运作效率、确保上下游工序协调性的关键所在。

目前,关于板坯库的研究多聚焦于入库决策[1]或出库决策[2-3]的制定,涉及库内运输问题的研究很少。但在集装箱码头装/卸货协同运输的相关研究中,文献[4]同时考虑装/卸过程,研究了集卡运输路线及数量配备问题。文献[5]针对集卡运输,建立以等待时间和运输时间加权和最小为目标的模型并求解。文献[6]构建集装箱码头整体作业仿真系统,研究动态集卡配置对装/卸作业的影响。这些研究为本文同时兼顾出/入库2种运输任务提供了很好的理论或实践支持。然而,板坯出/入库调度是在运输空间和位移方式都受限的情况下,研究多种设备协同运输的问题,系统运行时存在并行、协调、竞争等多种关系,这使板坯出/入库协同调度问题变得十分复杂。

多Agent系统(Multi-Agent System,MAS)[7]是从问题的局部出发,通过自底向上方式形成的一种分布式人工智能系统。多Agent系统因其在计算时间和空间上的并行性与分布性,比较适合解决生产调度和管理领域的问题[8-10]。在冲突协商方面,可以基于合同网协议[11]和拟市场机制[12-13]等策略。文献[14]采用MAS方法将码头装卸作业抽象为一系列智能体行为,构建自动化码头协同运输作业系统。文献[15]将MAS技术应用于分布式电梯群控系统,基于拟市场协商机制建模以降低平均候梯时间和平均乘梯时间。文献[16]以典型的流程工业过程为对象,提出热连轧机工业生产过程多智能体系统的体系结构,并设计了相应的协调控制机制。以上研究表明,多Agent系统在解决分布式动态调度问题中具有优势。然而,以上系统均使用控制Agent或管理Agent等主控角色指挥整个系统的协同工作,随着问题规模的扩大,主控Agent会因其通信量过大而降低系统的整体性能。

本文设计并实现一种无主控的自治系统,构建一个包括出库板坯、入库板坯、行车和台车等在内的板坯出/入库协同调度模型,将入库作业和出库作业划分为多个子工序,以统一结构封装任务(板坯)和资源(运输设备),并依据自身不同的属性,形成各自的行为规则,平等主动地参与到系统运作中;根据设备的物理状态(位置、负载情况等)和板坯的出/入库计划时间等因素,确定Agent的评价函数,以仲裁的方式协商解决资源冲突,最后通过系统仿真实验对出/入库协同作业、完全入库作业和完全出库作业3种场景的运输性能进行比较分析。

2 问题描述及建模

2.1 问题描述

板坯出/入库协同调度系统实际上是一个离散事件动态系统。系统的随机性主要体现在同一板坯的2次调度所用时间可能不同,这主要是由:(1)运输设备在完成上一次任务后的停止位置不确定; (2)入库板坯和出库板坯可以选择多条入库路径或出库路径。

问题描述如下:在不考虑板坯倒垛的情况下,已知准备出/入库的板坯集I、板坯计划出/入库时间Timei和板坯库中所有运输设备集J。运输设备在某一时间只能服务一块板坯,一块板坯在某一时间只能被一个运输设备服务,且各种运输设备的运输时间不确定,求板坯集的最小出/入库总运输时间。

2.2 数学模型

为了能更准确地表述模型,引入如下符号体系:

I:计划出库或入库的板坯集合;

Timei:板坯i计划出库或入库时间;

J:板坯库内所有运输设备的集合;

Ji:未知向量,表示板坯i的出/入库路径,对应于相应的解;

Mi:已知集合,表示板坯i的可行出/入库路径集(板坯的出/入库运输有特定的规则);

T:计划展望期。

定义决策变量如下:

其中,i表示出库或入库的板坯,i∈I;j表示板坯库中的运输设备,j∈J;t表示时间,t∈T。令 τij1={t|Xijt=1}表示板坯i被设备j响应的时间;τij2={t|Zijt=1}表示板坯i被设备j完成运输任务的时间。建立模型如下:

其中,式(1)表示最小化板坯的出/入库总运输时间;式(2)表示对于运输设备j,完成板坯i运输任务的时间不小于响应板坯i的时间;式(3)和式(4)表示运输设备j从响应板坯i的申请到完成板坯i的运输任务期间,不允许响应其他板坯的申请,即运输任务不允许中断;式(5)和式(6)表示一块板坯同一时刻只能被一台设备服务,且运输任务不允许中断;式(7)表示运输设备j响应板坯i申请的时间不早于板坯i计划出库/入库时间;式(8)保证服务于板坯i的设备工艺路线(出/入库路径)的可行性。

3 板坯出/入库协同调度系统

3.1 系统设计

板坯出/入库协同调度系统属于典型的多环节复杂动态系统,且各工序环节相互制约,受很多随机因素的影响,解析方法的求解结果对分析实际设备的并行工作行为和资源利用情况能力有限。因此,本文采用MAS技术,设计并实现了一个基于主动实体协作的系统。根据系统的全局目标,将整个系统分解为出/入库板坯、行车和台车等多个智能Agent族群。这样,各个Agent的局部目标将归结为最小化Agent的空载等待时间,即最大化Agent的资源利用率。整个系统由板坯调度计划信息库、智能Agent族群和黑板模型构成,如图1所示。

图1 板坯出/入库协同调度MAS系统

3.1.1 板坯调度计划信息库

板坯调度计划信息库主要包括板坯库配置信息、库内板坯信息、连铸工序生产计划和热轧工序生产计划等信息。板坯库配置信息是与仓库物理环境相关的信息,包括仓库规模、库内运输设备配置情况等;库内板坯信息记录板坯库中现存板坯位置信息,包括板坯所处跨位、垛位等;连铸生产计划和热轧生产计划是根据板坯出/入库决策产生的当日计划出/入库板坯时序信息。系统通过访问信息库,根据计划板坯的出/入库时序,创建出库和入库的板坯Agent(Slab Agent),当一块板坯的出/入库任务完成后,板坯Agent生命周期结束,并更新信息库中的库内板坯记录。

3.1.2 Agent构造

主要包括板坯Agent、行车Agent和台车Agent 3种族群。每个Agent的内部都由知识库、推理机、行为、通信、控制与决策5种构件组成,如图2所示。每个Agent都是以决策与控制为核心,通过通信构件实时观察外界环境变化,并根据知识库中的领域知识等进行推理,利用评价函数,评价效用并确定行为,并再次通过通信构件将行为结果反馈给系统。这里,将辊道运输板坯的运动转化为板坯的自主行为,这样任务和资源即可不加区分地以统一结构封装。系统中所有Agent根据自身状态(当前位置、负载情况等)主动参与到系统的运行中。

图2 Agent结构

Agent构造的说明如下:

(1)板坯Agent

根据板坯的类型,分为出库板坯Agent和入库板坯Agent。出库板坯Agent处理已存放在板坯库中的冷坯,入库板坯Agent处理经过上游连铸工序产生的热坯。

1)数据

主要包括板坯i计划出库或入库时间Timei、出库板坯的起始位置(跨位、垛位)、批次信息、入库板坯的目标位置(跨位、垛位)等。

2)知识

出库板坯和入库板坯的能力信息,即辊道设备的运输规则和板坯Agent与普通行车Agent的通信规则。

3)行为规则

Setp 1根据板坯i计划出库或入库时间Timei,创建并初始化出库板坯 Agent或入库板坯Agent。

Setp 2出库板坯Agent向所在跨的行车Agent发出库申请,加入出库申请队列等待行车。入库板坯Agent观察板坯库中的环境(包括各跨的缓冲床、辊道前方等资源是否空闲)。

Setp 3入库板坯Agent依据图3所示规则完成状态的更新:静止、垂直位移或水平位移。静止,表示辊道处于等待状态;垂直位移,表示继续在辊道上运输前往下一个跨区;水平位移,表示入库板坯被推入缓冲床并向所在跨的行车 Agent发出入库申请。

图3 入库板坯Agent行为

Setp 4重复以上步骤,直到所有出库板坯加入出库申请队列或入库板坯被推入缓冲床。

(2)行车Agent

行车Agent处理板坯库中各个跨内水平运送板坯的作业,分为普通行车Agent和上料行车Agent,用于确保板坯按批次出库。

1)数据

主要包括行车配置信息和每辆行车位移范围的信息等。

2)知识

行车运行能力信息,即行车运输规则、与板坯Agent和与台车Agent的通信规则等。

3)行为规则

Setp 1根据数据和知识,创建并初始化上料行车Agent,转Step2;创建并初始化普通行车Agent,转Step3。

Setp 2上料行车Agent与普通行车Agent通信,判断是否满足板坯出库批次,若满足,则运输板坯出库并更新状态,若不满足,则在上料口空载等待。

Setp 3普通行车Agent判断当前自身的状态,如果是满载,则根据承载板坯的目标位置,确定是否需要向台车Agent发出送坯申请(将板坯送上台车)并确定自身行为;如果是空载,普通行车Agent观察本跨内所有的出库申请、入库申请和从台车上接取板坯取坯申请,然后根据当前所处的位置及各个板坯计划出/入库时间Timei等因素,利用评价函数FCrane确定自身行为。

Setp 4重复Step2或Step3,直到所有批次出库任务完成或所有出库申请、入库申请、取坯申请全部得到响应。

(3)台车Agent

台车Agent处理板坯库中各个跨间垂直运送板坯的台车作业。

1)数据

主要包括台车配置信息和台车位移范围的信息。

2)知识

台车运行能力信息,即台车运输规则、与行车Agent的通信规则等。

3)行为规则

Setp 1根据数据和知识创建并初始化台车Agent。

Setp 2台车Agent判断自身的状态,如果是满载,则根据承载板坯的目标位置来确定自身的行为,同时发送取坯申请,通知目标跨的行车Agent接取板坯;如果是空载,则根据所有行车Agent的送坯申请、自身所处位置、板坯计划出/入库的时间Timei等因素,利用评价函数FTrolley,确定自身行为。

Setp 3重复Step2,直到所有的送坯申请全部得到响应。

3.1.3 黑板模型

黑板模型体现了平行协商机制,是一个开放的公共数据区,允许参与协商的各方在黑板上进行信息共享,是一种信息透明度极高的民主合作方式下的协商机制。具体来讲,入库板坯Agent、出库板坯Agent、普通行车 Agent、上料行车 Agent和台车Agent将需要传递的信息,以广播的方式,写在系统的一个公共数据区内,具体包含全局数据和局部数据2个部分。全局数据是与出/入库协同调度系统全局相关的数据,包括系统时钟、出/入库板坯数量等。局部数据主要与各Agent族群相关,记录Agent之间的通信信息,包括板坯Agent向行车Agent发出的出库申请或入库申请及响应集合、行车Agent向台车Agent发出的送坯申请及响应集合、台车Agent向行车Agent发出的取坯申请及响应集合等。图4表明了各种Agent之间传递信息的情况。

图4 系统通信序列

3.2 协商机制

本文引入市场行为中的投标/仲裁机制来协调资源冲突。当一个Agent有任务需要其他Agent合作完成时,就向其他Agent广播有关该任务的信息,即招标;接到招标信息的Agent检查自身解决该问题的能力,然后发出投标参数;最后由发出招标信息的Agent评估投标参数,选出最合适的中标者并与之合作。假设系统包括一辆台车和多辆行车,以台车Agent为例,构造Agent间的协商机制。

符号说明:

JC:表示发出送坯申请的行车集合,JC⊂J;

道所需时间(即满载运行时间);

Timei:板坯i计划出库或入库时间;

α:行车上的板坯i计划出库或入库的时间Timei对应的权值;

β:为台车运行时间对应的权值;

γ:为行车运行时间对应的权值;

Batchi:当板坯i为出库板坯但不属于当前出库批次时,Batchi为0;当板坯i为入库板坯或板坯i属于当前出库批次时,Batchi为1。

设计台车的评价函数FTrolley如下:

其中,Q为一个较大的常数;Timei和是行车发出送坯申请时提供给台车的报价,台车结合自身因素完成评价,从发出送坯申请的行车集合JC中选择一台行车响应送坯申请。

同理,普通行车Agent在收到来自本跨的入库申请、出库申请、取坯申请时,会依据Timei和行车空载移动到申请板坯i的时间2个因素来评价效用。式(10)为普通行车Agent的评价函数。

4 仿真实验

本文以某著名钢厂板坯库的入库和出库运输作业实际工艺路线为基础,将板坯出/入库作业分解成辊道垂直运输、行车水平运输和台车垂直运输等工序,设计多Agent板坯出/入库协同调度系统。实验采用NetLogo仿真软件,相关参数为:板坯库几何尺寸为668 m×668 m;单入口,单出口;辊道4段,普通行车4辆,台车1辆,上料行车1辆。实验中入库板坯目标位置和出库板坯的起始位置随机产生,行车和台车的初始位置随机设定;所有设备的空/满载运输速度均为2 m/s,板坯在不同工序上的中转作业时间为0。

4.1 出/入库协同作业分析

假设出/入库板坯全部为连铸-离线轧制板坯(CCR),即考虑所需出/入库运输工序最复杂的情况。板坯的计划入库频率为15块/h,出库计划随时间分布不均匀,以批次为单位进行(每批板坯数≥5)。统计完全入库作业、完全出库作业和出/入库协同作业3种场景下运输板坯的作业时间,如表1所示。其中,出(或入)库时间是指指板坯i的计划出(或入)库时间Timei与实际出(或入)库时间的差值;出(或入)库等待时间是指出(或入)库时间之内板坯处于静止状态的总时间;总运输时间是指系统完成所有运输作业的总工作时间。平均吞吐率是指出/入库板坯总数除以总运输时间。

表1 板坯运输时间均值统计

在完全入库作业中,板坯处于等待状态的时间很短,基本上到达入库口后就会被推入目标跨的缓冲床,且入库路径的选择上大都不需要台车中转,减小了运输时间。在完全出库作业中,由于受到出库作业工艺路线集的约束,出库作业大都需要使用台车,而台车的运能和数量都是有限的,所以与入库作业相比,出库作业时间较长,而且处于等待状态的时间也明显增加。

在出/入库协同作业中,入库板坯由于需要与出库板坯竞争行车,因此满载等待时间显著增加,导致平均入库时间增加;而出库作业的时间与完全出库作业相比并没有明显增加,这说明,出/入库协同作业的多Agent系统能够利用投标/仲裁机制,充分发挥运输设备空闲时间的作用,在入库作业的同时进行出库操作,提高设备的利用率和并行性。当出库批次为2时,虽然出/入库作业的等待时间都有增加,但是系统总的工作时间增长并不大,系统的并行能力得到充分发挥。系统平均吞吐率表明,出/入库协同作业下,系统的并行能力大大提高,虽然板坯的总数增加了,但是,从整体角度而言,平均每块板坯的运输时间却减少了。当出库批次增加为3时,无论是出库板坯还是入库板坯都会因为竞争资源陷入长时间的满载等待中,系统整体性能下降。在实际生产中,可以增加直接热装板坯(DHCR)数量,以便同时缓解CCR出库和入库两方面的运输压力。

4.2 资源利用率分析

资源利用率反映板坯库内的各种运输设备在运输过程中的使用情况,计算公式为:

通过仿真实验,分别统计完全入库作业、完全出库作业和出/入库协同作业3种场景下,普通行车和台车的资源利用率,如表2所示。

表2 资源利用率

由表2可知,在完全入库作业中,根据实际的入库板坯数量,4辆普通行车的利用率基本保持均衡,且处于一个比较低的水平,存在大量的空载等待时间,同时台车的利用率较低,只有目标位于出库口所在跨的入库板坯需要台车中转。在完全出库作业中,行车1和台车的利用率都有一定的增加,但系统设备的利用率偏差较大,设备利用不均衡现象显著。

与前2种情况相比,出/入库协同作业中所有设备的利用率均明显增加,空闲等待时间减少,并且保持均衡。其中,行车1和台车的利用率增长明显,这表明出库作业大都依赖台车中转完成,且行车1除了负责来自本跨的出库操作,还要接收经台车中转而带来的其他跨的出库板坯,因此利用率增加,整个系统设备能力得到充分发挥。

5 结束语

板坯出/入调度系统是在同时兼顾出库作业和入库作业的前提下,采用多种运输设备协同运输的分布式并行系统。本文以某钢厂板坯库库内运输调度作业为背景,以最小化板坯出/入库总运输时间为目标建立数学模型;基于MAS的计算机仿真方法,设计并实现了一个无主控的板坯出/入库协同调度系统,并基于招标/投标的协商机制,设计评价函数以仲裁方式协调资源冲突;最后通过系统仿真实验对出/入库协同作业、完全入库作业和完全出库作业3种运输场景进行比较,结果表明,出/入库协同作业有效提高了板坯库系统的运输吞吐率,另外在投标/仲裁机制的协商作用下,其运输设备利用率也提高明显且保持均衡。

[1] 涂雪平,施灿涛,李铁克.基于模糊匹配的板坯入库优化决策问题模型及求解[J].北京科技大学学报, 2011,33(3):376-382.

[2] 徐骏驰,杜 斌,朱 俊,等.基于混合遗传算法的板坯入库优化算法[J],控制工程,2009,16(5):547-550.

[3] 李耀华,王 伟,胡国奋,等.热轧板坯库出库计划编制模型与算法研究[J].计算机集成制造系统,2006, 12(3):377-381.

[4] 计明军,刘丰硕,李郭记,等.基于装卸协同作业的集装箱码头集卡调度及配置优化[J].大连海事大学学报,2010,36(1):47-50.

[5] Lee D,Cao J X,Shi Q X.A Heuristic Algorithm for Yard Truck Schedule Problem in Container Terminals[J]. Tsinghua Science and Technology,2010,15(4):467-474.

[6] 李浩渊,汪定伟.集装箱码头动态集卡配置的并行仿真优化方法[J].系统仿真学报,2009,21(14): 4243-4247.

[7] Minsky M.The Society of Mind[M].New York,USA: Simon&Schuster,1988.

[8] Caridi M,Cavalieri S.Multi-agent Systems in Production Planning and Control:An Overview[J].Production Planning&Control,2004,15(2):106-118.

[9] Shen Weining,Wang Lihui,Hao Qi.Agent-based Distributed Manufacturing Process Planning and Scheduling:A State-of-the-artSurvey[J].IEEE Transactions on Systems,Man and Cybernetics,Part C: Applications and Reviews,2006,36(4):563-577.

[10] 赵 博,范玉顺.MAS技术在生产调度研究中的应用[J].控制与决策,2003,18(1):1-6.

[11] Smith R G.The Contract Net Protocol:High-level Communication and Control in a Distributed Problem Solver[J]. IEEE Transactions on Computers,1980,29(12):1104-1113.

[12] Adhau S,Mittal M L,Mittal A.A Multi-Agent System For Distributed Multi-Project Scheduling:An Auctionbased Negotiation Approach[J].Engineering Applications of Artificial Intelligence,2012,25(8):1738-1751.

[13] Siwamogsatham T,Saygin C.Auction-based Distributed Scheduling and Control Scheme for Flexible Manufacturing Systems[J].International Journal of Production Research, 2004,42(3):547-572.

[14] 王祥雪,朱 瑾.基于MAS的集装箱自动化码头协同作业系统模型[J].计算机应用研究,2013,30(4): 1072-1075.

[15] 王遵彤,孙 栋,乔 非,等.分布式电梯群控系统多目标调度算法[J].控制理论与应用,2010,27(5): 602-608.

[16] 董 洁,尹怡欣,彭开香.流程工业多智能体系统协调控制[J].系统工程理论与实践,2008,(10):119-124.

编辑 顾逸斐

Slab Discharge/Location Coordinate Scheduling System Based on Multi-Agent

ZHANG Qiqi1,2,LIU Peng1,ZHANG Tao1
(1.School of Information Management and Engineering,Shanghai University of Finance and Economics,Shanghai 200433,China; 2.Shanghai Vocational College of Science and Technology,Shanghai 201800,China)

According to the collaborative transportation problem of the slab yard,this paper constructs a mathematical model to minimize the total slab discharge/location transportation time and designs an autonomous Multi-Agent System (MAS)including different roles,for example,the slab,the crane and the trolley.In this system,loading the slab into the yard and discharging the slab from the yard are considered at the same time.In addition,in order to coordinate the resource conflict,a multi-Agent negotiation and scheduling strategy based on biding-arbitration mechanism is incorporated into the system using evaluation functions.In system simulation,the slab discharge/location coordinate system is compared with single location or single discharge system respectively,and the results show that the transportation throughput of the coordinate system is better than the single ones,and facility utilization is effective and balanced.

slab discharge/location coordinate scheduling;Multi-Agent System(MAS);blackboard model;bidingarbitration mechanism;collaborative transportation;system simulation

1000-3428(2015)01-0289-07

A

C934

10.3969/j.issn.1000-3428.2015.01.055

国家自然科学基金资助项目(71171126);教育部高等学校博士学科点专项科研基金资助项目(20130078110001);教育部留学回国人员科研启动基金资助项目;上海市哲学社会科学规划基金资助项目(2011BGL015);上海财经大学研究生创新基金资助项目(CXJJ-2013-435);上海市金融信息技术研究重点实验室开放课题基金资助项目。

张琦琪(1977-),女,讲师、博士研究生,主研方向:生产计划与调度,智能优化方法;刘 鹏、张 涛(通讯作者),教授、博士。

2014-02-17

2014-03-17 E-mail:taozhang@mail.shufe.edu.cn

中文引用格式:张琦琪,刘 鹏,张 涛.基于多Agent的板坯出/入库协同调度系统[J].计算机工程,2015,41(1):289-295.

英文引用格式:Zhang Qiqi,Liu Peng,Zhang Tao.Slab Discharge/Location Coordinate Scheduling System Based on Multi-Agent[J].Computer Engineering,2015,41(1):289-295.