基于离散粒子群算法的作业车间调度优化

Equipment Manufacturing Technology No．9，2013基于离散粒子群算法的作业车间调度优化郭少帅(青岛理工大学 机械工程学院，山东 青岛 266033)摘 要：采用一种改进的离散粒子群算法对作业车间调度问题进行优化。对标准粒子群算法的参数选取策略作出改进。提出自然指数自适应的惯性权重；针对作业车间调度问题，采用基于优先表的编码方式，在该编码方式的基础上设计了相应的位置更新和速度更新方式，使算法能够用于求解作业车间调度问题，同时也通过实例求解，验证了算法的可行性。

关键词：离散粒子群算法；作业车间调度；自适应惯性权重；优先表编码中图分类号：TH186 文献标识码：B 文章编号：1672—545X(2013)09—0132—02作 业 车 间调 度 问 题 (Job—shop SchedulingProblem，简称JSP)是非常具有代表性的～类生产调度，属于NP-hard问题，目前已有的优化算法包括数学规划法、启发式算法、人工智能算法以及软计算方法等?。

粒子群优化算法(Particle Swarm Optimization，简称PS0)是一种软计算方法，由于算法原理简单，参数少，收敛速度快，已经被成功应用于函数优化、神经网络训练、模糊控制系统等诸多领域的优化问题2】。

针对车间生产调度问题，叶建芳等提出了一种免疫粒子群算法，成功的求解了JSP问题【31；黄慧等对粒子群算法做出改进，使其适用于作业车间调度问题[41。

本文采用基于优先表的编码方式，改进了粒子群算法中惯性权重的选取策略，并设计了算法的具体操作过程，对 JSP进行了成功地求解。

1 作业车间调度问题作业车间调度问题优化的目的是为生产任务中每个工件的各个工序安排加工顺序，在满足约束条件的情况下，尽可能满足决策者需要的性能指标。其中，决策者的需求称为优化问题的目标函数，求解JSP最常用的目标函数是寻求最短完工时间。

JSP具体描述如下：有 m台可用机床和n个待加工工件，每个工件包含m道工序(工序与机床一一对应)，每个工件的工艺流程固定且已知，每道工序的加工时间已知。

问题包含的基本变量有：可用机床集，待加工工件集，工件包含的全部工序集，每道工序的加工时间集等。

JSP的约束条件：(1)每个工件的工艺路径已知，且固定不变；(2)每台机床在同一时刻只能加工某一个工件的一道工序；(3)某个工件的一道工序在同一时刻只能在一台机床上加工；(4)一道工序的加工过程不能中断。

2 标准粒子群算法标准粒子群算法的核心是位置更新公式和速度更新公式【5l：k
d =k- +cl randl(Pia-Xik
d
’)+c2 rand2(p 一 k -b'i o,I'g )(1) 1 ： 。
一 (2)式中，为惯性权重，其作用是控制算法的搜索能力；c。和C 为学习因子；rand。和rand 为[0，1]内的随机数；删 k -为粒子先前的速度，可以理解为上一代粒子的飞行惯性；c．rand。Pid- )表示粒子学习自己的飞行经验；C2rand2 Pgd- ‘)表示粒子学习同伴的飞行经验。

3 用于求解 JSP的粒子群算法3．1编码在用种群迭代法对 JSP进行求解时，最常用的编收稿日期：2013—06—12作者简介：郭少帅(1987一 )，河南禹州人 ，在读硕士研究生，研究方向为制造系统优化设计。

132《装备制造技术)2013年第9期码方式是基于工序的编码。此种编码方式操作简单，解码方便[61，且迭代过程中产生的新粒子都在可行域内。但是存在多个编码对应一个调度方案的问题，会造成粒子更新过程中没有意义的操作，当该点处在全局最优P 时，甚至会造成粒子在“多个位置”之间震荡，延缓算法的收敛。

根据问题的特点，无论怎样制定调度方案，最后每台机器上工件的加工顺序必是工件 l，2，?，n的一 个排列，并且每个工件都是从其第一道工序顺次加工至最后一道工序。本文采用基于优先表的编码 ，对于每一台机床，用工件号的全排列代表该机床上各个工件的加工顺序。以三个工件，每个工件有三道工序的3×3调度为例：『 23 21] ㈥【2 3 1 J该编码表示机床 1上工件的加工顺序依次为 l、3、2；机床2上各工件的加工顺序为 3、2、l；机床3上各工件的加工顺序的2、3、l。

