置换流水车间调度问题的知识进化粒子群算法求解.docVIP

 置换流水车间调度问题的知识进化粒子群 算法求解# 唐海波，叶春明，刘长平** 5 10 （上海理工大学 管理学院，上海 200093） 摘要：针对粒子群优化算法求解置换流水车间调度问题时易陷入局部最优，提出采用知识进 化粒子群优化算法求解置换流水车间调度问题。该算法的每个群体空间内采用限定数目的粒 子群优化寻找局部最优解，利用知识进化算法的猜测操作和反驳操作形成以群空间为基础的 一个知识空间，然后再通过知识空间的协同进化更新知识空间从而形成问题的最优解。采用 所提算法对置换流水车间调度问题的基准数据进行测试，并比对标准遗传算法以及标准粒子 群算法，结果表明所提算法的可行性和有效性。 关键词：置换流水车间调度；知识进化算法；粒子群优化 中图分类号：TP18 15 A new hybird particle swarm optimization for solving permutation flow shop scheduling problem TANG Haibo, YE Chunming, LIU Changping (College of Management, University of Shanghai for Science and Technology, Shanghai 200093) 20 25 30 35 40 Abstract: In this paper, the algorithm that based on knowledge evolution particle swarm optimization is proposed to solve permutation flow shop scheduling problem with the criterion to minimize the maximum completion time (makespan), which Coping with the disadvantages of particle swarm optimization being easy to run into local optimum, The algorithm use qualified number of particle swarm optimization to find a local solution in each swarm space, use surmise operation and rebut operation in the knowledge evolution algorithm to form a knowledge space, and then update the knowledge space forming of optimum solution through co-evolution. The algorithm is tested with MATLAB simulation, the result shows that this algorithm has better than particle swarm optimizations. Key words: Permutation Flow shop scheduling; Knowledge evolution algorithm; Particle swarm optimization 0 引言 置换流水车间调度问题是在许多实际生产调度中非常普遍的，也是经典的NP-hard问题， 它的研究具有重要的理论意义和实际的工程价值。置换流水车间调度问题的任务是在有限的 资源约束下，n个工件在m台机器中的每一台机器上依次以相同的顺序加工，每台机器每次 只能加工一个工件，每个工件每次只能由一台机器加工，目的是使得总完工时间最小。自从 Johnson发表第一篇关于流水车间调度问题( Flow Shop Scheduling Problem)的文章以来, 这 类性质的优化调度问题已引起了许多学者的关注。 对于求解流水车间调度问题的方法通常有精确方法、启发式方法和智能优化方法三种类 型。精确方法主要有分支定界法，动态规划等方法，但由于是 NP-hard 问题，精确方法只能 基金项目：高校博士点专项科研基金项目(20093120110008)，教育部人文社会科学规划基金项目 (10YJA630187)，上海市重点学科建设项目(S30504) 作者简介：唐海波（1976-），男，博士，安徽巢湖人，研究方向：工业工程 通信联系人：叶春明（1964－），男，安徽宣城人，博士研究生导师，教授。研究方向：工业工程. E-mail: yechm6464@163.com -