基于改进粒子群算法的车间作业排序的优化设计.pdf

《基于改进粒子群算法的车间作业排序的优化设计.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、62011年11月中国制造业信息化第40卷第21期基于改进粒子群算法的车间作业排序的优化设计黄慧，黎向锋，左敦稳，薛善良(南京航空航天大学机电学院，江苏南京210016)摘要：兼顾车间作业排序中的制造周期和机器利用率，建立了以最小化最大完工时间为主目标、以最大化机器利用率为从目标的优化模型。设计了引入自适应技术的惯性权重，使基本粒子群算法的学习因子可动态变化地改进粒子群算法，并用该改进后的算法对车间作业排序进行了优化设计。实例研究表明：改进后的粒子群算法在收敛速度和收敛可靠性上均优于未改进的粒子群算法，在求解车间作业排序问题的应用中具有更高的求解质量。关键词：车间作业排序；自

2、适应技术；粒子群算法中图分类号：TH165；TP301．6文献标识码：A文章编号：1672—1616(2011)21—0006—04车间作业排序问题是一个典型的NP难题_1J，1问题描述与模型的建立是最困难的组合优化问题之一。由于其本身的复1．1问题描述杂特性，长期以来虽然JobShop研究取得了一定一个典型的车间作业排序问题可描述为：一个的应用效果，但是还存在着难以克服的弱点，如计加工系统中有m台机器和咒个待加工的工件，所算规模不可能较大，寻优结果不具备全局特性等。有工件的加工路径(即技术约束条件)预先给定，但作业车间生产线的有效利用涉及两方面：产品加工不要求一致，各工件在

3、各机器上的操作时间已知。顺序的不同所产生的加工周期和机器利用率这两排序的任务是如何合理地安排每台机器上工件的方面的变化。而现有的车间作业排序文献中，大多加工次序，使约束条件得到满足，同时使某些性能只单方面研究排序方法同所产生的制造周期的长指标得到优化l8J。短不同的问题l2-5j，同时考虑制造周期和机器利典型的JobShop问题一般会有以下条件：用率的文献极少。a．同一时刻每台机器只能加工一个工序，且每粒子群算法是模仿鸟类觅食过程的智能算个工序只能被一台机器所加工，同时加工过程不可法_6J。粒子群算法作为新兴的群体智能算法，自间断，整个过程中机器均有效；从提出之后，由于其概念

4、简明、实现方便，在解决复b．在整个加工过程中，每个工件不能在同一台杂组合优化类问题方面具有优越性能，因而被广泛机器上加工多次；地应用于各个领域。简单的粒子群算法容易早熟，c．各工件必须按照工艺路线以指定的次序在而且微粒在算法后期易在全局最优解附近“震机器上加工，工件i的第J道工序必须在第(一1)荡”_l。若对惯性权重引入自适应技术，并使其学道工序完成后才能开始；习因子可动态变化地改进粒子群算法，则会具有较d．不考虑工件的优先权，允许操作等待；高的全局寻优能力和收敛速度。e．除非特殊说明，工件的加工时间事先给定，本文兼顾车间作业排序问题中的机器利用率且在整个加工过程中保持不变。

5、和作业排序两方面，建立以最小化最大完工时间为1．2数学模型主优化目标、以机器利用率为从优化目标的数学模型，设计一种引入自适应技术的惯性权重及可动态设车间作业系统中：变化的学习因子来求解该问题的改进粒子群算法a．有个工件，用J={1，2，⋯，，z}表示工件(ParticleSwarmOptimization，简称PSO)，并基于集；MATLAB对其性能进行测试。b．有台机器，用M={1，2，⋯，m}表示机收稿日期：2011—05—18作者简介：黄慧(1987)，女，江苏盐城人，南京航空航天大学硕士研究生，主要从事生产调度智能算法及其应用方面的研究工作。·企业管理与信息化·黄慧黎

6、向锋左敦稳等基于改进粒子群算法的车间作业排⋯⋯7器集；所有工件作业时的时间记为F(J)，根据式(3)可c．用OP={OP1，OP2，⋯，OP}表示加工工求得机器J的利用率。序集，其中OP={OPOP⋯，OP}表示工件F(j)=tlj+t2j+⋯+to+⋯+(2)i的工序序列，OP娩表示工件i的第k道工序，若)=×100％(3)OP=0(k=1，2，⋯，791)，则表示工件i在进行第k道工序时不加工；2．4粒子群系统的更新方式d．用T表示加工时间矩阵，t，∈T，t表示工(t+1)=叫，(t)+C11[P订(t)一件i在第J个机器上的加工时间，若t=0，表示工xij(t)]+c2

7、r2[(t)一32(t)](4)件i在第个机器上不需要加工。z订(t+1)=．27(t)+7J(t+1)(5)设工件开始加工时间为0，那么车间作业排序自适应惯性权系数[9]的计算表达式如下：的目标就是求当所有工件都加工完成时的时间是{f~favg多少?设T={T1，丁2，⋯，}，表示工件i加一{工完的时刻，那么所求的目标函数即为f>min{max(Ti)}。(6)式中：训和W分别表示叫(惯性权重系数)的2算法设计最大和最小值；厂为粒子当前的适应值；坦和2．1粒子的编码与解码分别为所有微粒的平均和最小适应