基于多Agent的柔性作业车间预先/重调度系统

任海英，邹艳蕊

(北京工业大学经济与管理学院，北京 100124)

动态调度问题的提出，主要应对生产过程中出现的各种干扰因素，如急件到达、加工机器故障、工件取消和工件优先权增加等，从而保证既定预先调度计划得以正常执行。因此，需要根据系统状况不断地进行生产计划的重调度，以保证生产过程的顺利进行。目前，动态调度问题主要分为3类［1］:完全反应调度、鲁棒性调度和预先/重调度。完全反应调度可以理解为实时控制，基于生产系统的当前状态做出每个工件的调度决定。动态调度问题主要利用局部信息，其实质为局部优化调度，并不能满足全局优化的要求。鲁棒性调度在调度开始前即考虑到车间调度环境中可能发生的不确定性事件，并将这些不确定性事件以某种形式集成到调度中，但冗余度过高、对实时事件反应能力差会影响到鲁棒性调度的优化效果。预先/重调度在融合上述两种调度的优点，摒弃两者弱点的基础上，将其分为两个步骤来执行:①产生一个工作车间预测的理想调度，即预先调度。②执行过程中发现没有预测的干扰时，根据一定策略修改预先调度。

预先/重调度方法已经得到了广泛的研究，遗传算法、启发式算法和分派规则是预先/重调度经常用到的方法，并且取得了丰富的成果。文献［2］在分离图表的基础上提出重调度算法，即对受到影响的操作重新调度。文献［3］研究了预先/重调度，在柔性制造车间领域结合应用了遗传算法和启发式算法，不仅利用遗传算法实现了预先调度，还在重调度过程中考虑了机器故障、急件到达、订单优先权增加和订单取消等4种干扰，同时对每种干扰设计一整套相应的启发式算法，通过与分派规则比较，证明所提方法用于预先/重调度的优越性。WONG［4］等将计划和调度结合，基于Agent采用市场招投标的方式实现预先/重调度。但是这些方法不是计算量大就是效果不明显。多Agent方法已经广泛应用于生产调度方面，但用Agent方法研究预先/重调度还较少，没有形成系统的理论。为此，笔者以柔性作业车间为调度对象，用Agent方法对其预先/重调度问题做一次初步探索。

1 预先/重调度系统

1.1 问题描述

笔者对柔性作业车间调度问题做出如下描述:某车间有多台机器并生产多种产品，将每种产品的一个计划加工批次看作一个工件，其需要若干工序完成，每道工序可在一台或多台机器上完成。假定每道工序加工前的准备时间和生产单元间的运输时间与产品和批量无关，均记入加工时间，且加工过程中除设备外的其他资源充足，无须调度。工件预先到达车间，每个工件都有各自的工期。预先调度的目标是最小化平均滞后:

式中:Cj为工件j的完工时间;dj为工件j的工期;n为工件的数量。

在调度执行过程中，会产生多种类型的干扰，因此需要重调度以促进调度继续可行。重调度的目标为:①在干扰发生后的最短反应时间内保证调度的可行性;②保证预先调度目标的优化;③最小化与预先调度背离。由于在处理干扰过程中，会出现加工工具转移和开始时间改变导致携带成本的情况，因此，笔者应用开始时间背离解释重调度方案的优劣，其中开始时间背离为重调度与预先调度之间工件的工序完成时间差的总和，即:开始时间背离=Delay+Rush;Delay为完成时间差为正值的总和;Rush为完成时间差为负值的总和。

1.2 调度系统的Agent指标

(1)工件Agent(PA)。每个工件对应唯一的PA，其主要负责为对应的工序选择最优机器，并达到最优目标。所谓最优目标，即在工期前完成加工任务且完成时间最短。PA属性主要包含:工件号、工件类型、工件的工序列表、释放时间、工期，以及机器投标列表等。

(2)机器Agent(MA)。每台机器对应唯一的MA，其主要负责投标工作和选择加工工件等。MA的属性主要包含:机器类型和状态、工件招标列表、中标列表、等待列表、加工列表和机器故障等。MA的目标是使自身收益最大化。

(3)工序Agent(SA)。工件的每一道工序对应唯一的SA，同时工序信息记录在SA中。工序信息包含:工序最早开始时间、工序加工开始时间和完成时间、可加工该道工序的备选机器及其加工时间等。调度过程中，SA从数据库中读取与其对应的机器信息和时间信息，将其发送至相应PA，并放入工件工序列表。SA主要用来记录工序状态，属非智能型的反应式Agent，用于工序招标和评标，并将中标安排到相应机器。

1.3 预先调度策略

笔者采用多对多协商机制建立调度系统，其协商和调度流程按如下5个步骤进行:

(1)工件信息注册、机器信息注册以及Agent指派。工件抵达车间后，系统赋予每个工件一个唯一的PA。PA从数据库中读取相应工件的到期日和工序列表信息，并将相应工件注册到工件列表。同时，车间中的机器均具有一个MA，其保证将所有机器注册至机器列表中［5］。

