粒子群优化算法求解多目标流水车间调度问题

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

1、粒子群优化算法求解多目标流水车间调度问题摘要：研究了多目标流水车间调度问题，首先给出了基于排列的表示新方法，提出了将流水作业车间调度问题转化为连续优化问题的方法；然后设计了基于密集距离的多目标粒子群优化算法，该算法利用密集距离进行外部档案维护和全局最好位置选収;最后将新算法应用于一组流水车间调度问题并与强度Pareto进化算法2等算法进行比较，计算结果验证了新算法在多目标流水车I'可调度方血良好的搜索性能.关键词：多目标优化；流水车间调度；表示方法；粒子群优化算法ParticleSwarmOptimizationalgorithmforMulti-objectiveFlowShopSch

2、edulingAbstract:Thispaperaddressesmulti-objectiveflowshopschedulingproblem・Anewpermutation-basedrepresentationmethodisfirstproposedandanapproachtoconvertflowshopschedulingtoacontinuousoptimizationproblemisalsopresented.Crowdingmeasurebasedmulti-objectiveparticleswarmoptimizationisthenpresented,wh

3、ichexternalarchivemaintenanceandglobalbestpositionselectionareperformedbyusingcrowdingmeasure・Finally,theproposedalgorithmisappliedtoasetofflowshopschedulingproblemsandcomparedwithstrengthParetoevolutionaryalgorithm2etal.Thecomputationalresultsdemonstratethegoodperformanceoftheproposedalgorithmin

4、multi-objectiveflowshopscheduling.Keywords:multi-objectiveoptimization;flowshopscheduling;representationmethod;particleswarmoptimization1引言由于生产调度问题通常都存在相互冲突的目标函数，对这些问题进行多目标优化，具有重要理论意义和应用价值，在过去的20年里，基于智能优化算法的多冃标生产调度研允取得了很大的进展，出现了大量成功的多目标智能调度方法。关于流水车间的多目标调度，Sridhar等⑴利用多目标遗传算法处理流水车间和单元制造系统中的调度问题以最小化

5、makespan,总的流经时间和机器空闲时间。Ishibuchui等⑵提出了多目标遗传局部搜索算法以解决流水车间的多目标调度问题。Arroyo等⑶将精英策略、保持种群多样性以及并行多目标局部搜索引入到多H标进化算法(MOEA)中，并将混合算法应用于两目标流水车间调度。卫忠等⑷提出了一种在进化过程中能动态调整适应度分配的演化算法以解决多目标混合流水车间调度问题。师瑞峰等⑸通过在进化搜索过程中引入递进模式的精英策略、群体重构和可变邻域非为解局部搜索策略，提出了一种混合递进多目标进化算法并将其应用于流水车间调度。上述研究采用了两种方法：加权方法和Pareto最优化方法，其中Sridhar等采用

6、加权方法，只能为决策者提供少量最优调度方案；其余的研究釆用了第二种方法，能为决策者提供数量众多的Pareto最优解。粒子群优化算法(PSO)是一种新型智能优化算法，其基本思想来自于对鸟群优美而不可预测的飞行动作的模拟。PSO具有记忆粒子自身经历的最好位置的能力和粒子间信息共享的机制。算法首先在搜索空间内初始化粒子群，即确定粒子的初始位置与初始速度，然后在搜索过程中，按如下公式更新粒子的速度和位置终+1=VVU,+斤q(弓一+r2c2(Gt一X{)X/+i=+u{+[英中w为惯性权重，斤，石为加速常数，5心为[0,1]区间上均匀分布的随机数.Ut,xt分别表示r时刻粒子的速度和位置，为f时

7、刻粒子的自身最好位置和全局最好位置.自1995年问世以来，在算法设计和改进16凶等方面，PSO研究取得了很大的进展，但PSO的应用研究还不够深入。在生产调度⑼方面，PSO具有一定的优势，也存在一些问题，优势在于：和进化算法相比，利用PSO进行生产调度，不必设计特殊交叉、变异算子以保证非法个体不出现；而问题在于：连续的PSO不能直接应用于生产调度这样的组合问题，需要设计离散PSO或将调度问题转化为连续优化问题。本文采用第2种策略，将调