基于轮盘赌编码和粒子群算法的并行机调度优化.pdf

《基于轮盘赌编码和粒子群算法的并行机调度优化.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于轮盘赌编码和粒子群算法的并行机调度优化★口高潮口刘志雄1．武汉理工大学能源与动力工程学院武汉4300632．武汉科技大学机械自动化学院武汉4300813．武汉理工大学水路公路交通安全控制与装备教育部工程研究中心武汉430063摘要：将粒子群算法用于优化并行机调度问题，将遗传算法选择策略方法中的轮盘赌方法引入到编码方法中，提出了一种基于轮盘赌的粒子编码方法，用于表示并行机调度问题的解。通过对两个并行机算例的计算说明，基于轮盘赌编码方法的粒子群算法都能有效地对并行机调度问题进行优化。关键词：粒子群算法并行机调度轮盘赌编码中图分类号：TB11文献标识码：A文章编号：1000—

2、4998(2010)06—0027—03并行机调度研究n个工件在m台机器上的加工1并行机调度问题的描述过程，当每台机器均能满足各工件的加工，并且不考虑对于n个工件m台机器的并行机调度问题，假设工件的加工准备时间时，并行机调度的解主要考虑所每个工件只有一道工序，一个工件同时只能在一台机有工件在各机器上的划分问题，或者说，如何将m台器上加工，任何机器都可以加工任意工件，一台机器同机器分配给n个工件。以最大完工时间最小为优化目时只能加工一个工件。不考虑同～台机器上加工各工标的并行机调度问题已经被证明是NP完全问题⋯，启件之间的准备时间，用‘，表示工件的加工时间，并且发式算法、禁忌

3、搜索【，1和遗传算法等均被应用于每个工件的加工时间事先可知。引入变量W(i=1，2，求解并行机调度问题。⋯，m；J=1，2，⋯，n)，当w=1时，表示工件在机器粒子群算法(ParticleSwarmOptimization，PSO)是i上加工；否则，W=0。如果用C表示机器i上所有工一种基于群体智能的进化类算法】，在连续函数优化件的完工时间，则：问题领域，粒子群算法显示了其有效的优化性能。与遗传算法一样，采用粒子群算法求解调度问题时，也需要C。=∑加(1)针对调度问题的解建立一定的粒子编码方法，在粒子=1如果用．厂表示所有工件的最大完工时问，用F表和调度解之间建立一种映射关

4、系。利用遗传算法求解示最小化最大完工时间。即：并行机调度问题时，比较常用的染色体编码方法是整数编码方法[5】，通过在[1，m】之问随机产生的是整数f=m三xc。=m言x∑西(2)‘Jl』=1来表示被分配的机器编号，进而得到并行机的调度解。本文利用粒子群算法对并行机调度问题进行优化F=mini=minm∑(3)‘_。时，首先将遗传算法中的整数编码方法借鉴到粒子群J=1算法的粒子编码中，通过对粒子位置进行取整操作得并行机调度主要考虑的是所有工件在各机器上的到调度解。在此基础上，将遗传算法选择策略中的轮盘划分，如果考虑工件的准备时间，调度问题的解还需要赌概念引入到粒子编码中，提出

5、一种基于轮盘赌的粒考虑各机器上工件的次序。因此，对于并行机调度问子编码方法，即通过计算粒子位置的轮盘赌概率，通题，其可行解的前提条件是必须保证每台机器都被分过轮盘赌方法将工件分配给每台机器，从而得到调度配进行工件加工，在此基础上，对所有工件的任意分配解。都可形成一个可行调度解。最后采用基于两种不同编码方法的粒子群算法对2粒子群算法设计两个不同规模的并行机调度问题算例进行了计算，计算结果说明基于轮盘赌粒子编码方法的粒子群算法更2．1粒子群算法能有效地对并行机调度问题进行优化。在粒子群算法中，每个优化问题的解都用一个粒子表示，所有粒子都有一个由被优化的函数决定的适★国家自然科学

6、基金资助项目(编号：70801047)中国博士后科研基金资助项目(编号：20090450769)应值，每个粒子还有一个速度决定它们搜索的方向和收稿日期：2010年2月距离，所有粒子通过追随当前的最优粒子(个体最优粒矗机械制造48卷第550期2010／6回子和全局最优粒子)在解空间中进行搜索。假设粒子群生成的0到1之间的实数，选择对应的轮盘赌概率所对应中的第个粒子在n维空间中的位置表示为一个凡的父代个体作为新的父代个体。并行机调度的解主要考维向量=(，抛，⋯，‰⋯‰)，速度=(，，虑如何选择工件分配给每个机器，并且要保证每台机器⋯都有工件加工。因此，这里将轮盘赌选择策略的方法

7、引，，⋯‰)决定了粒子在搜索空间单次迭代的位移。当前粒子群中的个体最优粒子表示为P=(PP⋯，入到粒子编码方法中，用于给每台机器分配工件。P，⋯P)，全局最优粒子表示为g=(gl，gz，⋯，gl，⋯2．2．2．1二维粒子编码g)，粒子群中的所有粒子根据式(4)和式(5)来更新其采用同表1相同的二维粒子编码方法，与表1不同速度和位置。的是，第二维用随机生成的正的实数表示。那么，对于=“，+C1Fandom()(p一)种群中任意一个粒子，其编码可以表示如表2所示，表2+c2F~ndom()(一)(4)中，竹>0。+(5