改进蚁群算法在车间作业调度中的应用研究

第31卷　第2期2009年4月三峡大学学报(自然科学版)

J of China Three G orges Univ.(Natural Sciences )Vol.31No.2Apr.2009

收稿日期:2008209223

通讯作者:吴正佳(1964-),男,教授,博士,主要研究方向为计算机集成制造系统,智能算法理论研究等.

改进蚁群算法在车间作业调度中的应用研究

张利平　吴正佳　王　魁　王　文

(三峡大学机械与材料学院,湖北宜昌　443002)

摘要:研究了基于机器最短加工时间的一类车间作业调度问题,建立了多约束的数学模型,为解决

蚁群算法收敛性差和易陷入局部最优的问题,提出了一种基于插入移动的领域搜索方法,并使用该领域搜索方法嵌入蚁群算法.采用国际著名的benchmark 测试集F T06进行了实例验证,计算结果表明,该算法可收敛到最优值55,且最优值、平均值和标准差都优于蚁群算法,标准差远远小于蚁群算法.

关键词:车间作业调度;　蚁群算法;　邻域搜索中图分类号:TP278:TP312　　　文献标识码:A 　　　文章编号:16722948X (2009)022*******

Application of Improved Ant Colony Algorithm to JSP

Zhang Liping 　Wu Zhengjia 　Wang Kui 　Wang Wen

(College of Mechanical &Material Engineering ,China Three G orges Univ.,Yichang 443002,China )Abstract 　The job shop p roblem by t he SP T rules is researched.And t he mat hematical model wit h multi 2re 2stricted co ndition is set up.In order to solve ant colony algorit hm convergence and plunging local optimal val 2ue ,an improved ant colony algorit hm which bases on interval number is developed.It uses local search to im 2prove t he result in every circle.And it is examined by means of t he international famous benchmark set s F T06.The comp utation result s show t hat t his algorit hm can get t he optimal value 55.Optimal value ,average value and standard deviatio n are better t han ant colony algorit hm.The standard deviation in improved ant col 2ony algorit hm is much smaller t han t he o ne in ant colony algorit hm.K eyw ords 　job shop problem ;　ant colony algorit hm ;　local search

车间生产过程的作业调度问题是制造系统、运筹技术、管理技术与优化技术发展的核心,有效的调度方法与优化技术的研究和应用已成为先进制造技术实践的基础和关键[1].车间作业调度问题(Job 2Shop Problem ,J SP )是所有生产调度中最复杂、最困难、且

更具一般性的问题之一,也是最典型、最困难的组合优化问题之一.因此,该问题的研究一直是企业界与学术界关注的焦点问题,众多学者应用不同的求解算法对J SP 问题做了大量的研究工作,并提出了不同的调度理论与优化算法,但由于J SP 问题的复杂性与离散性,对该问题的求解尚未形成一个完整的理论体系,提出的各种优化算法在求解过程中也会出现早

熟、收敛于局部最优解等不足.蚁群算法是一种模仿

蚁群觅食行为的智能算法,近年来在J SP 问题上得到了广泛应用[2].鉴于蚁群算法的成功应用,文章提出了一种高效的蚁群调度算法,基于典型算法的试验,验证了所得算法的可行性和优越性.

1　JSP 的数学模型建立

许多学者在研究J SP 问题时,对问题的描述往往是有差别的,不失一般性,J SP 问题描述为n 个工件在m 台机器上加工,每个工件包含m 道工序,且已知每道工序在各自对应机器上的加工时间[3].J SP

问题

? 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. a9360122192e45361066f517

满足的约束条件为:(1)每个工件的下一道工序只能

在上一道工序完成后才能开始加工;(2)每个工件都须经过m 台机器加工;(3)每台机器在同一时刻只能加工某一工件的一道工序;(4)每个工件加工的优先级相同.

J SP 问题的评价标准较多,文章以所有机器完工时间最短为优化目标.从而,依据最短加工时间这一优化目标建立的数学模型如下:

目标函数:

min (max (T E ))

(1)　　约束条件:

S ij +t ij ≤S i (j +1)

(2)F ij k +t ij ≤F ghk

(3)式中,T E 为在满足约束条件下,一种调度方案对应的每一台机器结束加工的时间;t ij 为工件i 的第j 道工序的加工时间;S ij 为工件i 的第j 道工序的起始加工时间,i =1,2,…,n;j =1,2,…,m ;F ij k 为工件i 的第j 道工序在机器k 上加工的起始时间,i ,g =1,2,…,n ,i ≠g;j ,h =1,2,…,m .

2　JSP 的改进蚁群算法设计

蚁群算法(ant colony algorit hm )最初是由意大利学者M.Dorigo 等提出的一种基于种群的启发式仿生进化系统.蚁群算法最早用于解决著名的旅行商问题(Traveling Salesman Problem ,TSP ),采用了分布式正反馈并行计算机制,易于与其他方法结合,并具有鲁棒性(即对模型稍加修改便可以应用于其它问题)[4].如今,这一新兴的仿生优化算法已经成为人工智能领域的一个研究热点,目前对其研究已渗透到多个应用领域,在国内外许多学术期刊和重要国际会议上,蚁群算法已成为交叉学科中一个非常活跃的前沿性研究问题.

根据信息素更新策略的不同,M.Dorigo 提出了3种不同的基本蚁群算法模型,分别称之为Ant 2Cy 2cle 模型、Ant 2Quantity 模型及Ant 2Density 模型[5],文章提出采用基于插入移动的领域搜索的改进蚁群算法,提高蚁群算法的收敛性和跳出局部最优解.2.1　算法实现说明

由于J SP 问题讨论的是工件在机器上的排序,工序之间受技术约束条件的限制,不如TSP 与蚂蚁的觅食过程那样具有相似性.因为J SP 的解是所有工序的工件号的置换排列,也就是说每只蚂蚁构造一个解的过程就是在满足工件的技术约束和机器能力约束的情况下,从左至右地为解的每个位置选择一个工

序,同时将该工序安排到相应机器的相应位置的过程.因此,文章认为用蚁群算法求解J SP 时蚂蚁搜索过程如下.

对于J SP 问题,先用{1,2,…,n}对工序进行编码,并设置3个工序集合:工序集合{1,2,…,n},可选择的工序集合allowed k ,禁忌表工序集合tabu k .在搜索之初,由于工件的工艺约束条件的限制,蚂蚁k 允许选择的工序集合allowed k Α{1,2,…,k}是由所有工件的第一个工序所组成的集合,当蚂蚁k 为解的第一个位置选择工序时,从allowed k 中随机地选择,记录下该工序,然后将该工序放入禁忌表tabu k 中,同时将该工序安排到相应机器相应的位置上,并且将该工序同属一个工件的紧后工序放入allowed k 中替代该工序,依次搜索,直至所有工序都被选择,即禁忌表工序集合tabu k 的工序与工序集合{1,2,…,k}相同,从而蚂蚁完成一轮搜索.

针对蚁群算法易早熟,陷入局部最优解和收敛速度慢等不足,文章对已构建的解进行领域搜索,在每次循环中,领域搜索在较优集合的领域中进行,从而改善蚁群算法的性能.邻域搜索的构建方式有3种:(1)交换位置i 和i +1的两个相邻的工序,i =1,2,…,n -1(交换移动);(2)交换位置i 和j 上的工件,

i ≠j (互换移动);(3)将位置i 上的工件移动到位置j

上(插入移动).根据Thomas st utzle 的仿真结果,插入移动构建的邻域得到的解效果最好[6].插入移动的具体定义如下:令(i ,j )是一对位置,通过将位置i 上的工件π(i )插入到位置j 来得到新的排列π3.如果i

π(j ),π(i ),π(j +1),…,π(n ))

如果i >j

