基于ACA模型的多品种多工艺制造企业车间调度控制方法

摘要

一种基于ACA模型的多品种多工艺制造企业车间调度控制方法，包括以下步骤：1)设定多品种多工艺制造企业车间的目标函数，当将任务Agent的任务信息由协调Agent发送给决策Agent时，决策Agent先将任务信息用有向图G表示出来，并且由决策Agent通过任意算法得到的调度规则做为禁忌搜索法的初始解；2)规则决策元Agent首先计算目标值F，然后在该调度的邻域内用禁忌搜索法搜索出其他调度方法，采用目标值最小的解作为采纳的规则；3)元胞空间里的各个元胞(即工位)将根据规则决策元授予的调度规则进行状态改变。本发明能够描述复杂调度系统，很好地反映生产实际并兼顾模型运算效率，快速、较准确的解决了动态、复杂的多品种多工艺制造企业车间调度问题。

主权项

一种基于ACA模型的多品种多工艺制造企业车间调度控制方法，其特征在于：所述多品种多工艺制造企业车间中，工件j在机器i上的操作完成时间记作Cij，工件j离开整个加工系统的时间记作Cj，工件j的工期为dj，工件j的延迟定义为：Lj＝Cj‑dj(1)当工作完成滞后的时候是正，而当工作提前完成的时候是负；工件j的滞后定义为：Tj＝max(Cj‑dj，0)＝max(Lj，0)(2)采用制造期Cmax、最大延迟Lmax、总滞后时间∑Tj作为调度目标，通过权重加合法得到调度总目标函数的表示为：min(θ1Cmax+θ2Lmax+θ3∑Tj)(3)所述控制方法包括以下步骤：1)所述多品种多工艺制造企业车间的目标函数为：minF＝min(θ1Cmax+θ2Lmax+θ3∑Tj)，j＝1，2，...，n    (4)s.t. ykj‑yij≥pij    对所有(i，j)→(k，j)∈ACmax‑yij≥pij    对所有(i，j)∈Nyij‑yil≥pil∨yil‑yij≥pij    对所有(i，l)和(i，j)，i＝1，2，...，myij≥0      对所有(i，j)∈NLj＝Cj‑djTj＝max(Lj，0)Cmax＝max(C1，C2，L，Cj)式中：yij表示操作(i，j)的起始时间，N表示都有操作(i，j)的集合，A为所有路线约束(i，j)→(k，j)的集合，它需要工作j在机器k加工前先在机器i上加工，pij表示加工时间；当将任务Agent的任务信息由协调Agent发送给决策Agent时，决策Agent先将任务信息用有向图G表示出来；2)规则决策元Agent收到协调Agent发送来的调度规则的信息后，首先计算目标值F；然后在该调度的邻域内搜索出其他调度方法；(2.1)调度的邻域结构在关键路径上的两个加工任务(i，j)和(i，k)之间的邻对交换，在交换之后的机器i上，任务(i，k)在任务(i，j)之前执行；对于工件k，任务(i，k)属于这个工件，即工件k在机器h上完成任务(h，k)之后马上进行操作；在机器h上，交换任务(h，k)和在(h，k)之前在机器h上进行的任务，记为(h，l)；(2.2)搜索方法在获得初始调度解时，禁忌表是空的，规则决策元Agent的搜索过程如下：令π、V(π)、N(π)和πb分别表示加工顺序、移动集、邻域和当前已知的最好的解；假设移动集V(π)非空，将这些移动分成两类：非禁忌的移动和禁忌的移动。V(π)/T中的移动是未禁忌的，而V(π)∩T中的移动则是禁忌的。若V(π)为空，则说明已经找到了最优解，否则按照相应的工序开工时间由小到大的顺序依次检查V(π)中的移动；采用第一个比原解好的未禁忌的移动，并且在搜索过程中始终记录当前最好的解；若每个未禁忌的移动得到的解都不好于原解，则选择其中最不差的移动；若不存在未禁忌的移动，也就是V(π)所有的移动都被禁忌了，则采用移动集中禁忌“最久”的移动vo，并对禁忌表作出修改：在禁忌表中将vo和比vo禁忌更久的项删除；3)在车间物流畅通没有等待的时候，采用先进入先出和先到先服务的规则，格点状态变化如下： S c ( d ) τ + 1 ( q , t , d , e , wn ) = S c ( d ) τ ( q , t , d , e = 1 , wn + 1 ) S c ( i , j ( i ) ) τ ( q , Q ∈ t , d , e , wn ) if and S c ( d ) τ ( q , t , d , e = 0 , wn ) S c ( d ) τ ( q , t , d , e , wn ) else - - - ( 5 ) 式中：当粒子在原节点c(i，j(i))加工完成，并且目标节点c(d)的加工设备处于空闲状态，粒子下一时步向目标节点运动；同时，原节点c(i，j(i))的状态变化如下： S c ( i , j ( i ) ) τ + 1 ( q , t , d , e , wn ) = S c ( i , j ( i ) ) τ ( q , t = 0 , d = 00 , e = 0 , wn ) S c ( i , j ( i ) ) τ ( q , Q ∈ t , d , e , wn ) if and S c ( d ) τ ( q , t , d , e = 0 , wn ) S c ( i , j ( i ) ) τ ( q , t , d , e , wn ) else - - - ( 6 ) 当粒子处在运输节点、工序处理准备工位节点、工序处理工位节点时，在物流通畅情况下，粒子按流程方向进入下一邻接节点，故有：d＝(i+1，j(i+1))(2)SPT和LPL规则：最短或最长加工时间优先规则在τ＝0时刻将m个最短或最长的工作分配给m台机器；此后，任一台机器空闲，剩下的工作中加工时间最短或最长的将分配给这台空闲机器；PS＝PA，PA＝{k|tk＝min(max)T}(T∈t) S c ( d x ) τ + 1 ( q , t , d , e , wn ) = S c ( d x ) τ ( q , t , d , e = 1 , wn + 1 ) if S c ( d x ) τ ( q , t , d , e = 0 , wn ) S c ( d x ) τ ( q , t , d , e , wn ) else - - - ( 7 ) 式中：PS通过规则选择工件PA，在这里假设各工件加工的时间不相同，T为工件在c(dx)上加工所需的时间的集合，c(dx)为空闲的任一相同属性的机器，k为选定的在c(dx)上加工的粒子。