车间调度及其遗传算法

    书籍
    计算机书籍
本书主要介绍各种典型静态调度问题及其遗传算法的设计。全书由5章组成。第1章介绍调度问题的描述、分类和算法以及计算复杂性；第2章介绍遗传算法的理论与实现技术，包括算法流程、模式定理、隐含并行性、收敛性理论、收敛速度估计、算法设计（编码、适配值函数、算法参数、操作、终止条件、改进）、免疫遗传算法、并行遗传算法；第 3章介绍Job Shop调度描述、典型调度问题、Job Shop凋度的遗传算法编码、操作和框架设计、混合遗传算法、模糊 Job Shop凋度的遗传算法设计以及 Job Shop凋度的遗传算法综述；第 4章介绍 Flow Shop调度描述、常用启发式算法、典型调度问题以及置换 Flow Shop调度、多目标 Flow Shop凋度、批量可变 Flow Shop凋度、模糊Flow Shop调度和混合 Flow Shop调度以及它们的遗传算法设计；第 5章介绍并行机调度及其遗传算法设计，包括最小化最大完成时间、最小化最大加权推迟时间、最小化公共交货期下 E／T指标、一类带工艺约束并行机调度及其遗传算法设计。最后在附录中给出国际上常用的有关Benchmark问题。
本书适于作为控制科学与技术、管理科学、计算机科学、生产调度等学科的高年级本科生、研究生用作教材或参考书，也可供工程技术人员参考。

第1章 调度问题与计算复杂性
1．1 调度问题及其描述
1．1．1 调度问题
1．1．2 工件加工数据和特性的描述
1．1．3 机器加工环境的描述
1．1．4 加工性能指标的描述
1．1．5 性能指标的正规性、等价性和活动调度
1．1．6 调度问题的表示
1．1．7 Job Shop和 Flow Shop调度问题
1．2 调度算法分类与邻域搜索算法
1．2．1 调度算法分类
1．2．2 邻域搜索算法
1．3 计算复杂性与NP完全问题
1．3．l 计算复杂性基本概念
1．3．2 P，NP，NP－C，NP－hard
第2章 遗传算法理论与实现技术
2．1 遗传算法的基本流程
2．2 模式定理和隐含并行性
2．3 遗传算法的马尔可夫链描述及其收敛性
2．3．l 预备知识

