基于蚁群算法的虚拟企业生产任务调度优化研究

赵 强,周 敏

(武汉科技大学机械自动化学院,湖北武汉,430081)

虚拟企业(VE)是指分布在不同地区的多个常规企业利用信息和网络技术而快速响应市场需求与变化所组建的动态联盟,也是组织、人力、技术和信息等资源在完善网络组织结构基础上的有效集成[1-2]。当某企业面临资源缺乏或能力限制而导致无法独立完成某项生产任务时,就可以以盟主企业身份通过构建VE来完成该任务。一般来说,盟主企业首先将生产任务分解、归并为若干个子任务,然后采取招标或选择代理(V E-broker)等方式选择适宜的合作企业承担相应的子任务,通过合作企业共同努力最终完成整个生产任务。生产任务调度关系到VE运作的成败,已成为VE研究的一项重要内容。Wu[3]等提出了任务分解、归并的具体方法,该方法为VE生产任务调度奠定了基础;高阳等[4]建立了基于多智能体的V E生产任务调度模型,并利用集成优化算法来自动处理调度优化问题,但该模型未体现VE生产任务调度的层次性;苏平等[5]建立的VE生产任务调度模型仅考虑了生产任务的完成时段,且模型较为简单;高阳等[6]指出VE生产任务调度优化问题类似于Job Shop问题,结合生产任务之间的约束关系,建立了生产任务调度优化模型,但该模型未考虑合作伙伴自身的生产任务集。VE各合作伙伴是一个独立的实体企业,其自身也存在生产任务,该生产任务是影响VE调度层优化的重要因素,而这一重要因素在目前的相关研究中却往往被忽视。为此,本文针对VE调度层的优化问题,给出了VE生产任务调度的层次框架(包括VE全局调度与合作伙伴局部调度两个层次),综合考虑VE生产任务的时序逻辑关系、作业时间和生产任务集等影响因素,建立以任务总作业时间最小化为目标的数学模型,并基于蚁群优化求解算法,提出VE生产任务调度优化方案。

1 层次框架

为更好地完成各个生产任务,需要从全局和局部两个角度对生产任务进行调度。由于V E生产任务调度涉及多个合作伙伴,因此VE生产任务应分为VE调度和合作伙伴调度两个层次,如图1所示。

图1 VE生产任务调度层次框架Fig.1 Level framework of production tasks scheduling in VE

VE调度层是全局调度层,主要由盟主企业负责,其工作内容包括生产任务的分解、任务时序关系的确立以及合作伙伴的选择。从全局视点出发对生产任务进行优化调度,可确定各生产任务的作业时段,以满足交货期预定目标的要求。合作伙伴调度层是局部调度层,其调度目标是力求在V E调度层所规划的作业时段内完成各个生产任务。合作伙伴调度层由各个合作伙伴负责,具体的工作内容包括合作伙伴将其承担的生产任务进一步分解为子任务,并在优化的基础上,确定各子任务作业时段和加工作业。通过合作伙伴的协同作业,共同完成VE生产任务。

由于V E全局优化与合作伙伴局部优化存在耦合关系,因此它们之间不可避免地会出现冲突问题。如某一生产任务由于合作伙伴加工设备出现故障或出现紧急生产任务等原因,使得优化后的调度方案仍无法在预定时段完成该生产任务作业时出现冲突。冲突问题的解决需要盟主企业与合作伙伴协商解决,可放松某些生产任务的约束条件或缩短某些生产任务的作业时间,或者引入新的资源,重新选择承担某生产任务作业的合作伙伴,在相互协调的基础上,提出VE全局调度或局部调度优化方案。V E生产任务调度是一个持续协调和优化的过程。

2 优化模型

2.1 问题提出