πnew =(π(1),…,π(i -1),π(i ),π(j ),

…,π(i -1),π(i +1),…,π(n ))　　因此,在每次迭代过程中,采用插入移动更新当前构建的最优解,然后更新全局信息素,进入下一次迭代.2.2　算法步骤步骤1:参数初始化,令循环次数N c =0,设置最大循环次数为N cmax ;

步骤2:工件编码;按照工件的工序进行编码,每个工序用一个数字表示,记为{1,2,…,n};

步骤3:初始化ant 个蚂蚁,将ant 个蚂蚁随机置于可选择的工序集合allowed k 的某个工序上,并添加到禁忌表工序集合tabu k 中,令初始信息素τij =1,且

初始时刻Δτij =0;

67三峡大学学报(自然科学版)　　　　　　　　　　　　　　2009年4

月

? 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. a9360122192e45361066f517

步骤4:循环次数N c←N c+1;

步骤5:蚂蚁的禁忌表索引号k=1;

步骤6:蚂蚁数目k←k+1;

步骤7:蚂蚁根据式(4)选择下一步路径:

j=argmax u∈allowed

k

(τiuαηiuβ)if q

P k ij ot her

(4)

其中,q为平均分布在[0,1]之间的随机数,q0为[0, 1]上的参数,α,β为两个参数,分别控制信息素和启发信息的相对重要程度.ηk ij表示(i,j)的启发信息,用最早开始时间表示.τiu表示工序i到工序u的信息素值;P k ij表示按状态转移公式概率选择

P k ij=

τ

ij

αη

ij

β

∑

s∈allowed k

τ

ij

αη

is

β

if j∈allowed k

0ot her

(5)

这种选择方式,实际上进行了两次选择,首先产生一个[0,1]均布随机数q,如q小于预先设定的参数q0,则按照式(4)选择路径,否则按式(5)选择.

步骤8:根据式(4)和(5)选择工序j并前进,j属于可选择的工序集合allowed k,修改禁忌表指针,即将蚂蚁移动到工序j,把工序i移动禁忌表中,将工序i的后工序放入allowed k中替代该工序;

步骤9:若工序集合{1,2,…,n}没有遍历完,即k

步骤10:领域搜索.根据工序的技术约束和机器约束进行插入移动,若存在更优方案,用更优方案替代原方案,否则维持原方案.

步骤11:更新每条路径上的信息量

τk

ij=

ρτk ij+(1-ρ)Δτij

Δτ

ij=Q/T E蚂蚁k过路径(i,j) 0ot her

式中,ρ为信息素挥发系数;T E为蚂蚁k所走路径对应的机器最短加工时间;Δτij为信息素增量;Q为常数.

步骤12:若满足结束条件,即如果循环次数N c≥N cmax,则循环结束并输出程序计算结果,否则清空禁忌表并跳转到步骤4.

3　基于典型算例的应用研究

结合上述定义的改进蚁群算法,将其应用于J SP 问题benchmark集F T06问题[7].其中,参数如下:种群规模为ant=20,N cmax=1000,ρ=0.85,q0=0.4, Q=55.为了对比改进蚁群算法的性能,分别采用基本蚁群算法和改进算法对F T06问题计算10次,计算所得结果的最优值、平均值和标准差见表1,图1和图2分别给出了改进蚁群算法的收敛曲线图和最优解甘特图

.

表1　改进蚁群算法对比结果

FT06

最优解

改进蚁群算法

最优值平均值标准差

蚁群算法

最优值平均值标准差555555.10.315657.9 3.82

由表1可知,F T06问题[3]的机器最短加工时间为55,改进的蚁群算法可有效地逼近最优解,而蚁群算法没能得到最优值;另外,改进蚁群算法求解的平均值与问题的最优值基本接近,而蚁群算法求解的平均值与问题的最优值相差较大;第3,改进蚁群算法的标准差与为0.31,而蚁群算法求得的标准差为3.82,是改进蚁群算法的10倍.从图1可以看出,改进蚁群算法在迭代次数为409次时便收敛于最优解.

