随着智能制造的不断推进，分布式调度已经成为学术界和企业界的热点问题。《分布式流水车间调度与算法》融合考虑装配阶段、分批交付约束、阻塞约束和恶化时间约束、机器人约束、订单约束、阻塞约束和装配阶段、延展性序列相关切换时间和工件分组等几类典型分布式流水车间调度问题，分别建立了混合整数规划模型，研究了问题的先验知识和结构特性，探索了鲸鱼群优化、模拟退火、迭代贪心、非支配排序遗传、变邻域搜索等算法求解的关键理论与技术，提出了一系列具有创新性的优化调度理论，并设计了多种高效的调度方法。

目录
“智能科学技术著作丛书”序
前言
第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 与其他算法的对比 123
7.4 本章小结 126
参考文献 126
第8章 带阻塞约束和装配阶段的分布式阻塞流水车间节能调度 127
8.1 问题属性 127
8.2 改进的二代非支配排序遗传算法 127
8.2.1 解的编码 128
8.2.2 初始化 129
8.2.3 交叉和变异 133
8.2.4 局部搜索 137
8.3 实验分析 138
8.3.1 实验算例 138
8.3.2 实验参数 139
8.3.3 CPLEX模型验证 141
8.3.4 算法的性能分析 142
8.4 本章小结 150
参考文献 150
第9章 智能服装业调度问题实例验证 152
9.1 带装配阶段的分布式流水车间调度问题实例验证 152
9.1.1 工厂生产流程 152
9.1.2 实例数据导入 152
9.1.3 实例结果分析 153
9.2 带分批交付约束的分布式流水车间调度问题实例验证 154
9.2.1 工厂生产流程 154
9.2.2 实例数据导入 155
9.2.3 实例结果分析 156
9.3 本章小结 157
参考文献 157
第10章 制药业调度问题实例验证 158
10.1 带机器人约束的DPFSP实例验证 160
10.2 带机器人约束和订单约束的DPFSP实例验证 162
10.3 本章小结 165

