企业生产调度的智能优化方法

第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.3Job-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.1DNA算法41

5.1.1DNA算法的基本原理41

5.1.2DNA组成结构42

5.1.3DNA分子操作技术43

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

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

5.2DNA遗传算法46

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

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

5.2.3DNA遗传算法与遗传算法的比较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.2DNA遗传算法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

前言

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

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

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

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

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

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

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

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

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

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

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

编者

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

　　本书系统地研究了生产调度问题和智能求解算法，并根据实际应用提出了求解复杂调度问题的改进算法，获得了比较满意的调度结果。本书以流程工业、离散型制造工业和半导体制造工业中的生产调度问题为研究对象。在对微粒群算法的基本思想和原理阐述分析的基础上，提出了判断微粒群算法是否出现早熟收敛现象的收敛方法。详细讨论分析了DNA遗传算法的原理和基本流程。针对实际生产调度问题中普遍存在的不确定性因素，讨论了提前/拖后流水车间调度问题，并给出了不确定性问题的数学描述。以半导体生产过程中炉管区的调度问题为研究对象，在具体数学模型描述的基础上，将其分解为两个子问题，即在满足加工批量约束的情况下，对同类元件如何进行分批以及对各批元件如何进行机器的选择。　　本书详细阐述了微粒群算法和DNA遗传算法等新型群体智能优化算法的基本原理，以及在Flow-shop、Job-shop型生产调度问题、带约束条件的模糊交货期流水车间调度问题和半导体生产调度问题上的研究应用。本书在分析比较各种典型生产调度问题特点的基础上，研究了不同调度算法在这些生产调度问题中的应用，通过对实际生产调度问题的仿真实验，并将仿真结果进行分析和比较，得出了有效和实用的改进算法，为企业生产运作管理提供了科学的指导方法。　　本书适合管理专业或计算机专业的本科生和研究生以及生产调度人员阅读。