内容简介
随着智能制造的不断推进，分布式调度已经成为学术界和企业界的热点问题。《分布式流水车间调度与算法》融合考虑装配阶段、分批交付约束、阻塞约束和恶化时间约束、机器人约束、订单约束、阻塞约束和装配阶段、延展性序列相关切换时间和工件分组等几类典型分布式流水车间调度问题，分别建立了混合整数规划模型，研究了问题的先验知识和结构特性，探索了鲸鱼群优化、模拟退火、迭代贪心、非支配排序遗传、变邻域搜索等算法求解的关键理论与技术，提出了一系列具有创新性的优化调度理论，并设计了多种高效的调度方法。
目录
目录
“智能科学技术著作丛书”序
前言
第1章 绪论 1
1.1 典型调度问题背景 1
1.2 国内外研究现状 3
1.2.1 分布式流水车间调度问题研究现状 3
1.2.2 装配式流水车间调度问题研究现状 3
1.2.3 带装配阶段的分布式流水车间调度问题研究现状 5
1.2.4 带分批交付约束的分布式流水车间调度问题研究现状 6
1.2.5 带机器人约束的分布式流水车间调度问题研究现状 7
1.2.6 带订单约束的分布式流水车间调度问题研究现状 8
1.2.7 阻塞流水车间调度问题研究现状 8
1.2.8 节能多目标调度问题研究现状 9
参考文献 9
第2章 几类分布式流水车间调度问题建模 18
2.1 置换流水车间调度问题 19
2.2 分布式置换流水车间调度问题 20
2.2.1 模型1 21
2.2.2 模型2 22
2.2.3 模型3 24
2.2.4 模型4 24
2.2.5 模型5 25
2.2.6 模型6 27
2.2.7 模型7 28
2.3 带起重机装配阶段的分布式流水车间调度问题 29
2.3.1 问题描述 29
2.3.2 问题实例 29
2.4 带分批交付约束的分布式流水车间调度问题 31
2.4.1 问题描述 31
2.4.2 问题实例 31
2.5 带阻塞约束和恶化时间约束的分布式流水车间调度问题 32
2.5.1 带阻塞约束的分布式流水车间调度问题 32
2.5.2 带恶化时间约束的分布式流水车间调度问题 33
2.6 带机器人约束的分布式流水车间调度问题 33
2.6.1 问题描述 33
2.6.2 问题建模 34
2.6.3 问题实例 36
2.7 带阻塞约束和装配阶段的分布式流水车间调度问题 37
2.7.1 问题描述 37
2.7.2 问题建模 38
2.8 带延展性序列相关切换时间和工件分组的分布式阻塞流水车间调度问题 42
2.8.1 问题描述 42
2.8.2 问题建模 43
2.9 本章小结 47
参考文献 47
第3章 几类智能优化算法 50
3.1 鲸鱼群优化算法 50
3.1.1 气泡网攻击 50
3.1.2 寻找猎物 51
3.1.3 WOA研究现状 52
3.2 模拟退火算法 53
3.3 迭代贪心算法 54
3.3.1 迭代贪心算法描述 55
3.3.2 迭代贪心算法求解单目标优化问题 55
3.3.3 迭代贪心算法求解双目标优化问题 56
3.3.4 迭代贪心算法混合策略 56
3.4 非支配排序遗传算法 56
3.5 变邻域搜索算法 57
3.6 本章小结 58
参考文献 59
第4章 带装配阶段的分布式流水车间调度问题 62
4.1 带装配阶段的分布式流水车间调度问题建模 62
4.2 算法设计 64
4.2.1 改进的鲸鱼群优化算法 64
4.2.2 问题编码解码和初始化 64
4.2.3 右移策略 65
4.2.4 交叉策略 68
4.3 实验分析 70
4.3.1 实验算例 70
4.3.2 实验参数 71
4.3.3 右移策略的有效性 72
4.3.4 交叉策略的有效性 74
4.3.5 与其他有效算法的对比 76
4.4 本章小结 78
参考文献 78
第5章 带分批交付约束的分布式流水车间调度问题 80
5.1 带分批交付约束的分布式流水车间调度问题建模 80
5.2 算法设计 81
5.2.1 编码解码 81
5.2.2 解的初始化 82
5.2.3 邻域结构 82
5.2.4 基于改进鲸鱼群优化算法的局部搜索策略 86
5.3 实验分析 86
5.3.1 实验算例 86
5.3.2 实验参数 86
5.3.3 邻域结构的有效性 88
5.3.4 与其他算法的对比 89
5.4 本章小结 92
参考文献 92
第6章 带机器人约束的分布式流水车间调度问题 93
6.1 IIG算法设计 93
6.1.1 算法框架 93
6.1.2 问题编码 94
6.1.3 问题解码 95
6.1.4 初始化策略 96
6.1.5 邻域结构 96
6.1.6 析构策略 98
6.1.7 重构策略 99
6.1.8 接受准则 99
6.2 实验分析 100
6.2.1 实验算例和实验参数 100
6.2.2 局部搜索策略的有效性 100
6.2.3 接受准则策略的有效性 102
6.2.4 与其他算法的对比 103
6.3 本章小结 110
参考文献 110
第7章 带订单约束的分布式流水车间调度问题 111
7.1 问题描述 111
7.1.1 问题说明与假设条件 111
7.1.2 问题示例 112
7.2 改进的迭代贪心算法 113
7.2.1 算法框架 113
7.2.2 问题编码 114
7.2.3 问题解码 115
7.2.4 初始化 115
7.2.5 邻域结构 116
7.2.6 析构和重构阶段 118
7.3 实验分析 119
7.3.1 实验算例 119
7.3.2 实验参数 119
7.3.3 融合LS策略的有效性 120
7.3.4 融合SA接受准则策略的有效性 122
7.3.5 与
试读
第1章 绪论
随着智能制造的不断推进，调度问题越来越体现出其重要性。目前，典型的调度问题包括流水车间调度、混合流水车间调度、作业车间调度、柔性作业车间调度、开放车间调度等。随着企业不断国际化，分布式加工越来越成为典型的模式，因而，分布式调度问题已经成为学术界和企业界的热点问题。本章围绕几类典型的分布式流水车间调度问题的研究现状展开分析。
1.1 典型调度问题背景
中国制造业的革新迫切需要大力发展智能制造[1]。调度问题是智能制造的重要分支，而车间调度问题是调度应用中研究*广泛的分支。文献[2]指出超过四分之一的组装线以及加工制造过程都可视为流水车间调度问题(flow shop scheduling problem， FSP)。因此，FSP成为调度中*受关注的研究问题[3-6]。
图1-1(a)展示了一类典型生产车间示意图。服装业生产过程也是一类典型的调度问题，如图1-1(b)所示，生产过程具有典型的多品种、小批量生产等特点。我国是服装业产销大国，传统的服装生产主要依靠人力资源，如图1-2(a)所示。随着出口量的增加，人工劳动效率低、成本高、生产慢等缺点日益凸显。为了与时俱进，将智能化生产引入服装业，如图1-2(b)所示，通过机器加工代替手工，保证了生产高效性，降低了加工成本，提高了生产速度，从而能够满足国内外服装业的需求。进一步，随着经济全球化不断推进，与其他生产过程类似，服装业
图1-1 车间调度和服装业生产调度
图1-2 传统手工和新型智能化服装生产模式对比
生产方式也逐步进入分布式生产模式，实现了资源整合、降低成本、提高效率、快速生产的目标[3-4]。图1-3展示了服装业的典型分布式加工过程，主要包括加工、装配和分批交付(批处理)三大阶段。*先把加工服装需要的部件分配给各个工厂，之后进入工件加工阶段；加工后的工件进入产品装配阶段，借助搬运设备把加工完成的工件运输到装配机上进行装配；*后进入分批交付(批处理)阶段，根据客户的需求把装配好的服装交付给客户。
图1-3 服装业的典型分布式加工过程
F-factory(工厂)；M-machine(机器)；MA-machine assemble(装配机器)；C-customer(客户)
1.2 国内外研究现状
1.2.1 分布式流水车间调度问题研究现状
分布式流水车间调度问题(distributed flows shop scheduling problem， DFSP)已成为近年来的研究热点之一。文献[7]为求解该类问题，提出了一种改进的分布估计算法(estimation of distribution algorithm， EDA)，算法根据问题特征设计了局部搜索算子，显著提高了搜索能力。文献[8]提出了一种离散搜索(discrete search， DS)算法，设计了多样化生成法、改进法、参考集更新法、子集生成法以及子集重组选择法等五种方法。文献[9]设计了一种混合免疫算法(hybrid immune algorithm， HIA)，并将HIA与变异、疫苗接种操作算子相结合。文献[10]结合新的禁忌策略，融入了改进的强化局部搜索方法，实现了一种改进的禁忌算法。文献[11]提出了18种构造启发式算法，结合迭代贪心(iterated greedy， IG)算法，提升了算法求解能力。文献[12]设计了一种融合贪婪策略的化学反应优化方法。文献[13]提出了有界搜索迭代贪心算法，并嵌入了三种局部搜索策略以提升算法搜索能力。文献[14]采用多目标进化算法，设计了遗传算子和局部搜索相结合的混合策略，通过多层次优化来求解DFSP。文献[15]改进了教学优化算法，考虑了工厂负载和淘汰机制来提高算法性能。文献[16]采用了多目标鲸群算法，并与局部搜索算法相结合。
在约束处理方面，文献[17]在考虑无等待约束的DFSP中，提出了四种邻域搜索策略来避免陷入局部极小，提高了局部搜索能力。在考虑有限缓冲区约束的DFSP中，文献[18]在算法部分嵌入了单点交叉和有效的贪婪策略，以提高求解质量；文献[19]采用混合EDA来搜索*优解。在考虑零空闲约束的DFSP中，文献[20]提出了一种迭代贪心算法；文献[21]通过将教学优化算法和模因算法相结合来提高解的质量；文献[22]提出了一种头脑风暴算法求解带总延时约束的DFSP；文献[23]提出了一种基于模糊逻辑的混合分布估计算法，用来求解具有机器故障约束的DFSP，算法融合了一种基于模糊逻辑的自适应进化策略；文献[24]为了求解带阻塞约束的DFSP，构建了两类数学模型，设计了一种新的混合离散差分进化算法，改进了突变和交叉算子，融合了偏置分段算子来增加搜索信息的多样性；文献[25]考虑了顺序相关准备时间约束，并通过多班教学算法进行求解。
1.2.2 装配式流水车间调度问题研究现状
随着科学技术的飞速发展，企业不能仅满足于工件的加工，还急需具备多品种、小批量生产的能力，装配生产过程也因此产生并成为FSP的一个重要分支。装配式流水车间调度问题(assembly flow shop scheduling problem，AFSP)于1995年*次提出[26]。与FSP不同，一个典型的AFSP通常包