第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通常包括两个阶段：加工阶段和装配阶段。在FSP的基础上添加了一个装配阶段，也就是先将每个工件按加工顺序进行加工，然后通过装配机将加工完的工件集中组装成不同的产品。针对装配式流水车间调度问题，文献[27]考虑了具有装配工序的FSP，建立了具有加工、安装及装配步骤的优化模型。针对装配式混合流水车间调度问题(hybrid assembly flow shop scheduling problem， HAFSP)，文献[28]和[29]分析了问题上下界，提出了一种分支定界法。文献[30]提出了一种带全局交换的邻域搜索方法。针对装配式柔性流水车间问题(flexible assembly flow shop problem，FAFSP)，文献[31]提出了一种遗传算法和禁忌搜索相结合的混合算法。文献[32]采用混合EDA来解决柔性装配流水车间调度问题，并使用了全局优化策略提高算法跳出局部*优的能力。文献[33]考虑了带有同构并行机床的一类问题，设计了有效的启发式算法，当工件数量变大时，该启发式算法渐近*优。文献[34]考虑了批量输送系统，并利用双层遗传算法来解决此问题。文献[35]考虑了释放时间，提出了灰狼优化算法进行解的优化。文献[36]考虑了异构装配机器，提出了四种混合元启发式算法。文献[37]提出了一种列生成方法。文献[38]考虑了分批和配送操作，提出了混合整数非线性规划模型，并设计了混合帝国主义竞争算法(hybrid imperialist competitive algorithm， HICA)。文献[39]在解决带有释放时间的两阶段流水车间调度问题的同时优化了总延迟和总完工时间，设计了一种启发式算法。文献[40]解决了具有累积学习能力的两级三机流水车间调度问题，并在小尺寸工件的分支定界法中考虑了下界约束，提出了六种改进的混合粒子群优化(particle swarm optimization，PSO)算法。文献[41]研究了两阶段AFSP，考虑了配送协同约束，提出了混合遗传算法，将反向学习和反向邻域相结合提高算法的搜索能力。文献[42]进一步研究了两阶段AFSP，设计了一种新颖的类电磁机混合算法。文献[43]解决了三阶段AFSP，为了*大限度地减小产品完工时间的加权和，提出了一种利用分支定界法求解的有效方法。文献[44]*次解决了多阶段AFSP，建立了混合二元线性优化模型，考虑了问题的下界，设计了九种有效的启发式算法。装配式流水车间调度问题相关研究如表1-1所示。
　　1.2.3 带装配阶段的分布式流水车间调度问题研究现状
　　　　带装配阶段的分布式流水车间调度问题(distributed assembly flow shop scheduling problem，DAFSP)融合考虑了装配式和分布式约束[45-46]，是一类具有现实生产特点的调度问题。近年来，相关研究主要围绕优化算法和约束处理两个方面展开。
　　　　在优化算法方面，文献[47]建立了问题模型，设计了启发式算法和变邻域下降算法相结合的混合算法。文献[48]提出了改进的迭代贪心算法，融合了局部搜索，设计了算法销毁和重构过程。文献[49]设计了基于EDA的模因算法，将EDA的勘探和局部搜索开采结合到模因算法框架中，建立了描述*优解概率分布的概率模型，改进了增强采样机制，并融合了基于关键路径的局部搜索策略。文献[50]提出了一种基于生物地理学的混合优化算法，融合了几类启发式算法，并嵌入了一种新的局部搜索。文献[51]提出了一种回溯搜索超启发式算法，设计了一种双层优化机制。文献[52]实现了一种改进的遗传算法，采用了贪婪交配池选择*优解，并设计了交叉策略来提高收敛速度。文献[53]通过三维矩阵立方体改进了EDA，提出了变邻域下降算法来提升求解质量。
　　　　在约束处理方面，文献[54]考虑了具有无等待约束的DAFSP，提出了利用加工时间*短法则，在变异阶段根据工厂的完工时间来插入工件，并改进了生物地理学算法。为了解决具有总流量准则约束的DAFSP，文献[55]提出了三种离散入侵杂草优化算法，融合了局部搜索策略。为了解决具有序列相关切换时间约束的DAFSP，文献[56]设计了遗传规划超启发式算法，其中遗传算法和启发式算法分别作为高层和低层策略来优化解。文献[57]考虑了模糊约束的DAFSP，改进了混合交叉熵算法解决分布式装配线问题，并设计了基于三角模糊排序的修正策略。为了解决具有随机加工时间约束的DAFSP，文献[58]提出了一种融合元启发式方法的有偏随机混合算法。
　　　　综上，DAFSP相关研究相对匮乏，还存在诸多挑战性难题。上述文献所考虑的约束中，大多数均考虑单一装配机问题，对多约束、分布式流水线加工过程尚需开展深入研究。表1-2展示了带装配约束的分布式流水车间调度问题的相关研究成果。
　　1.2.4 带分批交付约束的分布式流水车间调度问题研究现状
　　　　分批交付约束存在于诸多领域中，如分布式网络配置调度[59]。Wang等[60]提出了基于订单选择的分配问题。Yin等[61]集成了生产和分批交付调度过程。Qi等[62]研究了分批交付下的两代理调度。Basir等[34]在两阶段装配流水车间上提出了一种分批交付系统，并找到了合适的批次。Noroozi等[63]考虑了第三方物流配送，结合了生产调度和分批交付。石建力等[64]在研究铁路物流配送问题时，考虑了分批配送优化方式，以行驶时间和服务时间为优化指标，提出了局部搜索策略和扰动机制。Kong等[65]提出了一种准时化策略，以解决预制施工中的分批交付问题。Kazemi等[38]考虑了装配流水车间调度的分批交付。Agnetis等[66]建议在生产和工厂之间进行分批交付，主要业务包括加工和运输。Wang等[67]研究了供应链中分批交付给多个客户的FSP，其中包括加工和分批交付两个阶段。彭温馨[68]把订单分配和配送路径看成特殊的生产和配送问题进行研究，设计了四阶段的启发式方法进行求解。马士华等[69]提出了订单分批策略，考虑了时间问题，设计了动态时间窗，消除了等待时间以及闲忙不均的现象。彭剑[70]在多个工厂调度中，使用分批运输的方式解决了降低消耗成本的问题，提高了效率。杜苗苗[71]针对分批配送问题提出了两类配送，根据这两类配送分别进行了数学建模。