　　 柔性制造系统作为一类复杂的人造系统，具有复杂性、递阶结构、不确定性、多目标、多约束、多资源相互协调等特点。鉴于其重要的应用价值和理论意义，相关的分析与控制的研究方法已受到工业界和控制界的广泛关注。制造系统的分析，是基于系统的已知配置和决策，在一定的假设条件下，对系统的各种性能进行评估；而制造系统的控制，则是根据一定的目标和约束来确定系统的配置和决策。研究控制策略的目的是提高系统的性能，而系统分析的目的则是更好地优化和控制系统。制造系统的分析和控制方法，从理论体系上可分为运筹学方法、马尔可夫链、排队论、极大极小代数、摄动分析法、Petri网、自动机／形式语言和仿真方法等。它们涉及系统的逻辑层次、时间层次和随机层次，进而形成离散事件动态系统的理论框架。
　　 生产调度是制造系统的一个研究热点，也是理论研究中最为困难的问题之一。调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路径、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益，有着极大的作用。由于系统建模方法的多样性，以及问题的侧重点不同，调度方法和研究对象也有明显的不同。就对象而言，有确定性和随机性调度、离散事件和连续事件调度、静态和动态调度等。就调度方法而论，有Gantt图法、构造型方法、动态规划、分支定界法、排队论方法、规则调度方法和仿真方法等。调度的优化指标包括正规性能指标和非正规性能指标，常用的指标有最大完成时间、平均加工时间、平均延迟时间、生产成本和 E／T指标等。
　　 目前，对调度理论的研究已受到广泛的关注，并取得了较大的进展，但还很不成熟。其中，对调度问题的复杂性研究已成为工程背景很强的一个应用数学分支。在算法研究方面，基于知识的方法和算法技术相结合的趋势正变得日趋显著，概率分析
　　方法在算法效率和性能方面的研究日益增多。对于难以求得最优解的问题，给出多项式时间的搜索方法具有很大的现实意义，同样，算法的随机性能分析也是比较有效的分析手段。算法研究中，最优化性能的渐近性分析具有理论指导性，而基于启发式算法的误差估计来确定次优度则无疑同样具有很大的意义。由于约束条件的存在导致难以建立数学模型，纯数学的方法往往不易奏效，也不易处理并发现象，因此，从工程中“满意”即可的实际需求出发，寻求满足约束条件的快速有效的优化算法正变得更有现实意义。迄今，计算复杂性理论表明，多数调度问题都属于NP难题，目标解的搜索涉及解空间的组合爆炸。线性规划、动态规划、分支定界和梯度下降等传统方法，或是需要目标函数的特殊信息，或是复杂度大，或是优化性能差，因而一般只能处理小规模问题，难以高效高质量地求解复杂问题。
　　 人们正是由于意识到基于计算和数值式的优化技术的弱点，以及调度问题的约束性、非线性、多极小性、不确定性、大规模性、多目标性等复杂性，才努力研究和发展了统计式全局搜索技术和人工智能的方法，例如模拟退火、遗传算法、禁忌搜索、进化规划、进化策略、神经网络方法、Lagrangian松弛方法和混沌优化等。这些优化算法通过模拟或揭示某些自然现象、过程和规律而得到发展，以人类认识和理解客观事物的知识、经验等作为解决问题的方法，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等，为解决复杂问题提供了新的思路和手段。迄今，这些算法独特的优点、机制及其非凡的优化能力，引起了国内外学者的广泛重视，并掀起了该领域的研究热潮，而且在诸多领域得到了成功应用，较满意地解决了一大批传
　　统优化方法难以解决的复杂问题。为此，国际上已设立了相应的学术协会和诸多相关的学术期刊与会议，而遗传算法则是其中研究与应用最广的一类优化算法。
　　 鉴于国际上生产调度和智能优化方法的研究热潮，本书主要介绍各种典型静态调度问题及其遗传算法的设计与实现。全书主要由5章组成，内容自成体系。第1章介绍调度问题与计算复杂性，包括对工件加工数据和特征、机器加工环境、加工性能指标的描述，进而给出调度问题的表示和分类，并着重介绍Job Shop和 Flow Shop两类典型调度问题；其次，对现有的调度算法进行分类，并介绍多种常用的邻域搜索算法；最后，对计算复杂性和NP等基本概念作简单介绍。第2章介绍遗传算法的理论与实现技术，首先阐述遗传算法的基本优化流程、模式定理和隐含并行性；其次介绍遗传算法的收敛性理论，包括算法的马尔可夫链描述、标准算法的收敛性和收敛速度估计，进而介绍一般可测状态空间上遗传算法的收敛性；然后，对遗传算法的编码、适配值函数、算法参数、算法操作、终止条件的设计进行介绍，并阐述遗传算法的改进研究和一种免疫遗传算法；最后介绍并行遗传算法。第3章介绍Job Shop调度问题及其遗传算法设计，首先对Job Shop调度进行描述，并介绍若干典型的调度问题；其次，介绍 Job Shop调度的多种遗传算法编码设计、算法操作和框架设计；进而，介绍Job Shop调度的一种有效混合遗传算法和一类模糊 Job Shop调度的遗传算法设计；最后，对Job Shop调度的遗传算法进行了简要综述。第4章介绍 Flow Shop调度及其遗传算法设计，首先对Flow Shop调度及其启发式算法进行介绍，进而介绍了若干典型 Flow Shop调度问题，然后分别介绍置换 Flow Shop调度、多目标Flow Shop调度、一类批量可变 Flow Shop凋度、模糊 Flow Shop调度和混合Flow Shop调度及其遗传算法设计。第 5章介绍并行机调度及其遗传算法设计，具体包括最小化最大完成时间的遗传算法、最小化最大加权推迟时间的遗传算法、最小化公共交货期下E／T指标的遗传算法和一类带工艺约束并行机调度的遗传算法设计。为读者研究方便，本书的附录给出了Job Shop和 Flow Shop的若干 Benchmark问题。
　　 本书可作为与生产调度及优化相关专业的师生、研究人员以及工程技术人员的参考书。由于作者水平有限，本书难免有不足之处，诚望读者批评指正。
　　 在本书编写过程中，清华大学自动化系郑大钟教授、王雄教授、赵千川副教授等给予了热心指导和建议，清华大学出版社王一玲老师等给予了大力支持，参与研究的有关学生做了大量工作，在此一并表示衷心的感谢。此外，本书的完成得到了国家自然科学基金（“复杂系统基于计算智能的混合优化理论与方法”（60204008》、国家攀登计划（970211017）、973国家基础研究项目（G1998020305，2002CB312200）、清华大学基础研究基金、清华大学骨干人才计划等项目的资助，这里谨致谢忱。
　　 王凌
　　 清华大学自动化系
　　 Email:wangling＠mail．tsinghua．edu.cn
　　 2002年9月于清华园