本书系统地研究了生产调度问题和智能求解算法，并根据实际应用提出了求解复杂调度问题的改进算法，获得了比较满意的调度结果。本书以流程工业、离散型制造工业和半导体制造工业中的生产调度问题为研究对象。在对微粒群算法的基本思想和原理阐述分析的基础上，提出了判断微粒群算法是否出现早熟收敛现象的收敛方法。详细讨论分析了DNA遗传算法的原理和基本流程。针对实际生产调度问题中普遍存在的不确定性因素，讨论了提前/拖后流水车间调度问题，并给出了不确定性问题的数学描述。以半导体生产过程中炉管区的调度问题为研究对象，在具体数学模型描述的基础上，将其分解为两个子问题，即在满足加工批量约束的情况下，对同类元件如何进行分批以及对各批元件如何进行机器的选择。

本书详细阐述了微粒群算法和DNA遗传算法等新型群体智能优化算法的基本原理，以及在Flow-shop、Job-shop型生产调度问题、带约束条件的模糊交货期流水车间调度问题和半导体生产调度问题上的研究应用。本书在分析比较各种典型生产调度问题特点的基础上，研究了不同调度算法在这些生产调度问题中的应用，通过对实际生产调度问题的仿真实验，并将仿真结果进行分析和比较，得出了有效和实用的改进算法，为企业生产运作管理提供了科学的指导方法。

本书适合管理专业或计算机专业的本科生和研究生以及生产调度人员阅读。

第1章　绪论　1

 1.1　本书写作背景及意义　1

 1.2　本书主要内容　3

第2章　生产调度问题及其优化方法　5

 2.1　生产调度问题的提出　5

2.1.1　生产调度问题　6

2.1.2　生产调度问题的分类　7

 2.2　车间生产调度问题　8

2.2.1　车间生产调度问题的描述　8

2.2.2　车间调度问题的特点　9

2.2.3　Job-shop、Flow-shop和可重入型的车间调度问题　9

 2.3　生产调度问题的优化方法　11

2.3.1　调度策略的研究　12

2.3.2　生产调度方法的研究　13

 2.4　小结　18

第3章　人工生命与群体智能　19

 3.1　人工生命　19

3.1.1　人工生命的研究思想　20

3.1.2　人工生命的研究结构　20

3.1.3　人工生命的研究动态　21

 3.2　群体智能　23

3.2.1　群体智能的研究起源　24

3.2.2　群体智能算法的原理　24

3.2.3　群体智能的研究动态　25

 3.3　群体智能与人工生命的关系　27

3.3.1　群体智能与人工生命的区别　27

3.3.2　群体智能与人工生命的联系　27

 3.4　小结　28

第4章　微粒群算法　29

 4.1　微粒群算法　29

4.1.1　微粒群算法的基本思想　29

4.1.2　微粒群算法的参数设置　30

4.1.3　微粒群算法的框架理念　31

4.1.4　微粒群算法的设计及流程　32

4.1.5　微粒群算法的收敛性分析　36

 4.2　微粒群算法与其他优化方法的比较　39

 4.3　微粒群算法的应用现状　39

 4.4　小结　40

第5章　DNA遗传算法　41

 5.1　DNA算法　41

5.1.1　DNA算法的基本原理　41

5.1.2　DNA组成结构　42

5.1.3　DNA分子操作技术　43

5.1.4　DNA计算与软计算的集成　44

5.1.5　DNA算法的研究现状及应用　45

 5.2　DNA遗传算法　46

5.2.1　DNA遗传算法的基本概念　46

5.2.2　DNA遗传算法的实现技术　47

5.2.3　DNA遗传算法与遗传算法的比较　48

 5.3　小结　49

第6章　作业型生产车间的微粒群调度算法　51

 6.1　作业车间调度问题描述　51

 6.2　基于作业调度问题的微粒群算法　53

6.2.1　编码　53

6.2.2　局部极值的判断　54

6.2.3　建立记忆库　56

6.2.4　动态设定惯性权重　57

6.2.5　自适应的交叉机制　57

6.2.6　自适应的变异机制　58

6.2.7　改进微粒群算法的流程　58

 6.3　仿真算例　60

 6.4　小结　63

第7章　流水型生产车间的DNA遗传调度算法　65

 7.1　流水车间调度问题的描述　66

 7.2　DNA遗传算法　67

 7.3　改进DNA遗传算法　71

7.3.1　建立工序问题的DNA计算模型　71

7.3.2　编码方法　72

7.3.3　适应度函数　73

7.3.4　分裂算子　74