在V E全局优化生产任务调度之前,盟主企业先将总任务分解为若干具有时序关系的各个生产任务(生产任务之间用活动网络图来表示)。在完成合作伙伴局部选择的基础上,根据每个伙伴自身已确定的生产任务信息、完成VE全局优化各个生产任务所需作业时间和生产任务之间转运时间(将运输和资源的调整时间,统称为转运时间)等信息来进行生产任务调度优化,其目标是在兼顾生产任务时序约束关系、生产任务作业时间和各个伙伴自身任务集等信息前提下,使得生产任务调度方案既能保证产品交货期要求,也能使得所有生产任务总的作业时间最小化。VE全局调度优化完成后,各个生产任务的作业时段也就初步确定。随后合作伙伴将自身所承担的各个生产任务再次分解,并根据生产任务分解、设备占用等信息进行局部调度方案的优化,其目标是保证生产任务在已规划的时段内完成作业。由于VE全局调度与合作伙伴局部调度的优化模型类似,且VE生产任务调度的关键在于全局调度优化,因此以下仅讨论V E全局调度优化模型及其求解。

2.2 条件假设

以最小化生产任务作业时间为目标,建立了VE全局调度层优化模型。该优化模型的假设条件如下:①每个生产任务的开始作业时间应遵循时序逻辑的约束关系,在生产任务执行过程中不容许中断;②考虑到伙伴自身生产能力和条件限制,在生产任务执行过程中,一次能且仅能执行一个生产任务;③生产任务的起始作业时间为0。

2.3 模型符号

VE全局调度层优化模型的符号设定如下:P为合作伙伴集,m为合作伙伴总数,P={P1,P2,…,Pk,…,Pm},k∈[1,m];T为生产任务集,n为生产任务总数,T={T1,T2,…,Ti,…,Tn};Rk为Pk承担的生产任务集,Rk={T1,…,Ti,…},i∈[1,n],且各个伙伴任务集满足Rk∩Rk′=φ(k,k′∈[1,n]),R1∪R2∪…∪Rm=T;H为满足时序约束关系的所有生产任务对集合;Fi为Ti的紧前生产任务集,(Ti′,Ti)∈H,Ti′∈Fi,i′∈[1,n];zi′i为Ti′～Ti的转运时间,当Ti′与Ti由同一伙伴完成时,zi′i=0;TBi为由Pk承担的生产任务集,且作业顺序位于Ti紧前的一个生产任务,TBi∈Rk;si为Ti的开始作业时间;ti为完成Ti所需的作业时间;fi为Ti的结束作业时间;Mk为Pk先于VE组建前已确定的生产任务集,用时间段表示,记为Mk={[m1,m2],…};D为产品交货期。

2.4 模型描述

基于以上假设条件及符号设定,VE全局生产任务优化调度模型描述如下:

式(1)为目标函数,即生产任务总的作业时间,优化调度方案力求最后一个生产任务尽早完成;式(2)为某生产任务开始作业时间,必须在其所有的紧前生产任务转运完成后才能够开始,即满足作业逻辑顺序约束;式(3)为某生产任务开始作业时间,必须在由同一个伙伴完成且作业顺序位于该生产任务紧前的生产任务完成后才能够开始,即满足资源约束;式(4)为生产任务开始作业时间与完成作业时间的关系;式(5)为合作伙伴执行V E全局生产任务时,不能与自身已确定的生产任务相冲突;式(6)为交货期约束。

3 蚁群算法优化求解

蚁群算法[7-8]是一种模拟蚂蚁觅食行为的进化算法。蚁群算法对离散组合优化问题有较好的求解效果。因此,以下采用蚁群算法对VE全局生产任务调度问题进行优化求解。

3.1 算法设计

3.1.1 约束矩阵的建立

蚁群算法在求解VE全局生产任务调度时,每次迭代中均要求每只蚂蚁从起始节点开始,遍历所有生产任务节点,最后到达终止生产任务节点,蚂蚁走过的节点顺序便是构造的解。由于生产任务之间存在时序逻辑关系,因此只有建立生产任务间的约束矩阵,才能有效保证构造解的合理性,进而保证VE全局生产任务调度优化方案的合理性。可采用3个常量来建立VE全局生产任务间的时序逻辑约束矩阵,并以生产任务Ti与Tj为例加以说明。0表示Ti与Tj之间不存在时序逻辑约束关系;1表示Ti与Tj之间存在时序逻辑约束关系,且Ti先于Tj开始作业;2表示Ti与Tj之间存在先后顺序关系,且Ti后于生产任务Tj开始作业。VE全局生产任务间的时序逻辑约束矩阵A(A的行与列的编号均为生产任务编号)描述如下:

3.1.2 状态转移概率

蚂蚁从一个生产任务节点i转向下一个生产任务节点j时,其转移概率计算式为

3.1.3 信息素更新

在第t次迭代中,蚂蚁按式(8)的选择规则遍历所有生产任务节点,构造出一个调度序列,即得到所有生产任务的作业顺序。在第t+1次迭代开始前,需要对信息素进行更新,其更新式为

式中:Δτij=1/fmax(k),其中fmax(k)为蚂蚁k在第t次迭代后得到的生产任务总作业时间,d;ρ为信息素的挥发因子。

3.2 求解步骤

VE全局生产任务调度优化的求解步骤如下:

(1)初始化:①建立生产任务时序约束矩阵;②参数初始化,即初始化外激素信息矩阵、设置外激素消逝速度等参数;③在虚拟起始点生成一定数量的一代蚂蚁。

(2)迭代直至满足预定迭代次数:①每只蚂蚁都可根据约束矩阵判断生产任务节点;②蚂蚁按照式(8)进行状态迁移;③完成对所有生产任务节点的遍历;④按照式(9)进行信息素更新;⑤记录最优的生产任务调度优化方案。

(3)输出最优的生产任务调度方案。

4 实例分析

4.1 应用实例

由5个合作伙伴(编号为P1～P5)组成的V E共同完成某汽车起重机产品的制造任务,交货期为100 d。该制造任务可分解为包括汽车起重机的起升机构制造、回转机构制造、变幅机构制造以及装配调试等23个生产任务,生产任务之间活动网络如图2所示。生产任务分工后,P1～P5分别完成生产任务集为ET1～ET5:ET1为{T2,T6,T8,T15,T22},ET2为{T5,T11,T20,T21,T23},ET3为{T10,T14,T18},ET4为{T3,T7,T12,T16,T17},ET5为{T4,T9,T13,T19,T24}。由图2可看出,圆角矩形框下的数字是合作伙伴完成该零部件生产任务所需的作业时间,箭头线上的数字标注代表转运时间(当生产任务由同一伙伴完成时,转运时间为0)。若生产任务的开始时间设定为0,则P1已确定的生产任务集为{[40,60]},P2已确定的生产任务集为{[65,75]},P3已确定的生产任务集为{[15,35]},P4已确定的生产任务集为{[40,50]},P5已确定的生产任务集为{[68,75]}。综合考虑上述已知信息,V E优化的生产任务调度方案是求解最小化起重机产品的制造完工时间。

4.2 调度优化

综合以上给定信息,采用蚁群算法进行优化求解。设定蚂蚁数量为20,α=β=0.9,ρ=0.9,迭代次数为200。VE全局优化后的汽车起重机生产任务调度方案如图3所示(生产任务开始时间设定为原点)。在该调度方案下,生产任务T24～T2的制造和转运时间总计为83.5 d,加上10 d的产品装配和调试时间,整个汽车起重机产品制造生产任务可在93.5 d内完成,满足了客户交货期要求。

图2 汽车起重机生产任务活动网络Fig.2 Activity network diagram of production tasks of truck crane

图3 VE全局生产任务调度方案Fig.3 Global scheduling plan of production tasks in VE

4.3 调度调整

在生产任务作业初期,合作伙伴P3由于企业自身生产任务的调整使得在时间段[35,60]以内生产任务较重,合作伙伴P3不能在上述时段对生产任务T14进行作业,因此需要对生产任务调度方案进行适当调整。在不影响其他合作伙伴生产任务作业的前提下,VE全局优化后的汽车起重机生产任务调度方案如图4所示。在该调度方案下,生产任务T14的作业时段由[35,45.5]调整为[21.5,32],并且生产任务T2～T23的制造和转运时间总计仍为83.5 d,也满足了产品的交货期要求。