(2)PA向相应MA进行招标。PA完成一道工序后，会随即从工序列表中选择下一道工序，并向选中工序的所有可选机器MA发出招标信息，招标信息放在工件招标列表中，主要包括工件类型和机器类型。PA进入投标等待阶段。

(3)MA统筹其招标工件，并发出投标。MA主要根据Arrange原则计算工件相应工序的开始时间和完成时间，填写投标标书后发送至向其招标的工件PA，同时将投标标书放入机器投标列表中。MA进入中标等待阶段。

(4)PA选择MA。PA根据最小完成时间确定中标机器［6］，并将相应工件的工序添加至MA工件招标列表中。

(5)MA选择中标工件。若工件中标列表中有多个工件，MA则根据关键比率CR(见式(2))选择工件，若CR相同，MA则利用SPT规则选择工件。MA将选中的工件放入工件加工列表，然后对选中工件的下一道工序继续招标，其余未被选中工件，离开机器的工件中标列表，重新招标。

式中:dj为工件j的工期;ct为当前时刻;Rjm为工件j在第m台机器加工前的剩余加工时间，即，Sjm为工件j在第m台机器加工前的剩余工序集合。

1.4 重调度策略

1.4.1 重调度假设条件

条件1 忽略重调度时间，一旦重调度完成，相应工件立刻进入加工状态。

条件2 所有干扰随机产生，且不会在重调度的过程中产生。

条件3 采用不间断策略，即受到影响的工件完成重调度后，该工件在新机器上重新开始加工。

条件4 仅考虑机器故障和急件到达两种干扰。假设可准确估计机器故障发生时的故障持续时间，假设急件到达时其重要性远大于普通工件。

1.4.2 重调度的基本思路

采用受到影响的工件重新调度方法，要点是识别受到影响的工件，并对其进行重新调度。

对于机器故障，在机器故障的这段时间加工的工序必然受到影响，相应的工件完成时间也会受到影响。有时受到影响的工件工序会导致延迟后的完成时间大于加工计划中随后工序的开始时间，这就导致调度不可行，因此需要对直接和间接受到影响的工件工序进行识别，将它们放入受到影响的工件列表(AO)中，由Agent重新进行招标和调度安排［7］。

对于急件到达，急件直接插入到能够加工它的机器上进行加工，同时将机器上预先安排的工件工序加入到AO中重新进行招标和调度安排。

1.4.3 机器故障谈判策略

(1)定义机器故障开始时间、故障持续时间和机器号为机器故障，当故障机器MA识别到受影响的PA后，会解除二者之间的合作关系。识别方法如下:

If((工件相应工序的开始时间≤故障开始时间and工件相应工序的结束时间＞故障开始时间)或者(工件的开始时间≥故障开始时间and工件的开始时间＜故障开始时间+故障持续时间))

Then{MA将该工件相应工序放入到AO中，并将其从工件加工列表中删除，设置工件的加工状态为未加工}

(2)AO列表中的PA向能够加工它的MA进行招标。检查AO，如果列表中工件工序之前的工序并没有在AO中(保证工件的前后两道工序不同时招标)，则工件的相应工序向能够加工它的机器进行招标，招标信息包括最早开始时间和最晚开始时间，计算公式如下:

最早开始时间=max{故障开始时间，前续工序的完成时间}

最晚开始时间=If(它是最后一道工序){工件的最后期限-加工时间}

Else{工件的下一道工序的开始时间-加工时间}

(3)MA安排受到影响的工件并向工件投标。投标MA根据工件相应工序最小松散时间(最晚开始时间-最早开始时间)选择加工工件，并安排工件。安排方式如下:

在工件相应工序的最早开始时间之后

if(工件加工列表在两个工件之间有空位置存在)then{工件相应工序的开始时间=空位置的开始时间，工件加工列表索引号=空位置之前的工件工序+1}

Else{开始时间=机器上最后一道工序的完成时间，工件加工列表索引号=工件最后一道工序的索引号+1};

工件相应工序的完成时间=开始时间+加工时间。MA将完成时间和等待加工列表索引号写入投标标书发送给相应PA。MA删除相应的招标信息。

(4)PA选择MA。工件选择最小完成工序时间的机器，并将相应工件的工序放入到工件等待加工列表。PA删除相应的投标信息。

(5)机器加工工件。PA检查工件的后续工序和相应机器工件等待加工列表中的下一道工序是否受到影响，如果受到影响，放入到AO中，并进行招标。

1.4.4 急件到达谈判策略

(1)急件PA到达系统。干扰属性包括工件类型，工件的到达时间。系统通过工件类型从数据库中调出工件的相关属性，来产生急件［8］。

(2)急件的相应工序向能够加工它的机器进行招标。相应内容如预先调度。

(3)MA安排急件。由于是急件，因此优先级高于其他普通工件，安排方式如下:

if(机器当前有工件)then{急件的开始时间=机器当前工件的完成时间}

if(机器当前没有工件)then{急件的开始时间=急件的到达时间}。

并将信息发送给相应机器，内容如预先调度。

