基于改进粒子群算法的Job-shop调度优化

发布时间：2017-11-04 16:01

本文关键词：基于改进粒子群算法的Job-shop调度优化

【摘要】：Job-shop Scheduling Problem（简称JSP）是一类经典且具有代表性的车间作业调度问题，在车间作业调度问题的研究中占有重要的地位。车间作业调度问题具有很高的研究价值：一方面，先进的调度优化理念能够解决车间生产过程中所面临的诸多问题，提高车间的生产能力和企业的竞争力；另一方面，车间作业调度问题属于NP（Non-deterministic Polynomial，非确定多项式）难问题，，其优化方法能够为旅行商问题（TravelingSale-manProblem，简称TSP）、车辆路径问题（Vehicle Routing Problem，简称VRP）等其他领域的组合优化问题提供求解思路。本文采用粒子群算法对Job-shop调度问题进行优化，对算法做出了合理的改进，并解决了粒子群算法优化离散变量问题时遇到的粒子更新问题，更好的发挥了粒子群算法的性能。深入分析粒子群算法的机理和算法相关参数的作用，提出一种基于自然指数函数的惯性权重选取策略；为了提高算法的全局寻优能力、避免算法陷入局部最优，在粒子群算法中加入了变异机制。全面比较了目前主流的用于求解Job-shop调度问题的编码方式，根据粒子群算法的特点，提出了混合编码的策略，并在此编码方式的基础上，设计了更好的速度位移模式。建立了完善的Job-shop调度数学模型，以最短完工时间为优化目标函数，采用本文改进的算法对几类经典的Benchmark实例进行了优化，与前人的研究成果相对比，证明了改进后算法的优越性。
【学位授予单位】：青岛理工大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP18;TH186

【参考文献】

中国期刊全文数据库前10条

1 何利;刘永贤;谢华龙;刘笑天;;基于粒子群算法的车间调度与优化[J];东北大学学报(自然科学版);2008年04期

2 田野;刘大有;;求解流水车间调度问题的混合粒子群算法[J];电子学报;2011年05期

3 谷峰,陈华平,卢冰原,古春生;粒子群算法在柔性工作车间调度中的应用[J];系统工程;2005年09期

4 张玉芳;薛青松;熊忠阳;;基于禁忌搜索的动态粒子群算法[J];计算机工程与应用;2008年24期

5 彭传勇;高亮;邵新宇;周驰;;求解作业车间调度问题的广义粒子群优化算法[J];计算机集成制造系统;2006年06期

6 潘全科;王文宏;朱剑英;;解决无等待流水车间调度问题的离散粒子群优化算法[J];计算机集成制造系统;2007年06期

7 张长胜;孙吉贵;欧阳丹彤;张永刚;;求解车间调度问题的自适应混合粒子群算法[J];计算机学报;2009年11期

8 张维存;郑丕谔;吴晓丹;;基于蚁群粒子群算法求解多目标柔性调度问题[J];计算机应用;2007年04期

9 唐海波;叶春明;;一种求解作业车间调度的混合粒子群算法[J];计算机应用研究;2011年03期

10 朱霞;;一种求解作业车间调度的文化粒子群算法[J];计算机应用研究;2012年04期