基于混合蚁群算法的企业车间作业计划问题研究

卢冰原,程八一

(1.南京工程学院 经济管理学院,江苏 南京,211167;2.中国科学技术大学 管理学院,安徽 合肥 230026)

●实务·方法

基于混合蚁群算法的企业车间作业计划问题研究

卢冰原1,程八一2

(1.南京工程学院 经济管理学院,江苏 南京,211167;2.中国科学技术大学 管理学院,安徽 合肥 230026)

文章研究了以最小化制造跨度为目标的,具有模糊加工时间的车间作业计划问题。针对该问题,采用三角模糊数来表征时间参数,并在此基础上构建问题目标函数。之后给出了一种混合蚁群求解算法,将模拟退火算法的全局优化特性嵌入蚁群算法来避免局部最优的问题。最后通过实例验证了算法的有效性。

车间作业计划;蚁群算法;模拟退火算法;组合优化

一、引 言

车间作业计划 (Job-Shop Scheduling,JSS)问题是离散型制造企业生产调度问题的一种简化模型,属于典型的NP-hard问题,至今仍然是研究的热点。目前针对 JSS问题的研究大多集中在理想的确定性环境下,相关参数为确定值。然而现实生产过程中,存在机器因素、人力因素和系统因素的影响,致使包括时间参数和约束条件在内的相关信息存在着模糊性。

在古典 JSS问题的求解算法研究方面,基于知识的方法和算法技术相结合的趋势越来越明显,如遗传算法、禁忌搜索、进化规划、神经网络方法、蚁群算法 (Ant Colony Optimization,ACO)、模拟退火算法 (S imulated Annealing,SA)等[1-2]。1994年,Colorni[3]等人首先将 ACO应用于 JSS问题,但结果较差。Blum和 Samples[4]对 ACO进行了改进并进一步应用在开放式车间调度问题中,改善了近似解的质量。为进一步提高ACO的性能,一些学者将 ACO和其他算法混合利用,取得了较好的效果,Heinonen[5]等采用了局部搜索技术对 ACO方法获得的解进行改进,Kuo-Ling Huang[6]等使用了变换瓶颈机器的方法,并结合禁忌搜索,来提高 ACO的搜索效率。

本文将 JSS问题扩展到接近现实的模糊环境中,用三角模糊数 (Trigangular Fuzzy Number,TFN)来表征时间参数。同时针对 JSS问题,将蚁群算法和模拟退火算法结合起来,给出了一种混合蚁群求解算法 SA-ACO,通过 ACO完成路径的搜索,在迭代过程中不断产生新的可行解,采用 SA在迭代过程中,控制搜索范围,避免搜索过程陷入局部最优。该算法的有效性已经得到实例验证。

二、企业车间作业计划问题模型

在一个规模为 m×n的 JSS问题中,包括待加工的作业集合 J={J1,J2,…,Jn}和机器集合M= {M1,M2,…,Mm}。各作业的工艺路线和作业每道工序的加工时间已知,每道工序都必须在指定的机器上加工,且必须在前一道工序完成后才能开始加工,一台机器最多同时处理一个作业。要求确定各机器上所有作业的加工次序,使得某些加工性能指标达到最优。

为了直观描述 JSS问题,同时和 ACO的实现过程相匹配,本文中采用图模型[2]来表示。在 JSS的图模型中,G=(V,C∪D);V= (O∪σ0,σN+1)。其中,C为有向弧集合,对应同一作业上的不同工序,弧的方向表示工序的先后关系;D是无向弧集合,由无向弧连接的结点对应在同一机器上加工的工序;G中每一条弧的权值为其所对应起点工序的加工时间,两边分别加上不占加工时间的起始顶点σ0和终止顶点σN+1。每个作业包含若干道工序,表示作业 j在机器Mi上加工的工序;O表示所有集合;N表示集合 O中工序的总数;σi表示在一个可行解π中,位于人工蚁搜索路径上的第 i个工序 (0≤i≤N+1)。

要获得JSS问题的可行解,便需要确定各无向弧的方向,即每台机器上工序的先后关系。制造跨度 (makespan)是JSS问题中最常用的性能指标,而对于一个可行解π=(σ0,σ1,σ2,…,σN+1),制造跨度 f(π)就是从源点 σ0到终点σN+1的最长路径。