(4)急件选择机器。同机器故障谈判策略的步骤(4)。

(5)急件离开机器。机器加工完急件后，急件的下一道工序进行招标，转到步骤(2);MA检查工件等待加工列表中的后续工件是否受到影响，如果受到影响，则将后续工件工序放入到AO中，按照机器故障谈判策略选择机器进行加工。

2 仿真实验

笔者采用 CHRYSSLOURIS等［9］的实验方法测试上述模型的有效性，假设实验条件为:车间拥有4个工作中心、9种机器和10种工件，每种工件的工序在1到5之间不等，且某些工序可被不同机器加工，实验所用数据参考文献［10］的附录A(主要包含工件数量、工件工序数、加工时间和加工机器类型等)。仿真实验将上述数据录入数据库，并利用Eclipse平台连接数据库，读取相应的工件信息、工序信息和加工进度等。当10种工件同时到达车间时，干扰是随机产生的，机器故障的开始时间是0到MakeSpan之间的随机数，机器故障的持续时间是0到500之间的随机数。急件也是随机产生的，急件的到达时刻是0到MakeS-pan之间的随机数。每次试验进行10次，取其平均数。为了比较，笔者采用Jain的初始调度(遗传算法)和right-shift重新调度方法分别与预先调度和重调度结果比较(由于Jain是可中断调度，无法与其比较)，证明所提出方法的优越性。工期的设定采用TWK规则:

式中:rj为工件j的释放时间;Pj为工件j的加工时间;K为工期紧急度系数，将K设为1.5。

2.1 预先调度结果

预先调度结果如图1所示，预先调度目标函数的结果如表1所示。

图1 预先调度结果

表1 预先调度目标函数的结果

与Jain的遗传算法相比，多Agent方法的平均滞后、MakeSpan和机器利用率都有相应程度的提高，平均滞后提高13.01%，MakeSpan提高4.60%，机器利用率提高5.21%。

2.2 重调度结果

2.2.1 机器故障实验

在机器故障实验中，分别测算随机产生0、6、9、12、15、18、21 次故障的机器，与 right-shift方法比较结果如表2所示。

2.2.2 急件到达实验

在急件到达实验中，分别测算0、1、2、3个急件到达的情况，急件到达的目标函数如表3所示。

2.2.3 结果分析

(1)与预先调度相比，重调度系统在受到干扰影响之后，其平均滞后、MakeSpan和MeanFlowTime都有相应程度的增大，机器利用率也相应下降。

(2)随着干扰程度的加深，各预先调度目标函数受到影响，开始时间背离也相应增大。

(3)从表2和表3可以看出，当干扰发生时，相比right-shift方法，多Agent方法的各目标函数得到相应优化。

3 结论

建立了多Agent的柔性车间预先/重调度系统，用Java语言进行程序设计，以平均滞后为预先调度主要目标，开始时间背离为重调度目标进行仿真实验，通过将预先调度与Jain的遗传算法、重调度与right-shift方法相比较，结果表明了笔者所提出的方法的优越性。由于只考虑机器故障和急件到达两种干扰，因此对其他干扰进行策略设计和实验，并对所提干扰处理策略进行优化，将是笔者下一步的研究目标。

表2 机器故障目标函数结果

表3 急件到达目标函数结果

［1］VIEIRA G E，HERRMANN J W，LIN E.Rescheduling manufacturing systems:a framework of strategies，policies，and methods ［J］.Journal of scheduling，2003(6):39-62.

［2］ABUMAIZAR R J，SVESTKA J A.Rescheduling job shops under random disruptions［J］.International Journal of Production Research，1997，35(7):2065-2082.

［3］JAIN A K，ELMARAGHY H A.Production scheduling/rescheduling in flexible manufacturing［J］.International Journal of Production Research，1997，35(1):281-309.

［4］WONG T N，LEUNG C W，MAK K L，et al.Integrated process planning and scheduling/rescheduling-an agent-based approach［J］.International Journal of Production Research，2006，44(15):3627-3655.

［5］WONG T N，LEUNG C W，MAK K L，et al.An agent-based negotiation approach to integrate process planning and scheduling［J］.Int J Prod Res，2006，44(7):1331–1351.

［6］任海英，邹艳蕊.基于多Agent协商的柔性车间调度系统［J］.微计算机信息，2011，27(1):14-16.

［7］李贤，王占杰.基于工艺路线的多Agent车间调度系统设计与实现［D］.辽宁:大连理工大学图书馆，2007.

［8］CHURCH L K，UZSOY R.Analysis of periodic and event-driven rescheduling policies in dynamic shops［J］.International Journal of Computer Integrated Manufacturing，1992，5(3):153-163.

［9］CHRYSSOLOURIS G，PIERCE J E，DICKE K.A decision-making approach to the operation of flexible manufacturing systems［J］.The International Journal of Flexible Manufacturing Systems，1992，3(4):309-330.

［10］SIWAMOGSATHAM T，SAYGIN C.Auction-based distributed scheduling and control scheme for flexible manufacturing systems［J］.Int J Prod Res，2004，42(3):547-572.