求解作业车间调度问题的粒子群优化算法

《求解作业车间调度问题的粒子群优化算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Vol.29No.6Dec.2008河南科技大学学报：自然科学版JournalofHenanUniversityofScienceandTechnology:NaturalScience文章编号：1672-6871(2008)06-0049-04求解作业车间调度问题的粒子群优化算法张慧霞，张叙，高兴宝（陕西师范大学数学与信息科学学院，陕西西安710062）摘要：讨论了作业车间调度问题的数学表达模型，考虑将粒子群优化算法与差异演化算法的优点结合起来，提岀求解作业车间调度问題的新的混合粒子群优化算法，对7个标准算例的仿真结果表明了算法的有效性和优越性。关键词：作业车间调度；混

2、合粒子群算法；差异演化中图分类号:TP18文献标识码：A0前言作业车间调度问题（JobShopSchedulingProblem,简称JSSP），具有很强的工程背景，在现实生活中也有广泛的应用，它是一个典型的NP-难组合优化问题，应用启发式算法求得其近似解成为现实的解决方案，如邻域搜索法，模拟退火法SA⑴，禁忌搜索法TB：2】，遗传算法GA⑶，粒子群算法"®等，也被应用到调度问题中，并且取得了较好的效果。然而粒子群算法的寻优能力主要来自粒子之间的相互作用和相互影响，粒子本身没有变异机制，从而PSO容易陷入局部最优解，为了克服这个缺点，人们对粒子群算法做了许多改进：7-91

3、o本文在算法的寻优过程中，通过评价粒子聚焦的程度，从而引入差异演化变异机制"°】，增加了粒子群的多样性，改善了搜索全局最优解的能力。1作业车间调度的数学模型作业车间调度问题是要在台机器上加工几个工件，每个工件有m个工序，加工必须满足：（1）-台机器一次只能加工一个工件的一个工序；（2）每道工序必须在指定的机器上加工给定的时间段^.（i=l-nj=l（3）按照加工工艺的规定，每道工序必须在它前面的工序加工完毕后再加工；（4）每道工序从开始到结束，不会被另外的工序所中断。儿表示第i个工件的第j个工序在对应的机器上的加工时间。调度的目的是在满足约束的条件下寻找工序在机器上的排列

4、（即由台机器上加工的工序的排列），使得所有机器的完工的最长时间最短,即优化的目标函数为min

5、max（T4）

6、i=1.2,…，m（1）其中7：表示机器的完工时间。2粒子群PSO算法2.1粒子群算法原理粒子群优化算法（ParticleSwarmOptimization，简称PSO）是最新的进化算法之一，它是基于迭代模式的优化算法。最初由Kennedy和Eberharl提出，用于求解连续非线性函数优化问题，而后被广泛应用于神经网络训练，任务指派和排序问题，它具有容易执行且计算高效的优点（H-，3]o在粒子群算法中，随机产生的解（称为粒子）作为初始种群，在每次迭代过程中，粒子带

7、一个动态调基金项目：国家自然科学基金项目（60671063）；陕西省科学技术计划项目（2006A02）作者简介：张惹般（1982■八女.河南漂河人.硕士生；奇兴宝（1966-）.男.陕西陇县人，教授，博士生导师.主要从爭主要从事最优化理论与算法•进化计算•神经网络的研究.收稿日期：2008-03-10整的速度。在维空间中根据个体最优Pb“和全局最优gy进行优化。设粒子群规模为/V,在第/次迭代中第i个粒子在D维空间中的坐标位置可以表示为=(心⑴宀(『)，•・•・£o(f)),心1,2,・・・N,第i个粒子在D维空间中的飞翔速度表示为Vt(t)=(vn(i),%(f)，…，

8、％(f))，i=l，2,・・・，/V.从而第i个粒子在第j(j=l,2,・・・，D)维空间中的飞行速度和位置可以由下式调整+O二⑷叫⑴+ciri(Pb..i*(O-儿(())+c2r2(gbe-

9、.(t)-X,(z))[%=匕《，如>Ivu=-匕“,vu

10、，它的设定可以权衡粒子的全局探索和局部探索能力；"是(0,1)中的随机数;g为加速常数(通常取q=c2=2)o式(3)中对粒子的速度匕⑴进行了最大的限制，若当前对粒子的加速度导致它在某维的速度分量％")超过了该维的最大速度限制则该维的速度被限制为最大速度卩“，它决定了粒子在解空间的搜索精度，若人“太大，粒子可能超出最优解，若P“太小，粒子容易陷入局部搜索空间而无法进行全局搜索，式(4)为粒子调整自身的位置。2.2PSO算法求解JSSP应用PSO算法求解作业车间调度问题的关键一步是在解空间和问题空间之间建立一个映射，即如何将问题