例如图 1中,G所代表的 JSS问题,|J|=3,|M|=3,N=8,有向弧用实线表示,无向弧为虚线。由图 1可知,作业 1包含两个工序,分别在 M1、M2上加工,对应为、在机器M3上加工的工序共有、两个。表示工序的开始时间、加工时间和结束时间。Sijk、Tijk和Cijk同样用 TFN三元组表示,可通过 TFN函数进行计算。对应三元组中三个参数,有{1,…,3}。

图1 一个 3×3JSS的图模型

对于三角模糊数 T=(to,tm,tp),用 Vω(T)、VL(T)和 VR(T)分别表示 T的全积分和左、右积分值。VL(T)代表 T的乐观状态,VR(T)代表 T的最坏可能,则 T的全积分 Vω(T)可定义为 VL(T)和 VR(T)的加权和[7-8],即 Vω(T)=ωVL(T)+(1-ω)VR(T),ω是乐观系数,ω∈[0,1]。μ(t)为 T的隶属函数。

三、SA-ACO混合算法

ACO是一种应用于组合优化问题的启发式搜索算法,它充分利用蚁群行为中所体现的正反馈机制进行求解,同时利用分布并行计算方式在全局的多点进行解的搜索,但存在着容易陷入局部最优的问题。SA在局部搜索技术的基础上,增加了概率控制,很好地避免了局部搜索方法容易进入局部优化的情形。在 SA-ACO执行中,对于 ACO每次迭代得到的结果,通过 SA从中选择优秀解,然后对这些优秀解的路径进行激励。随着迭代次数增加,模拟退火的温度降低,状态逐渐趋于稳定,每次迭代所接受的优秀解减少,算法执行趋于收敛,在达到终止条件时,搜索过程结束。

(一 )初始化

在 SA中,相关参数有:初始温度 T0,T的衰减系数 B;ACO的参数设置主要包括:控制参数α、β,最大迭代数 Im,人工蚁数量m0。在执行搜索过程之前,人工蚁的位置均在初始结点σ0处。

(二)信息素更新

工序加工时间用 TFN表示,制造跨度 f(π)也是 TFN,表示为 Cmax=(maxjmaxi(Cij)),Cij=Sij+Tij。 Sij、Tij和 Cij分别

在搜索过程中,人工蚁从当前结点σi移动至后续结点σj(0≤i,j≤N+1),σj的选择依据下属的伪随机比例状态迁移规则:

其中,q∈(0,1),为随机数;q0∈(0,1)为预设的数;α、β表示人工蚁对路径的选择权重,α表示人工蚁对经验的利用,β表示独立探索 ;τ(σi,σ)为弧 (σi,σ)上信息素浓度 ;η(σ)为(σi,σ)上的启发式信息值;J(σi)为结点σi处的可行路径集合,其约束包括作业约束和机器加工约束。除按 (1)选择路径之外,人工蚁以概率 (1-q0)进行有偏向的搜索,s为选择的随机结点,人工蚁选择路径 (σi,s)的概率为:

人工蚁在搜索的过程中,路径上的信息素发生局部更新,更新规则为:

在 (3)式中,传统 ACO将ρ设置为常数,这样对τ(σi,σj)无法进行动态约束,容易导致算法的过早停滞,降低了搜索空间。本文中采用动态ρ值的设置:ρ=kτ(σi,σj)(k≥0,为常数)。在所有人工蚁到达σN+1之后,首先更新全局最优解π＊,其制造跨度为 f(π＊),然后对信息素进行全局更新:

上述的信息素更新结束后,调整模拟退火的温度:T=BT。在迭代过程的前期,得到优化的路径较多,解决了非优秀解路径上信息素过多累积的问题,在算法执行的后期,Metropolis准则的约束增强,除了当前最优解π＊,其它得到激励的路径明显减少,强化了算法向全局最优解集中的趋势。

(三)搜索终止规则

若迭代次数满足 I=Im,算法的迭代过程结束。得到的π＊为最终解。然后根据π＊确定各机器上的加工顺序,从而求出制造跨度 f(π＊)。

四、案例分析

以图 1中的 JSS问题为例,在 ACO的参数体系中,本文采用 m0=100,α=β=10,q0=0.8,并对模拟退火的参数进行调节,随着问题规模增大,迭代次数增多,模拟退火的初始温度T0也相对较高,衰减系数 B较大。若各工序加工时间如表 1所示,则各机器上的加工序列为;制造跨度 f(π＊)=(13.5,15,17.3), Vω(f(π))=14.8,ω =0.7。当 T0=20;B=0.90时 ,达到最优解的平均迭代次数为 52.2。

