一种群体智能算法的研究与应用(源码)【字数：14894】
摘 要摘 要阻塞流水车间调度问题（Blocking Flow Shop Scheduling Problem, BFSSP）是传统流水车间调度问题的一个重要分支，该类问题符合现代加工制造的实际情况，在食品加工、塑料生产、钢铁制造、化工制造等行业有着广泛的应用，因此对该类问题进行研究具有重要的理论和实际意义。本文对新兴的化学反应算法（Chemical Reaction Optimization, CRO）进行研究，将化学反应算法应用于阻塞流水车间调度问题，并以最小化最大完工时间为目标进行了求解。大量实验测试表明单纯的CRO算法随机性较强，收敛速度慢，算法效果不佳。为了提高求解质量，本文在种群初始化和种群搜索能力方面对CRO算法进行了改进(1)基于NEH（Nawaz-Enscore-Ham, NEH）算法和PF（Profile Fitting, PF）算法设计了NEH_PF（Nawaz-Enscore-Ham & Profile Fitting, NEH_PF）算法对种群初始化，以此提高初始种群的质量；(2)将迭代贪婪算法应用于化学反应算法的碰墙反应，以此来提高算法局部搜索能力；(3)设计了Path-Relinking算法引导种群向优质解进化，从而提高算法的全局搜索能力。利用标准测试数据集进行测试，实验表明本文所提出的算法对于求解阻塞流水车间调度问题是可行的、有效的，算法具有较好的收敛性，并具有较高的求解质量，在部分测试实例中得到了新的最优解。关键词化学反应算法；迭代贪婪；Path-Relinking；阻塞流水车间调度问题；最大完工时间
目 录
第一章 绪论 1
1.1 课题研究背景和意义 1
1.1.1 流水车间调度问题 1
1.1.2 阻塞流水车间调度问题 3
1.2 国内外研究状况 3
1.2.1 国内研究状况 3
1.2.2 国外研究状况 4
1.3 本文研究内容 4
第二章 问题描述 6
第三章 CRO算法介绍 8
3.1 CRO算法概述 8
3.2 CRO算法的四种反应过程 9
3.2.1 单分子撞墙反应 9
3.2.2 分解反应 10
*好棒文|www.hbsrm.com +Q: @351916072@
3.2.3 双分子碰撞反应 12
3.2.4 合成反应 12
3.3 CRO算法流程 13
3.3.1 CRO算法基本参数 14
3.3.2 CRO算法实现步骤 15
第四章 CRO算法求解BFSSP 16
4.1 求解思路 16
4.2 编码 16
4.3 种群初始化 16
4.4 四种反应算子 16
4.4.1 碰墙反应 16
4.4.2 分解反应 17
4.4.3 双分子碰墙反应 17
4.4.4 合成反应 18
4.5 CRO算法实现 19
4.6 实验结果比较 20
第五章 改进的CRO算法求解BFSSP 22
5.1 CRO算法优化方法 22
5.2 种群初始化方法的改进 22
5.2.1 NEH算法介绍 22
5.2.2 PF算法介绍 23
5.2.3 混合NEH算法和PF算法的NEH_PF算法初始化种群 23
5.3 迭代贪婪算法 25
5.3.1 迭代贪婪算法介绍 25
5.3.2 迭代贪婪算法应用于BFSSP 25
5.4 PathRelinking算法 26
5.4.1 PathRelinking算法介绍 26
5.4.2PathRelinking算法应用于BFSSP 27
5.5 改进的CRO算法求解BFSSP 28
5.5.1 初始化种群 28
5.5.2 碰墙反应 29
5.5.3 分解反应 30
5.5.4 双分子碰撞反应和合成反应 31
5.5.5 改进的CRO算法实现 31
5.6 实验对比 32
结 论 37
致谢 38
参考文献 39 第一章 绪论
1.1 课题研究背景和意义
1.1.1 流水车间调度问题
流水车间调度问题，也被称为同序作业调度问题，该问题的研究始与20世纪50年代，Johnson首先对其进行研究，之后广大学者开始对该问题进行研究和扩展，并将其用于实际应用中。
流水车间调度问题一般可以描述为n个工件在m台机器上进行加工，每个工件都需要在m台机器上加工来完成每道工序，并且每道工序都只在一台机器上进行加工，每台机器也只能加工特定的工序。加工的n个工件的工序相同，每个工件在每台机器上的加工时间给定。流水车间调度问题的具有许多分类，比较具有代表性的几种流水车间调度问题为：
（1）无等待流水车间调度问题
无等待流水车间调度问题在传统流水车间调度问题基础上添加了同一工件相邻的两工序之间没有等待时间这一约束，对于此问题一般求解目标为最小化生产周期。该问题的甘特图如图11所示，在图11中有两个加工工件、，工件首先进行加工，工件的第一道工序的开工时间由于连续生产的要求与工件的第一道工序完工时间产生开工时间差，时间差为di, j 。
/
图11 无等待车间流水问题甘特图
（2）阻塞流水车间调度问题
阻塞流水车间调度问题在传统流水车间调度问题基础上添加了阻塞约束。该约束描述为当一个工件在一台机器上加工完成后，如果下一台机器正在加工，则因机器之间没有缓冲区，该工件只能滞留在上一台机器上，即该工件被阻塞了，阻塞状态会持续到下一台机器可用为止。图12描述的是3个工件在3台机器上进行加工的阻塞流水车间调度问题甘特图，第二个工件由于第二台机器上有第一个工件在加工，只能被阻塞在第一台机器上一段时间，直到第一个工件离开第二台机器。
/
图12 阻塞流水车间调度问题甘特图
（3）有限缓冲区车间调度问题
有限缓冲区车间调度问题基于流水车间调度问题的约束外同时约定：在每两台相邻的机器i和i+1之间存在大小为Bi的缓冲区，即工件j在机器i上完成后，如果下一台机器i+1上存在工件进行加工，则工件j将进入缓冲区，如果此时缓冲区已满，则工件j将被阻塞在当前机器上，工件在缓冲区中均服从先入先出规则。图13表示缓冲区为1的4个工件在3台机器上进行加工的甘特图，工件分别为π1，π2，π3，π4，阴影部分为工件进入缓冲区。
目 录
第一章 绪论 1
1.1 课题研究背景和意义 1
1.1.1 流水车间调度问题 1
1.1.2 阻塞流水车间调度问题 3
1.2 国内外研究状况 3
1.2.1 国内研究状况 3
1.2.2 国外研究状况 4
1.3 本文研究内容 4
第二章 问题描述 6
第三章 CRO算法介绍 8
3.1 CRO算法概述 8
3.2 CRO算法的四种反应过程 9
3.2.1 单分子撞墙反应 9
3.2.2 分解反应 10
*好棒文|www.hbsrm.com +Q: @351916072@
3.2.3 双分子碰撞反应 12
3.2.4 合成反应 12
3.3 CRO算法流程 13
3.3.1 CRO算法基本参数 14
3.3.2 CRO算法实现步骤 15
第四章 CRO算法求解BFSSP 16
4.1 求解思路 16
4.2 编码 16
4.3 种群初始化 16
4.4 四种反应算子 16
4.4.1 碰墙反应 16
4.4.2 分解反应 17
4.4.3 双分子碰墙反应 17
4.4.4 合成反应 18
4.5 CRO算法实现 19
4.6 实验结果比较 20
第五章 改进的CRO算法求解BFSSP 22
5.1 CRO算法优化方法 22
5.2 种群初始化方法的改进 22
5.2.1 NEH算法介绍 22
5.2.2 PF算法介绍 23
5.2.3 混合NEH算法和PF算法的NEH_PF算法初始化种群 23
5.3 迭代贪婪算法 25
5.3.1 迭代贪婪算法介绍 25
5.3.2 迭代贪婪算法应用于BFSSP 25
5.4 PathRelinking算法 26
5.4.1 PathRelinking算法介绍 26
5.4.2PathRelinking算法应用于BFSSP 27
5.5 改进的CRO算法求解BFSSP 28
5.5.1 初始化种群 28
5.5.2 碰墙反应 29
5.5.3 分解反应 30
5.5.4 双分子碰撞反应和合成反应 31
5.5.5 改进的CRO算法实现 31
5.6 实验对比 32
结 论 37
致谢 38
参考文献 39 第一章 绪论
1.1 课题研究背景和意义
1.1.1 流水车间调度问题
流水车间调度问题，也被称为同序作业调度问题，该问题的研究始与20世纪50年代，Johnson首先对其进行研究，之后广大学者开始对该问题进行研究和扩展，并将其用于实际应用中。
流水车间调度问题一般可以描述为n个工件在m台机器上进行加工，每个工件都需要在m台机器上加工来完成每道工序，并且每道工序都只在一台机器上进行加工，每台机器也只能加工特定的工序。加工的n个工件的工序相同，每个工件在每台机器上的加工时间给定。流水车间调度问题的具有许多分类，比较具有代表性的几种流水车间调度问题为：
（1）无等待流水车间调度问题
无等待流水车间调度问题在传统流水车间调度问题基础上添加了同一工件相邻的两工序之间没有等待时间这一约束，对于此问题一般求解目标为最小化生产周期。该问题的甘特图如图11所示，在图11中有两个加工工件、，工件首先进行加工，工件的第一道工序的开工时间由于连续生产的要求与工件的第一道工序完工时间产生开工时间差，时间差为di, j 。
/
图11 无等待车间流水问题甘特图
（2）阻塞流水车间调度问题
阻塞流水车间调度问题在传统流水车间调度问题基础上添加了阻塞约束。该约束描述为当一个工件在一台机器上加工完成后，如果下一台机器正在加工，则因机器之间没有缓冲区，该工件只能滞留在上一台机器上，即该工件被阻塞了，阻塞状态会持续到下一台机器可用为止。图12描述的是3个工件在3台机器上进行加工的阻塞流水车间调度问题甘特图，第二个工件由于第二台机器上有第一个工件在加工，只能被阻塞在第一台机器上一段时间，直到第一个工件离开第二台机器。
/
图12 阻塞流水车间调度问题甘特图
（3）有限缓冲区车间调度问题
有限缓冲区车间调度问题基于流水车间调度问题的约束外同时约定：在每两台相邻的机器i和i+1之间存在大小为Bi的缓冲区，即工件j在机器i上完成后，如果下一台机器i+1上存在工件进行加工，则工件j将进入缓冲区，如果此时缓冲区已满，则工件j将被阻塞在当前机器上，工件在缓冲区中均服从先入先出规则。图13表示缓冲区为1的4个工件在3台机器上进行加工的甘特图，工件分别为π1，π2，π3，π4，阴影部分为工件进入缓冲区。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/rjgc/853.html
