一种柔性路径下跨作业单元调度方法

摘要

本发明涉及一种柔性路径下跨单元调度方法，包括以下步骤：一、定义一套符号描述柔性路径下跨单元调度问题；二、建立多Agent协商模型：定义四种基本角色：工件Agent，机器Agent，单元Agent以及管理Agent，这四种Agent允许自由协商交互，以协同求解复杂问题；三、多Agent之间进行协商，完成跨单元调度。本发明更注重全局性能，使得最大完工时间、平均延迟、延迟工件个数、平均跨单元次数性能指标得到提升，并且降低了动态协商机制的复杂度。

主权项

1.一种柔性路径下跨单元调度方法，包括以下步骤：一、定义如下符号描述柔性路径下跨单元调度问题：i    工件集的索引i＝1，...,J，其中J为需要进行跨单元调度的特殊工件的个数；q_i    工件i的工序集的索引(q_i＝1,..,N)，其中N为工件i的工序数；L_i    工件i的跨单元路径的集合；l_ir    工件i的跨单元路径集的索引(r=1,...,R)，R为路径数目；m    工件的下一道工序可选的加工机器的索引；t    当前时刻；t_m    机器上当前工件的加工完成时刻；P_{avg_i}    工件i的历史平均处理时间；在t时刻机器m的缓冲队列中等待加工的工件集合；p_ji    工件i的第j道工序的历史平均加工时间；p_jim  工件i的第j道工序在机器m上的加工时间；d_i    工件i的交货期；m_qi    可以加工工件i的第q道工序的机器集合；Tr_i    工件i的单位距离的转移时间；H_c，c′    单元c到单元c′的距离；在t时刻工件i的松弛时间；即工件i的预计完工时间与其交货期的时间差;二、建立多Agent协商模型：定义四种基本角色：工件Agent，机器Agent，单元Agent以及管理Agent，这四种Agent允许自由协商交互，以协同求解复杂问题：(1)工件Agent当工件到达之后为其创建一个工件Agent，工件Agent的功能是：确定加工 序列，选择工艺路径，计算自身信息素以及被选中概率，当工件被加工完成之后，由管理Agent注销该工件Agent；(2)单元Agent单元Agent代表系统内的制造单元，负责管理单元内所有机器Agent，同时与工件Agent和机器Agent进行通信；记录机器Agent的基本信息，计算单元内机器的信息素和被选择的概率；当被选为工件Agent的加工单元时，向机器Agent告知工件的加工信息；(3)机器Agent机器Agent代表单元内的机器，功能是向工件Agent发出招标信息，以决定缓冲队列中工件的加工顺序，同时机器Agent接收来自单元Agent的指令，加工相应的工件；(4)管理Agent为了方便工件Agent和单元Agent以及机器Agent之间的协商，定义了管理Agent：管理Agent负责管理和维护全局信息，包括根据单元和机器的信息为新到来的工件提供可行路径集合，并对可行路径集合进行处理；当工件在机器上加工完成后需在管理Agent中记录该加工时间的信息，用于统计工件的历史平均处理时间；三、多Agent之间进行协商，完成跨单元调度，具体包括：(1)工件决策跨单元路径：在工件到来之前，各个机器Agent向其所在的单元Agent注册信息，各单元Agent将所有已知信息告知管理Agent，从而使管理Agent获得单元制造系统CMS内所有的单元及单元内机器的信息；当新的工件到来后，为其创建一个工件Agent，工件Agent向管理Agent注册信息，包括交货期，工件的所有工序及其次序约束关系；管理Agent根据注册信息为新到来的工件提供可行路径集合，并对可行路径集合进行处理，去除冗余路径，判断共有路径和非共有路径；对于每个工件的所有可选路径，管理Agent将非共有路径部分的信息告知有关的单元Agent，并发送针对该工件形成联盟的消息；联盟Agent形成后等待接收工件Agent发送的加工请求信息，同时，管理Agent将处理之后的路径信息发送给工件Agent，工件Agent根据接收到的路径信息，分别对共有路径和非共有路径采取相应的措施：对于共有路径，工件Agent告知路径中相应的单元 Agent，单元Agent将分配到的工件的待加工工序放入机器的缓冲队列中等待加工，并更新相应机器Agent的缓冲队列信息；对于非共有路径，工件Agent向若干个联盟Agent发送招标信息CFP，联盟Agent收到请求后将形成联盟Agent的各单元Agent的信息素即单元内能加工该工件的机器的信息素发送给工件Agent；工件Agent计算各个联盟Agent被选择的概率，选中其中一个联盟Agent，并向其发送确认信息，同时向其他未被选中的联盟Agent发送拒绝信息；被选中的联盟Agent告知相关的单元Agent将工件的加工任务放入机器的缓冲队列中；其中，机器m的信息素计算通过公式(1)得到：在公式(1)中，(t_m-t-H_c，c′Tr_i)表示工件到达机器m后机器m可用的等待时间，其中H_c，c′Tr_i表示工件由上单元移动到当前单元所花费的时间，表示机器m的任务缓冲队列中的所有待加工工件的完成时间，p_qim表示当前工件i在机器m上所需的加工时间；如果(t_m-t-H_c,c′Tr_i)的值为负数，表示工件在到达该机器之前，机器已经被释放，在这种情况下，机器会在任务缓冲队列中选择下一个加工的工件，那么(t_m-t-H_c,c′Tr_i)再加上这个工件的加工时间即为工件i到达机器m后，等待机器m可用的等待时间；工件i的第q道工序选择机器m的概率通过公式(2)得到：其中，参数α,β决定信息素和启发式信息的影响程度大小，具体值由用户设定；工件i的第q道工序在机器m上加工的启发式信息η_qim的计算见公式(3)：η_qim＝1/p_qim    (3)机器m被选中的概率即为其所在单元被选中的概率，在此基础上，根据公式(4)计算联盟被选中的概率： (2)机器决策工件的执行顺序当机器的当前工件加工完成后，机器Agent检查其缓冲队列，如果队列中只有一个待加工工件，那么直接加工该工件，如果缓冲队列中的待加工工件有两个或两个以上，那么机器Agent向可加工的工件Agent发送招标信息CFP；各工件Agent收到机器Agent的请求后计算相应工件的信息素并且发送给机器Agent，机器Agent根据收到的信息素计算各个工件Agent所代表的工件被选择的概率，从中选择一个工件Agent后对其发送确认信息，同时对其他未被选中的工件Agent发送拒绝消息；被选中的工件Agent确认信息后加工该工件，当该工件加工完成之后，机器将该工件在单元内的加工信息告知管理Agent；当机器的缓冲队列中没有待加工的工件时，该机器Agent的协商过程停止;工件i的信息素计算见公式(5)：其中表示松弛时间，松弛时间通过公式(6)得到；q表示工件i已经完成的工序数；其中，表示从当前时刻t到工件i所有工序全部完成所需的时间，即该工件的剩余加工时间；公式(5)和(6)中涉及到的P_{avg_i}和p_ji是通过计算管理Agent记录的工件历史完成信息而来的；工件i被选择概率的计算与机器被选择概率的计算相似，由信息素和启发式信息组成，计算公式见公式(7)：其中，参数α,β决定信息素和启发式信息的影响程度大小，具体值由用户设定；启发式信息η_qim同样根据公式(3)计算得到；工件决策跨单元路径以及机器决策工件的执行顺序是同时进行并且不断重复的，直到没有新的工件到来并且所有已分配的工件都加工完毕后停止。