采用基于优先表的编码方式，优点是每个有效编码便对应一个调度方案，不存在编码与调度方案的多对一问题 ，在给定的编码方式之下也不存在编码与调度方案的一对多问题，使得算法每次迭代对编码的操作更加有效，从而加快了算法的收敛。

产生有效编码的方法：(1)根据工件的工艺路径，设定每个工件的工序号为工件的优先级别，工件号越小，优先级最高；(2)从优先级为 1的工件中任选一个工件，将该工件号放在对应的机床上，并将该工件剩余工序的优先级全部减 1；(3)重复步骤2，直至所有工件在机床上的加工顺序全部确定。

仍以三个工件，每个工件有三道工序的调度为例。设定工件 l的工艺路径为车 铣 磨，工件2的工艺路径为铣一车一磨，工件3的工艺路径为车磨 铣，车床的机床号记为 1，铣床记为 2，磨床记为3，编码产生过程主要有以下三个方面：一 是，优先级为 l的工序包括工件 1的车削，工件 2的铣削，工件 3的车削，从中任选一个，此次编码选则工件2的铣削工序，则铣床上最先加工的工件为2，将2填人编码对应位置；二是，将工件 2的剩余两道工序的优先级全部减 1，此时优先级为 1的工序包括工件 1的车削，工件 2的车削，工件 3的车削，从中任选一个，此次选择工件 1的车削工序，则车床上先加工的工件为 1，将 1填人编码对应位置；三是，重复以上步骤，直至每个工件的所有工序在各机床上的加工顺序全部确定。