7.3.5　变异算子　74

7.3.6　选择算子　74

 7.4　仿真算例　75

 7.5　小结　78

第8章　模糊交货期流水车间的微粒群调度算法　81

 8.1　模糊交货期调度问题　82

8.1.1　订单完成期的模糊描述　85

8.1.2　订单的实际处理时间　86

8.1.3　模糊目标函数　86

 8.2　提前/滞后流水车间(FSSP)的混合微粒群算法　87

8.2.1　提前/滞后FSSP问题的描述　87

8.2.2　引入惩罚函数　88

8.2.3　动态惯性权重　89

8.2.4　引进交换子、交换序　90

8.2.5　引入禁忌搜索机制　91

8.2.6　混合微粒群算法的流程　92

 8.3　仿真算例　92

 8.4　小结　96

第9章　半导体制造系统的调度问题　97

 9.1　半导体制造产业的战略意义　97

 9.2　半导体生产过程及制造工艺　98

9.2.1　半导体生产制造过程　98

9.2.2　半导体生产的工作区域　99

9.2.3　半导体生产制造工艺　100

 9.3　半导体制造系统调度　104

9.3.1　半导体制造系统调度问题的特点　105

9.3.2　半导体制造系统调度的约束　106

9.3.3　半导体制造系统的调度分类　107

9.3.4　半导体制造系统的调度策略　110

 9.4　小结　111

第10章　半导体炉管区生产调度的微粒群算法　113

 10.1　半导体炉管区的生产调度　113

10.1.1　半导体炉管区的生产情况　113

10.1.2　半导体炉管区调度问题的数学描述　114

 10.2　基于群体智能调度模型的双层微粒群算法　116

10.2.1　半导体炉管区群体智能调度模型　116

10.2.2　实现集中优化控制的C_PSO算法　117

10.2.3　实现分布式动态控制的D_PSO算法　119

10.2.4　算法流程　120

 10.3　仿真算例　121

 10.4　某半导体制造公司6寸线炉管区批量调度实例　128

 10.5　小结　133

第11章 结束语　135

参考文献　139

附录　149

4.2 微粒群算法与其他优化方法的比较

1.微粒群算法与遗传算法的比较

微粒群算法与遗传算法有很多共同之处，在大的进化步骤上基本是相同的。微粒群算法是依据自己的搜索经验和同伴的搜索经验，采用全局搜索和局部搜索相结合的搜索模式得到微粒下一个位置；而遗传算法是采用优势个体的选择、交叉、变异的方式产生下一代。在计算时遗传算法有编码、解码、选择、交叉和变异等操作；而微粒群算法是l通过对速度与位置的修改来完成的，微粒的位置也不像遗传算法那样由于受到编码的限制而不够灵活。从某种意义上讲，微粒群算法的搜索比遗传算法更具随机性，因此更不容易落入局部最优。

2.微粒群算法与BP算法的比较

BP算法在训练神经网络时是利用单一初始值以梯度下降模式进行；而微粒群算法在训练神经网络时是以一群微粒，即很多个初始值采用依据自己的经验结合群体的经验，有导向的随机搜索模式进行。因此，微粒群算法陷入局部极值的概率大大降低。此外，BP算法在训练神经网络时，需要较复杂的求导计算，导致它对目标函数、传递函数都有要求(要求可求导)，隐含层层数也不宜过多。而微粒群算法在训练神经时，无需求导计算，因而对神经网络的层数、目标函数和神经元的传递函数等都没有限制，使用更为灵活方便，应用范围大大拓宽。

微粒群算法与传统的优化方法相比具有很多优点。首先，在优化目标函数的性态上没有特殊要求，甚至可以将传统优化方法无法表达的问题描述为目标函数，使算法与数学模型更容易结合，应用更具广泛性。其次，微粒群算法的随机搜索本质使得它更不容易落入局部最优，而基于适应值的概率进化特征又保证了算法的快速性。因此，微粒群算法对于复杂的，特别是多峰值的优化计算问题具有很强的优越性。

4.3 微粒群算法的应用现状

微粒群算法是最早应用于人工神经网络的训练方法，Kennedy和Eberhart成功地将微粒群算法应用于分类XOR问题的神经网络训练上。作为一个演化神经网络的例子，微粒群算法已应用于分析人颤抖的诊断，包括帕金森(Parkinson)病和原发性颤抖，这是一个非常具有挑战性的领域。同时微粒群算法已成功地应用于演化一个用来快速和准确地辨别普通个体和有颤抖个体的神经网络，而网络的输入则为从一个活动变化记录系统中获得的归一化移动振幅。

