求解JOB-SHOP车间作业调度的混合算法研究

摘要

作业车间调度问题（JSP）是一类满足任务配置和顺序约束要求的资源分配问题，是最困难的组合优化问题之一。有效的生产调度方法和优化技术的研究和应用是实现先进制造和提高生产效益的基础和关键。求解的方法以启发式算法为主，基于优先权规则，即从未排序的工序特定子集中选用工序的规则。 本文鉴于精确方法仅适合于小规模问题，以混合算法来求解Job-shop调度问题。主要工作如下：首先，通过对国内外作业车间调度问题的研究，介绍了已有的求解Job-shop调度问题的各种算法。其次，在阐述遗传算法基本概念、原理、方法的基础上，针对普通遗传算法在求解Job-shop调度问题时，存在着收敛速度慢和易出现“早熟”现象的缺点，提出算法混合思想。接下来分析了遗传算法和禁忌搜索算法及蚁群算法的优缺点，遗传算法能以较大概率找到全局最优，但局部搜索能力不强，对车间调度系统进行优化时需较长时间。禁忌搜索算法收敛较快，局部搜索能力强，但其收敛性和初值的选择有很大关系。蚁群算法的正反馈和并行搜索特点提高解的质量和稳定性，但算法时间长，且容易陷入局部最优解。本文提出了作业车间调度的混合算法。经过多次试验，发现在遗传算法完成后，直接选用遗传算法得到的最优解作为禁忌搜索的初始解进行计算得到的最终解和用遗传算法所得到的最终解相差无几，但平均进化代数减少，避免了遗传算法的早熟收敛。对于混合蚁群遗传算法由于遗传算法具有快速随机的全局搜索能力，但对于系统中的反馈信息利用却无能为力，当求解到一定范围时往往做大量无为的冗余迭代，求精确解效率低，蚂蚁算法是通过信息素的累积和更新收敛于最优路径上，具有分布式并行全局搜索能力，但初期信息素匮乏，求解速度慢，算法是将遗传算法与蚂蚁算法融合，采用遗传算法生成信息素分布，利用蚂蚁算法求精确解，优势互补。通过对标准作业车间调度问题的测试，与传统算法进行比较，证明了本文的算法在求解Job-shop调度问题方面有较好的效果。

目录

文摘

英文文摘

声明

引言

第一章车间调度

1.1车间调度在企业生产中的重要性

1.1.1车间调度问题的定义

1.1.2车间调度的重要性

1.2车间调度问题概述

1.2.1车间调度问题的分类与特点

1.2.2车间调度问题的研究现状

1.2.3车间调度问题的研究策略

1.3 Job-Shop调度问题

1.3.1JSP模型

1.3.2 JSP的表示

1.3.3 JSP的复杂性

1.4求解Job-shop调度问题的算法研究现状

本章小结

第二章遗传算法

2.1遗传算法概述

2.2遗传算法的基本定理

2.2.1模式定理

2.2.2内含并行性定理

2.3遗传算法的基本实现技术

2.3.1编码方法

2.3.2适应度函数

2.3.3遗传操作

2.4遗传算法的运行参数

本章小结

第三章车间调度问题的混合算法研究

3.1遗传算法在车间调度的应用

3.1.1基本原理与基本流程

3.1.2模式定理和隐含并行性

3.1.3遗传算法的缺陷

3.2混合遗传禁忌算法

3.2.1禁忌搜索算法及其在车间调度的应用

3.2.2混合遗传禁忌算法的框架设计

3.2.3混合遗传禁忌算法的操作

3.3混合蚁群遗传算法

3.3.1蚁群算法的特点

3.3.2基本蚁群算法

3.3.3蚁群算法的流程

3.3.4蚁群算法的原理

3.3.5面向Job-shop调度问题的混合蚁群遗传算法描述

本章小结

第四章实例分析

4.1仿真实验

本章小结

第五章结束语

5.1全文总结

5.2展望

参考文献

攻读硕士学位期间发表的学术论文

致谢