这说明改进蚁群算法有更高的求解质量和收敛性,可有效跳出局部最优解,且有较强的鲁棒性.

4　结　论

将改进蚁群算法应用到J SP问题,并

采用

benchmark测试集F T06问题进行了实例验证,对比

蚁群算法的最优值、平均值和标准差,改进的蚁群算

法在解决该类J SP问题是有效可行的,并可收敛到最

77

第31卷　第2期　　　　　　　　　　　　　张利平等　改进蚁群算法在车间作业调度中的应用研究? 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. a9360122192e45361066f517

优解.目前,国内外学者对J SP问题研究较多,也较简单化,还不能满足实际生产中的需要,文章采用改进的蚁群算法求解J SP问题,为求解该类问题提供了新的方法,但仍有很多复杂的问题有待进一步研究,如柔性J SP问题和随机性J SP问题等.

参考文献:

[1]　何　霆,刘　飞,马玉林等.车间生产调度问题研究[J].

机械工程学报,2000,36(5):972102.

[2]　Lin D,MAR KIS V.On2line Parameter Estimation for a

Failure Prone System Subject to Condition Monitoring

[J].Journal of Applied Probability,2004,41(1):2112 220.[3]　葛茂根.基于微粒群优化的车间生产作业调度方法研究

[D].合肥:合肥工业大学,2006.

[4]　李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大

学出版社,2004:9.

[5]　段海滨.蚁群算法原理及其应用[M].北京:科学出版

社,2005.

[6]　Tho mas Stutzle.An A nt App roach to the Flow Shop

Problem[R].Aachen,Germany:Proceedings of Europe2 an Congress on Intelligent Techniques and Soft Compu2 ting,1998.

[7]　潘全科,王文宏,朱剑英.一类解决Job Shop问题的改进

遗传算法[J].中国机械工程,2006,17(8):8662869.

[责任编辑　张　莉]

(上接第50页)

续表2　船队最大系缆力成果表(单位:t)

泊位船闸运行方式

首横

左　　　　右

首纵

上　　　　下

尾横

左　　　　右

左靠船墩

左右线同时充水 1.42 1.34 2.41 4.30 1.43 1.33左右线错时充水(12min) 1.35 1.30 1.47 2.36 1.23 1.26

3左靠船墩

左右线同时充水 2.02 1.55 2.29 5.91 1.39 1.63左线单充 1.83 1.10 1.43 3.53 1.34 1.22左右线同时充水(131～145m) 1.34 1.24 2.14 5.16 1.20 1.23

3闸前60m

左右线同时充水 1.78 1.10 1.78 3.96 1.49 1.12左右线同时充水(131～145m) 1.360.93 1.63 3.26 1.37 1.13　　注:二级充水125.25～145m,渠底高程130～139m,H=135m,船队4×3000t,3为μ139m.

3　结　语

该套全自动化控制系统,在1∶40长江三峡水利枢纽连续双线五级船闸模型试验中应用情况良好,其对阀门的启闭速度控制精确,试验过程中的各种水力学数据稳定可靠.系统自动化程度高,抗干扰能力强,软硬件技术先进,技术指标满足模型试验要求,成果令人满意.该系统是确保三峡工程的航运效益充分实现的重要一环,有着巨大的潜在经济效益和社会效益.参考文献:

[1]　樊启祥.三峡永久船闸关键技术问题综述[J].中国三峡

建设,2002(8):729.

[2]　钮新强.三峡工程永久通航建筑物的设计与研究[J].水

力发电,1997(7):43246.

[3]　谭玉柱.

三相反应式步进电机驱动接口电路设计与应用

[J].中小型电机,2002(1):33234.

[4]　赵京东.双三拍与三相六拍步进电机控制器的GAL电

路设计[J].曲阜师范大学学报:自然科学版,2001(1):

95296.

[责任编辑　张　莉]

87三峡大学学报(自然科学版)　　　　　　　　　　　　　　2009年4月? 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. a9360122192e45361066f517

本文来源：https://www.bwwdw.com/article/e8oq.html