SA-ACO算法在解决上述规模较小的问题时,能得到最优解。针对对于较大规模的问题,本文选择 JSP的部分基准问题算例 9,将其中的加工时间 t由确定值调整为三角模糊数(δ＊ t,t,φ＊ t),令δ=0.9,φ=1.15。然后将结果与传统 ACO方法 10进行对比,为对比方便,表中数据均为三角模糊数的中间数。实验中采用和传统 ACO方法相同的参数体系:q0= 0.8,m0=100,Im=200,运行结果的对比数据见表 2。表中数据说明,在解决大规模的 JSS问题时,随着机器数和作业数的增加,SA-ACO在路径的均衡搜索能力上的优势更为明显,与最优解的偏差更小。

表2 SA-SCO与传统ACO实验结果的比较

五、结 论

本文对具有模糊加工时间的 JSS问题进行了研究,用三角模糊数来表征时间参数,并给出了相应的目标函数。在对JSS问题求解方面,本文在 ACO算法的基础上,结合 SA跳离局部解空间的特性,给出的 SA-ACO算法有效地克服了 ACO局部最优的缺陷,改善了 ACO的收敛性能。实验表明,相对于传统 ACO,SA-ACO在处理 JSS问题时有明显的优势。对离散型制造企业来说,有效的车间作业计划是其实现先进制造和提高生产效益的基础和关键。该算法有助于构造更加高效、鲁棒的车间作业计划,并可适用于现实的模糊生产环境,以提高企业生产运作中的智能决策水平,从而提高企业竞争能力。

[1]Garey E L,Johnson D S,Sethi R.The complexity if flowshop and job-shop scheduling[J].Mathematical Operation Research,1976,1:117-129.

[2]Blazewicz J,Presch E,SternaM B.Disjunctive graph machine representation of the jobshop scheduling problem [J]. European Journal ofOperational Research,2000,127 (2) :317-331.

[3]Colorni A,Dorigo M,Maniezzo V,et al.Ant system for job shop scheduling[J].Belgian Journal ofOperations Research,1994,34:39–53.

[4]Blum C,SampelsM.An ant colony optimization algorithm for shop scheduling problems[J].Journal ofMathematical Modelling and Algorithms,2004,3:285–308.

[5]Heinonen J,Pettersson F.Hybrid ant colony optimization and visibility studies applied for job shop scheduling problem [J].AppliedMathematics and Computation.In Press.A-vailable,2006,10:18.

[6]Kuo-Ling Huang,Ching-JongLiao.Ant colony optimization combined with taboo search for the job shop scheduling problem[J].Computers&Operations Research.In Press Available,2006,8:22.

[7]Ish iiH,Tada M,Asuda M T.Two scheduling problems with fuzzy due dates[J].Fuzzy Sets and System's,1992, 46(3):339-347.

[8]Feng-Tse Lin.Constructiong a job-shop schedulingmodel based on imprecise data[C].the IEEE international conference on fuzzy system,2003.

[9]JSS.Benchmark Problem [EB/OL].[2004-04-20] ftp://mascmga.Ms.ic.ac.uk/pub/jobshop1 (2). txt.

[10]Boryczka U.Ant Colony System for JSS[J].Lecture Notes in Computer Science,2004,33(5):296-305.

[责任编辑:余志虎 ]

The Research of Enterprise Job-shop Scheduling Problem Based on Hybrid Ant Colony Optim ization

LU Bing-yuan1,CHENG Ba-yi2
(1.School of Econom ics and M anagem ent,Nanjing Institute of Technology,Nanjing211167,China;2.School of M anagem ent,University of Science and Technology of China,Hefei230026,China)

This paper studies the job-shop scheduling problem which has fuzzy operation time and which aims at min imized makespan.For this problem,it introduces triangle fuzzy number to denote time parameters,on which the aim function is constructed.After that,a hybrid ant colony optimization is proposed to get perfect scheduling scheme,which can prevent premature opt imization by inserting the global opt imization ability of SA into ACO.Moreover,some examples are described to approve its effectiveness.

job-shop scheduling;ant colony optimization;simulated annealing;combinatorial optimization

F273

A

1007—5097(2010)11—0147—03

10.3969/j.issn.1007-5097.2010.11.035

2009—09—04

江苏省教育厅高校哲学社会科学基金项目 (09SJD630036);国家自然科学基金项目 (70671096)

卢冰原 (1977—),男,安徽阜阳人,副教授,博士,研究方向:商务智能;

程八一 (1981—),男,安徽安庆人,博士研究生,研究方向:商务智能。