当某生产任务延期完成时,可根据VE全局生产任务的延迟程度对生产任务调度方案进行适当的调整。若生产任务T22延迟2 d完成,则对合作伙伴P4而言,可将其承担的生产任务作业时间适当延迟。VE全局生产任务调整后的汽车起重机生产任务调度方案如图5所示。在该调度方案下,生产任务T2～T23的制造及转运时间总计为84 d,满足了产品交货期要求。

图4 T14作业时段调整后的VE全局生产任务调度方案Fig.4 Global scheduling plan of production tasks in VEafter adjusting operating time of T14

图5 T22作业延迟的VE全局生产任务调度方案Fig.5 Global scheduling plan of production tasks in VE under operating delay of T22

当生产任务T22延迟2 d完成,并且合作伙伴P4由于企业自身生产任务的调整使得在时间段[26,50]以内无法对其承担的生产任务进行作业时,V E全局生产任务优化后的生产任务调度方案如图6所示。在该调度方案下,生产任务T2～T23的制造和转运时间总计为96.5 d,无法满足产品交货期要求。为不影响产品交货期,合作伙伴P4需要通过引入合作企业或新增加工设备等方法来缩短生产任务T12或T16的作业时间,并将完成自身生产任务的时间段控制在[40,50]以内,以保证VE全局生产任务调度方案进度的执行。

图6 P4任务集调整的VE全局生产任务调度方案Fig.6 Global scheduling plan of production tasks in VEafter adjusting task sets of P4

基于上述方法,并结合各个生产任务作业的实际情况,对VE全局生产任务调度方法进行优化和调整,从而保证了汽车起重机制造生产任务的按期完成。

4.4 算法有效性的验证

以文献[6]提供的实例,我们验证了蚁群算法求解V E全局生产任务调度优化问题的有效性。VE全局优化后的生产任务调度方案如图7所示。在该生产任务调度方案下,求得制造周期为99 d,与文献[6]给出的VE全局优化结果相同。本研究运用蚁群算法在Pentium IV PC机上的平均求解时间仅为2.6 s,明显优于文献[6]给出的6～8 s的平均求解时间。因此,蚁群算法可有效地求解V E全局生产任务调度优化问题。

图7 不考虑合作伙伴任务集的VE全局生产任务调度方案Fig.7 Scheduling plan of production tasks in VEafter neglecting partner’s task sets

5 结语

生产任务调度是典型的NP难题。本文描述了VE生产任务调度的层次框架(包括V E全局调度层和合作伙伴局部调度层)。VE生产任务调度层主要内容是从全局视点出发对生产任务进行优化,在满足交货期的预定目标前提下,达到最小化生产任务的作业完成时间;而合作伙伴调度层主要内容是力求在VE调度层所规划的作业时段内完成各个生产任务。针对VE生产任务调度层的优化问题,建立了以生产任务总的作业时间最小化为目标的优化模型,并给出了蚁群求解算法。通过某汽车起重机制造实例验证了优化模型及其求解算法的有效性,并针对实际情况给出了VE生产任务调度调整的具体方案。

[1] Nagel R,Dove R.21stcentury manufacturing enterprise strategy:an industry-led view[R].Bethlehem:Iacocca Institute,Lehigh University,1991:122-134.

[2] Abbe M.Virtual organization[J].Communication of the ACM,1997,40(9):30-37.

[3] WuNQ,Sun J.Grouping the activities in virtual enterprise paradigm[J].Production Planning and Control,2002,13(4):407-415.

[4] 高阳,周伟.基于多Agent的虚拟企业调度研究与实现[J].中国机械工程学报,2004,15(11):978-982.

[5] 苏平,伍乃骐.一种可重构制造系统的生产计划方法[J].计算机集成制造系统,2003,9(3):189-193.

[6] 高阳,江资斌.用混合遗传算法求解虚拟企业生产计划[J].控制与决策,2007,22(8):931-934.

[7] Marco D,Vittorio M,Alberto C.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Cybernetics,1996,26(1):29-41.

[8] Marco D,Luca M G.Ant colonies for the traveling sales-man problem[J].Bio Systems,1997(43):73-81.