3．2惯性权重的选取对惯性权重 的研究，最开始是使其取定值，后来在大多数问题中被动态改变的W取代。目前大多数文献中采取的惯性权重选取策略是 Shi提出的线性递减权值策略[51。

惯性权重的取值较大时，速度更新公式中 ／ Ig-项增大，即粒子继承上一代的飞行速度相对较多，能够一定程度上保证粒子向更多区域探索，但会减缓算法的收敛速度；反之，较小的 能够加快算法的收敛速度，但也容易使算法过快的收敛至局部最优解而导致早熟。

本文对惯性权重的选取策略进行改进，提出一种自然指数自适应的惯性权重选取策略：： e
- GIG(4)式中，G为当前迭代次数；G一为最大迭代次数。

该策略惯性权重的取值仅与当前迭代次数和最大迭代次数有关，不需要设置其他参数，简单易理解，且能够加快算法的收敛速度。

3．3算法的修正定义基于优先表编码粒子之间的距离和粒子的速度：粒子之间的距离为两个粒子编码串中对应位置上不相同元素的个数 ，记为 dis(筏X,k)；粒子的速度值为一个非负的整数，表示粒子位置更新时所要进行的操作次数。

粒子群的位置更新和速度更新公式变为：= int[ k一+C1 rand。dis(xI～p )+c：rand d ( )】(5)= ① 1,Pi (6)式中，int[]为取整函数；符号④为对粒子进行置换操作；为置换次数。

对粒子进行置换操作是指对某一行中的两个不同元素进行位置调换。

4 实例计算以FT06问题为例[71，利用Vc++软件编写程序(下转第 1 41页)133《装备制造技术>2013年第9期(2)通过对卷筒维护的规范化，制定严格的点检措施，一旦检查发现挡环与扇形块间隙过小，及时调整，避免隐患演变成故障，为生产创造了良好的设备环境。

(3)开卷机卷筒导向块裂纹问题的解决，使得对今后其他开卷机的维护方法和检查方式都有了借鉴的先例，为维修人员能更迅速、高效地查找开卷机卷筒出现故障的原因提供了依据，从整体上提高了设备的管理水平。

参考文献：[1】邹家祥．轧钢机械【M】．北京：冶金工业出版社，2000.

【2】王海文．轧钢机械设计[M]．北京：机械工业出版社，1983.

【3】成大先．机械设计手册 [M】．北京 ：化学工业出版社 ，2008【4】姜继海，宋锦春．液压与气压传动【M】．北京：高等教育出版社．2002.

【5]王春行．液压控制系统【M】．北京：机械工业出版社，1999.

【6】路甬祥．液压气动技术手册 【M】．北京 ：机械工业出版社 ，20n2.

Improvement of the Structure of the Uncoiler BarrelYANG Jia-ye，YAN Sheng(Guangxi Liuzhou Iron and Steel(group)Company，Liuzhou 545002，China)Abstract：Analyzed the heavy volume abrasion pull unit decoiler correction drum fan guide boards easy to the cause ofthe fracture， an d presents the measures for uncoiler drum structure and the efect after tran sforming， for themaintenan ce pe~onnel can more quickly，eficiently an d find decoiler drum the cause of the failure to provide the basis，more production provide a powerful gu arantee.

Key words：the rewinding unit；uncoiler；drum structure modification；maintenance methods(上接第 133页)进行仿真模拟。算法中参数取G一=300，C。=C =2，种群规模 M=50。运行程序 50次，有 39次收敛到最优解，算法收敛率为78％，文献【7]中提出的算法运行l0次，收敛到最优解的次数为7次，收敛率为7O％，标准粒子群算法的收敛率为 30％。因此，本文设计的算法具有可行性和优越性。

5 结束语本文用改进的离散粒子群算法求解JsP问题。提出了一种自然指数形式的自适应惯性权重；根据 JSP的特点，采用基于优先表的编码方式，在此编码方式的基础上设计了粒子群算法的具体操作过程；通过实例验证了算法的有效性。

L、奠0参考文献：【1】刘 民，吴 澄．制造过程智能优化调度算法及其应用【M】．北京 ：国防工业出版社，2008.

【2】Ioan C T．The particle SWal'fl optimization algorithm converganceanalysis and parameter selection[J]．Information Processing Let—ters，2003，85(6)：317-325.

[3】叶建芳，王正肖，潘晓弘．免疫粒子群优化算法在车间作业调度 中的应用 [J]．浙江大学学 报 ：工学版 ，2008，42(5)：863-868.

[4】黄 慧，黎向锋，左敦稳，等．基于改进粒子群算法的车间作业排序的优化设计切．中国制造业信息化，201 1，40(21)：6—9.

【5】Shi Yuhui，Eberhart R C．A modflied particle swarnl optimizer【C】．IEEE World Congress on Computational Inteligence，An-chorage，1998：69-73.

[6]潘全科 ，王文宏，潘 群 ，等．解决 JOB SHOP问题的粒子群优化算法【J】_机械科学与技术，2006，25(6)：75—79.

【7]乔佩利，马丽丽，郑 林．基于改进粒子群算法的车间调度问题研究【J】．哈尔滨理工大学学报 ，201 1，16(2)：35—39.

Job-Shop Scheduling Problem Optimization based on Discrete Particle Swarm AlgorithmGUO Shao—shuai(School of Mechanical Engineering，Qingdao Technological University，Qingdao Shandong 266033，China)Abstract：An improved discrete particle swarm algorithm is applied to solve the job-shop scheduling problem．Theparameter selecting strategy is improved，and al adaptive inertia weight of natural exponential function is put forward.

Regarding to the job—shop scheduling problem，selects the encoding mode based on precedence table，and designs therelative position updating and speed updating mode on this basis to solve the job-shop scheduling problem．It provedthe practicab ility of the algorithm by example solution.

Key words：discrete particle swami algorithm；job-shop~heduling；adaptive inertia weight；Precedence table encoding141