群体智能算法求解阻塞流水车间调度问题研究(源码)【字数：11186】
摘 要摘 要随着近一个世纪的科学技术的发展，企业对其生产与管理模式的不断改进已经成为了一个重要性的问题，而生产调度问题在该方面则显得尤为重要。生产调度问题广泛存在于各个行业之中，如食品加工行业，纺织业，制药业等。而带有阻塞区域的车间流水调度问题显示更有代表意义。该问题可以应用于不同行业之中，例如机器加工产业可以利用该问题选择不同工件的加工顺序，石化产业可以选取不同工序的流程等。该问题的研究价值在现实生活中显得越来越重要。本文针对阻塞流水车间调度问题提出了一种以最小化最大完工时间为目标的人工蜂群算法。本算法在初始化阶段采用了启发式算法的概念对初始数据进行随机处理，从而用来提高初始解的质量。在该蜂群算法的雇佣蜂阶段，引入了交叉、变异、局部重构等方法，对某个已知解进行一次或多次处理，进一步增强了该算法对解集的优化能力。跟随蜂阶段则处理由雇佣蜂传递过来的信息，利用随机解的迭代处理增强了对解的处理能力，同时也保证了解在一定区间内的优势性。侦查蜂阶段则防止解集陷入局部最优解，并对解进行领域扰动增强多样性。最终算法通过多次迭代产生最优序列。针对之前学者研究的数据，对提供的m个工件，n台机器（m，n可变）的加工数据进行实验测试，通过对变量的控制变化，证明了该算法在小型区间内的可行性。关键词蜂群算法；最大完工时间；迭代处理；局部最优
目 录
第一章 绪论 1
1.1 研究背景 1
1.2 群体智能算法在阻塞流水车间方面的研究 1
1.3 主要研究内容 2
1.4 主要研究方法 3
1.5 论文的组织结构 3
第二章 阻塞流水车间问题概述 4
2.1 引言 4
2.2 阻塞流水车间调度模型 4
2.3 车间调度问题的研究现状与方法 7
2.4 本章小结 8
第三章 蜂群算法的研究与应用 9
3.1 引言 9
3.2 人工蜂群算法机理 9
3.3 人工蜂群算法概述 11
3.4 人工蜂群算法的研究及应用 11
3.5 本章总结 12
第四章 人工蜂群算法求解阻塞流水车间调度问题 13
4.1 算法模块功能概述 13 *好棒文|www.hbsrm.com +Q: ￥351916072￥
4.1.1 问题编码 13
4.1.2 初始解集的建立 13
4.1.3 重构领域结构操作 13
4.1.4 雇佣蜂阶段 14
4.1.5 跟随蜂阶段 15
4.1.6 侦查蜂阶段 17
4.1.7 模块功能图 17
4.2 算法流程 18
4.3 实验结果与分析 18
4.3.1 实验设置 18
4.3.2 试验参数的影响 18
4.3.3 算法性能测试 22
4.3.4 算法性能总结 23
4.4 本文算法与普通ABC算法的区别 23
4.5 本章小结 24
结论 25
致谢 27
参考文献 28
第一章 绪论
1.1 研究背景
随着经济全球化的发展，各企业面临着新的挑战。企业要想在激烈的竞争中占据优势，就必须加快提高生产效率，作业调度问题主要就是研究如何提高生产效率，因此，对该问题的研究具有重要意义。作业调度问题有很多种类，本文研究的阻塞流水车间调度问题主要具有单线度，离散性和随机性的特点，本文针对单个流水线的调度问题进行研究，各工件与机器的加工时间等都具有不确定性，同时，本文针对最大完工时间进行调度处理，处理结果直观，便于观察。本文所研究的调度问题应用范围十分广泛，它可以广泛的应用在生物、制药、机械、电子等工业企业中，也应用在装配线与服务业中，各种类的企业都可以不同程度的将该问题引入到其生产线中。除了提升效率之外，还可以用更好的质量来响应市场，而这一要求就势必要求进行更优的生产调度。例如如何组织生产，调配资源，对企业提高核心竞争力具有不可或缺的作用，而流水车间调度问题（FSSP）则是生产调度问题的一个重要分支。在这几十年的研究过程中，研究者们先后提出了一些基于运筹学的传统计算方法，一些启发式规则，以及一些基于其他规则的研究方法，但是随着生产工业的迅猛发展，调度问题的规模和复杂程度更是急剧上升，这些方法已无法满足实时性的要求。所以，人工智能的出现则为这类问题提供了新的思路。而群体智能算法则以思路清晰，结构简单，约束条件少的优点非常适合于求解各种类型的复杂生产调度问题。经过学者们的研究发现，该方向在解决该类问题上具有良好的适用性。同时在实践上，则优化了流水车间的调度，增强了企业的核心竞争力。
1.2 群体智能算法在阻塞流水车间方面的研究
流水车间调度问题是一个比较传统的问题,最早的研究要从20世纪50年代开始算起。流水车间作业调度问题是最难的组合优化问题之一,已经被证明属于NP类问题。利用精确算法求解是比较困难的,如何可以快速、有效地求解车间作业调度问题一直以来都是一个研究热点。
遗传算法作为一种全局优化搜索算法,具有并行搜索的能力,通过遗传算子的作用,可以将各代群体搜索到的信息进行保存和传递,这些是传统优化方法所不具有的,遗传算法也因此成为解决车间调度问题使用最广泛的优化算法之一。不同学者将各种遗传算法和其他算法相结合提出了有效的解决办法，如：将模拟退火算法引入自适应遗传算法，提出了混合遗传算法[]。再有将遗传算法和蚁群算法进行更小粒度的融合，提高了求解效率和精度。还有学者提出了一种动态混合遗传算法，通过引入自适应的遗传算法[]思想，通过实验表明，该算法能在较大区间内得到较优解。而本文所用到的人工蜂群算法也是一种通过模仿蜜蜂的采蜜行为而提出的群集智能方法。自 2005 年Karaboga系统地提出了人工蜂群算法(Artificial Bee Colony, ABC)模型以来，ABC算法受到越来越多学者们的关注，现在已经取得了许多重要的研究成果，并在科研和工程领域有着广泛应用。
但是，目前绝大多数的基于遗传算法的车间调度方法，仅在中小规模领域上具有可适用性，对于规模较大的情况还不适用，而ABC算法的自身模型的研究上处于初始阶段，其在NPHard离散域优化问题上仍存在提高空间。因此，本文就针对人工蜂群算法（ABC）提出了一种能较为有效的解决阻塞流水车间的算法。
1.3 主要研究内容
本文基于对人工蜂群算法的研究，将人工蜂群算法对阻塞流水车间调度问题进行求解，做了以下三个方面的工作。
（1）研究当前基本阻塞流水车间问题的情况，了解该问题的背景，研究目的，研究手段等，理解该算法的基本应用以及他与其他方面的结合应用，同时仔细理解其他学者在该问题上提出的可行性解。
（2）研究现有的ABC算法模型，理解现有的人工蜂群算法机理。将ABC算法中的劳动分工和角色转换两个重要的机制理解，雇佣蜂，跟随蜂和侦查蜂三种蜂种之间的角色转换和他们之间的功能。同时理解该算法下的重构操作以及在三个蜂种之外的其他工作。
目 录
第一章 绪论 1
1.1 研究背景 1
1.2 群体智能算法在阻塞流水车间方面的研究 1
1.3 主要研究内容 2
1.4 主要研究方法 3
1.5 论文的组织结构 3
第二章 阻塞流水车间问题概述 4
2.1 引言 4
2.2 阻塞流水车间调度模型 4
2.3 车间调度问题的研究现状与方法 7
2.4 本章小结 8
第三章 蜂群算法的研究与应用 9
3.1 引言 9
3.2 人工蜂群算法机理 9
3.3 人工蜂群算法概述 11
3.4 人工蜂群算法的研究及应用 11
3.5 本章总结 12
第四章 人工蜂群算法求解阻塞流水车间调度问题 13
4.1 算法模块功能概述 13 *好棒文|www.hbsrm.com +Q: ￥351916072￥
4.1.1 问题编码 13
4.1.2 初始解集的建立 13
4.1.3 重构领域结构操作 13
4.1.4 雇佣蜂阶段 14
4.1.5 跟随蜂阶段 15
4.1.6 侦查蜂阶段 17
4.1.7 模块功能图 17
4.2 算法流程 18
4.3 实验结果与分析 18
4.3.1 实验设置 18
4.3.2 试验参数的影响 18
4.3.3 算法性能测试 22
4.3.4 算法性能总结 23
4.4 本文算法与普通ABC算法的区别 23
4.5 本章小结 24
结论 25
致谢 27
参考文献 28
第一章 绪论
1.1 研究背景
随着经济全球化的发展，各企业面临着新的挑战。企业要想在激烈的竞争中占据优势，就必须加快提高生产效率，作业调度问题主要就是研究如何提高生产效率，因此，对该问题的研究具有重要意义。作业调度问题有很多种类，本文研究的阻塞流水车间调度问题主要具有单线度，离散性和随机性的特点，本文针对单个流水线的调度问题进行研究，各工件与机器的加工时间等都具有不确定性，同时，本文针对最大完工时间进行调度处理，处理结果直观，便于观察。本文所研究的调度问题应用范围十分广泛，它可以广泛的应用在生物、制药、机械、电子等工业企业中，也应用在装配线与服务业中，各种类的企业都可以不同程度的将该问题引入到其生产线中。除了提升效率之外，还可以用更好的质量来响应市场，而这一要求就势必要求进行更优的生产调度。例如如何组织生产，调配资源，对企业提高核心竞争力具有不可或缺的作用，而流水车间调度问题（FSSP）则是生产调度问题的一个重要分支。在这几十年的研究过程中，研究者们先后提出了一些基于运筹学的传统计算方法，一些启发式规则，以及一些基于其他规则的研究方法，但是随着生产工业的迅猛发展，调度问题的规模和复杂程度更是急剧上升，这些方法已无法满足实时性的要求。所以，人工智能的出现则为这类问题提供了新的思路。而群体智能算法则以思路清晰，结构简单，约束条件少的优点非常适合于求解各种类型的复杂生产调度问题。经过学者们的研究发现，该方向在解决该类问题上具有良好的适用性。同时在实践上，则优化了流水车间的调度，增强了企业的核心竞争力。
1.2 群体智能算法在阻塞流水车间方面的研究
流水车间调度问题是一个比较传统的问题,最早的研究要从20世纪50年代开始算起。流水车间作业调度问题是最难的组合优化问题之一,已经被证明属于NP类问题。利用精确算法求解是比较困难的,如何可以快速、有效地求解车间作业调度问题一直以来都是一个研究热点。
遗传算法作为一种全局优化搜索算法,具有并行搜索的能力,通过遗传算子的作用,可以将各代群体搜索到的信息进行保存和传递,这些是传统优化方法所不具有的,遗传算法也因此成为解决车间调度问题使用最广泛的优化算法之一。不同学者将各种遗传算法和其他算法相结合提出了有效的解决办法，如：将模拟退火算法引入自适应遗传算法，提出了混合遗传算法[]。再有将遗传算法和蚁群算法进行更小粒度的融合，提高了求解效率和精度。还有学者提出了一种动态混合遗传算法，通过引入自适应的遗传算法[]思想，通过实验表明，该算法能在较大区间内得到较优解。而本文所用到的人工蜂群算法也是一种通过模仿蜜蜂的采蜜行为而提出的群集智能方法。自 2005 年Karaboga系统地提出了人工蜂群算法(Artificial Bee Colony, ABC)模型以来，ABC算法受到越来越多学者们的关注，现在已经取得了许多重要的研究成果，并在科研和工程领域有着广泛应用。
但是，目前绝大多数的基于遗传算法的车间调度方法，仅在中小规模领域上具有可适用性，对于规模较大的情况还不适用，而ABC算法的自身模型的研究上处于初始阶段，其在NPHard离散域优化问题上仍存在提高空间。因此，本文就针对人工蜂群算法（ABC）提出了一种能较为有效的解决阻塞流水车间的算法。
1.3 主要研究内容
本文基于对人工蜂群算法的研究，将人工蜂群算法对阻塞流水车间调度问题进行求解，做了以下三个方面的工作。
（1）研究当前基本阻塞流水车间问题的情况，了解该问题的背景，研究目的，研究手段等，理解该算法的基本应用以及他与其他方面的结合应用，同时仔细理解其他学者在该问题上提出的可行性解。
（2）研究现有的ABC算法模型，理解现有的人工蜂群算法机理。将ABC算法中的劳动分工和角色转换两个重要的机制理解，雇佣蜂，跟随蜂和侦查蜂三种蜂种之间的角色转换和他们之间的功能。同时理解该算法下的重构操作以及在三个蜂种之外的其他工作。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/jsjkxyjs/785.html