微粒群算法最直接的应用就是多元函数的优化问题，包括带约束的优化问题。特别是在电力系统、集成电路设计、系统辨识、状态估计等问题中的应用。参考文献78是使用微粒群算法对一个电气设备的功率反馈和电压进行控制。采用一种二进制与实数混合的微粒群算法来决定对连续和离散的控制变量的控制策略，以得到稳定的电压。如果所讨论的函数受到严重的噪音干扰而呈现非常不规则的形状，同时所求的不一定是精确的最优值，微粒群算法能得到很好的应用。此外，微粒群算法还在动态问题中得到应用。一般而言，微粒群算法与其他演化算法一样，能用于求解大多数优化问题。在这些领域中，最具潜力的有多目标优化、模式识别、信号处理、工作调度的决策制定、实时机器人路径设计和图像分割等。

总之，由于微粒群算法概念简单、实现容易，短短几年时间便获得了很大的发展，目前已广泛应用于函数优化、神经网络训练、模糊系统控制等领域。在“国际演化计算会议”CEC国际年会上，微粒群算法被作为一个独立的研究分支，与遗传算法、进化规划等进化算法相提并论，从而受到国内外相关领域众多学者的关注与研究。

P39-40

随着社会经济的发展，决定生产经营过程能否稳定高效运转的调度问题的复杂性不断提高。生产调度问题是涉及运筹学、应用数学、人工智能学以及计算机科学等学科的综合性问题，具体来讲，它是研究在满足一定技术与资源约束条件下操作的排序，并且按照排定的秩序给操作分配资源，最终使某个执行目标达到最优或近优的管理理论。其研究的范围包括车间作业调度问题、流水车间调度问题和柔性车间调度问题等。生产调度问题是具有多约束、多目标、随机不确定性质的组合优化问题，寻找调度问题的精确最优解十分困难，因此生产调度问题已经被证明是属于NP-hard性质的问题(NP问题是可以在一个多项式时问内验证一个解是否正确的问题，NP-hard是指NP难度的问题)。研究有效的智能算法来求解生产调度问题是一个具有应用价值和科学研究意义的课题。

近年来各种不同的人工智能方法被广泛应用到调度领域中，如模拟退火算法、神经网络算法、遗传算法等。然而，随着人们对生命本质的不断了解，生命科学正以前所未有的速度迅猛发展，它使人工智能的研究开始摆脱经典逻辑计算的束缚，大胆探索起新的非经典计算途径——DNA遗传算法以及群体智能(Swarm Intelligence)——微粒群算法。群体智能是一种在自然界生物群体所表现出的智能现象启发下提出的智能模式，是计算智能领域的关键技术之一。

本书系统地研究了生产调度问题和智能求解算法，并根据实际应用提出了求解复杂调度问题的改进算法，获得了比较满意的调度结果。本书具体的研究工作主要集中在以下几个方面。

1.以流程工业、离散型制造工业和半导体制造工业中的生产调度问题为研究对象。

2.在对微粒群算法的基本思想和原理阐述分析的基础上，提出了判断微粒群算法是否出现早熟收敛现象的收敛方法。

3.详细讨论分析了DNA遗传算法的原理和基本流程。

4.针对实际生产调度问题中普遍存在的不确定性因素，讨论了提前/拖后流水车间调度问题，并给出了不确定性问题的数学描述。

5.以半导体生产过程中炉管区的调度问题为研究对象，在具体数学模型描述的基础上，将其分解为两个子问题，即在满足加工批量约束的情况下，对同类元件如何进行分批以及对各批元件如何进行机器的选择。

本书由柳毅负责全书的组织、编写和最终定稿工作。马慧民、何志康等参与了本书相关章节的编写和调试脚本程序的工作，浙江工业大学软件学院院长王万良教授、上海理工大学管理学院副院长叶春明教授对本书进行了认真审阅，提出了许多建设性的指导和意见，使本书内容日臻完善，在此对他们所付出的辛勤劳动表示诚挚的感谢。同时，感谢杭州电子科技大学学术著作出版基金、杭州电子科技大学科研启动基金为编写、出版提供的经费资助。

本书在编写过程中，参考了部分图书和期刊论文资料，在书后以参考文献的形式列出。

信息技术的迅猛发展和企业管理的改革创新，时刻影响着企业生产调度优化问题的发展进程，尽管我们付出了很多的努力，但由于水平有限，加之时间仓促，书中难免存在不足之处，敬请读者不吝赐教。

编者

2008年8月于杭州电子科技大学