柔性制造系统研究与分析.docx

摘 要

ABSTRACT
Key words: Flexible Manufacturing System Activity Planning Static Scheduling Dynamic Scheduling Heuristic Algorithm

目 录
摘要 I
ABSTRACT II
第1章 绪 论 1
1.1 FMS系统生产计划调度的意义 1
1.2 生产调度发展及国内外研究现状 2
1.3 本课题研究的主要内容 6
第2章 FMS生产计划调度理论研究 8
2.1 生产调度中的基本概念 8
2.2 生产调度的分类 8
2.3 生产调度问题的特点 9
2.4 生产调度的研究方法 9
2.5 生产调度研究存在的问题 11
2.6 生产调度研究的发展趋势 12
第3章 FMS系统计划调度模型研究 13
3.1 FMS的概念 13
3.2 FMS系统生产计划调度框架 13
3.3 FMS作业计划 15
第4章 基于启发式算法的FMS作业计划方法 17
4.1启发式算法概述 17
4.2 FMS作业计划算法的优缺点 18
4.3 FMS作业计划的描述模型及约束条件 21
4.4 FMS作业计划启发式算法 22
4.4.1 FMS调度问题的数学描述 22
4.4.2 目标函数 23
4.4.3 FMS调度优先规则 23
4.4.4 启发式算法步骤 24
4.5实验结果与分析 26
4.5.1 FMS作业计划调度实例 26
4.5.2 结果分析 28
第5章 某企业FMS生产计划调度系统方案设计 29
5.1 某企业需求分析 29
5.2 车间生产计划调度系统组成 29
5.3 车间生产计划调度系统的开发环境与软件结构 30
5.4 车间生产计划调度系统作用 32
结束语 33
致谢 34
参考文献 35

第1章 绪 论
1.1 FMS系统生产计划调度的意义
制造业是国民经济的支柱产业。没有发达的制造业，就没有国家的真正繁荣和强大。制造技术[1]——完成制造活动所需一切技术手段的总称，是支持高质量制造业的技术后盾。
计算机集成制造系统（Computer Integrated Manufacturing System, CIMS）和智能制造系统等先进制造技术的典型代表，始终把加工制造过程作为重要的研究对象之一。随着电子技术、计算机技术的发展，制造设备自动化水平和加工能力得到了极大的提高，NC、CNC技术得到了普遍采用，柔性生产与制造应运而生，并迅速发展成为被广泛应用的柔性制造系统（Flexible Manufacturing System，简写FMS）。
FMS在提高生产效率和产品质量、保证交货期、提高系统可靠性、加强企业应变能力等方面已取得很大效益[2]。但是单纯将FMS的硬件设备组成一个系统，并不一定就能取得上述效果。再加上FMS制造过程的自动化水平的提高，指挥生产过程合理、高效运行的生产计划调度问题变得更加复杂，往往超出人的正常决策能力。依靠手工制订作业计划存在以下问题：
制订作业计划工作量大、烦琐，效率低；
对调度员素质要求高，计划质量难以保证；
对生产过程监控实时性差，影响调度的动态品质；
依赖人来指挥生产加工过程的传统模式已经远远不能适应FMS制造环境的需要，迫切需要研究有效的生产计划调度方法和建立实现这些生产计划调度方法的计算机生产计划调度管理系统。
作业排序问题[3]有着深刻的实际背景，是工农业生产、国防、科研、交通运输以及各种服务行业中普遍遇到的问题。作业调度问题的研究不仅具有重大的现实意义，而且具有深远的理论意义。作业调度就是根据产品制造需求合理分配产品制造资源，进而达到合理利用产品制造资源、提高企业经济效益的目的。它是产品制造行业中共存的问题，它与FMS中的工厂管理、产品制造层次紧密相关，是FMS领域中研究的重要课题。
一般地说，凡是有多个不同项目要完成，就有排序问题的存在[3,4]。这些问题的共同特征就是要将不同的任务安排一个执行的顺序和时间，将有限的人力、物力资源分配给不同的任务，使预定的目标达到最优。由于同一台设备上可能要加工的零件有多个，一个零件可能有多道工序要到多台设备上去加工，不同零件的加工工艺路线也可能不相同，而每道工艺的加工时间也可能不相同，这就使得排序问题非常复杂。n个任务在m台机器上不同的安排顺序得出的结果差别较大，怎样安排加工顺序，才能得到最优或近似最优的结果，就是调度问题；其中，“机器”可以指工厂里的各种机床、维修工人、轮船要停靠的码头、计算机的中央处理器、存储器、输入和输出单元，即代表“服务者”；而“任务”则是等待机床加工的各种零件、待修理的机器、即将停靠码头的轮船、等待处理的程序，即“服务对象”；对于一般的排序问题，“机器”和“任务”都有多个，调度问题要解决的是确定服务者对服务对象的服务顺序和时间，使目标函数达到最优。
大规模、复杂约束、多目标的调度问题是目前的研究热点，是接近实际生产的优化模型。生产调度是其中一类，该问题的研究对实际生产具有重要意义：对一般的生产调度问题，总完工时间（Total Flowtime）最小促使资源稳定有效地利用、任务的快速传递及在制品库存最小[5,6]；而最大完工时间（makespan）最小能减小总的生产周转时间，这些都是目前现代集成制造系统FMS、计算机系统和其他一些信息系统所关心的一些问题。
车间作业调度是FMS领域中研究的重要课题。同时也是在实际中应用最广的运筹学分支之一，研究它对于在现有资源条件下提高工作效率和经济效益有重要作用。
调度问题的研究自50年代就受到应用数学、运筹学、工程技术等领域的科学家们的重视，是一门十分古老的学科[3,7,8,9]。许多调度问题是NP难题，严重阻碍了调度问题研究取得重大进展和突破。象Flow-shop和Job-shop这样的典型加工问题，尽管已经对实际问题作了大量的抽象和简化，但在多数情况下仍为NP难题，更何况FMC、FMS这样的加工系统调度问题，较Flow-shop和Job-shop要复杂的多。因此，仅仅依靠基于解析优化技术方法，试图解决属于NP难题的调度问题，不可避免地遇到了难以逾越的障碍，其它如仿真方法等也同样受到NP问题的困扰。
由于一个好的作业调度方案不仅可以降低生产成本，而且可以提高企业产品的准时交货能力，从而增强企业的竞争力。所以，本题研究基于启发式算法的FMS作业计划方法，以满足实际工程应用中对于实时性和优解性需求。
1.2 生产调度发展及国内外研究现状
到目前为止，研究调度问题的主要理论仍然是产生于五十年代的经典调度理论(Classieal Seheduling Theory)。一般认为，Johnson于1954年对两台机器下作业排序问题的求解是经典调度理论产生的重要理论。他首先提出了n/m/F/Cmax问题的优化算法，并且在此基础上给3/F/Cmax中特殊情况算法。Jacks在他的个研究报告里首先提出了EDD规则；Smith也提出了单机(single Machine)问题的几个优化规则。这段时期的研究成果主要是提出了针对特殊的和规模较小问题的解析优化方法，一般仅适用于单机和简单的流水车间(F1ow-Shop)问题，研究范围较窄，但这些早期的工作为经典调度理论后来的发展奠定了基础。
六十年代，人们开始用一些普通的优化方法来解决调度问题，主要是一些数学规划方法(如分枝定界法和动态规划法)，如story、Ignall等的研究，同时也有人开始将启发式算法应用到调度问题的研究中去，如Gere、Gavt提出的方法。P.Mellor系统总结和归纳了调度问题的有关定义和概念，包括研究调度问题的12条假设、27个调度目标和一些解决问题的方法[10]，他注意到了调度理论同实际生产脱节的问题;conway等(1967)提出了调度问题的描述系统。六十年代末期，一个完整的经典调度理论体系开始初步形成。
七十年代，问题复杂性方面的理论工作开始了，人们发现大多数调度问题都是NP-complete问题或NP-hard问题，一般很难找到解决这些问题的快速算法，因此解决调度问题的启发式算法开始成为求解调度问题的重要算法。如Campvell、Gupta、Baker、Danwnbring、Garey和Gonzalez等都提出了很多重要的算法。panwalkar等回顾了二十年来调度理论的研究情况，总结和归纳出113条调度规则[11]，并对其进行了分类;我国学者越民义等开始研究调度问题。
八十年代初期，Stephen[20]等从三个方面对调度问题进行了重新考察，并根据调度理论在实际中的应用情况，对未来发展做了一些分析和预测，认为调度理论与实际的结合已经成为调度研究的首要问题。这个富有挑战性的课题吸引了来自机械制造、自动化技术、计算机科学、企业管理、系统工程和应用数学等多个领域的学者，许多跨学科领域的技术和方法被应用到调度问题研究中，调度成为一种跨学科的研究领域。其中一项最引人注目的工作是以Carnegie-Melfon大学的MFox为代表的学者们开展的基于约束传播的ISIS研究。这项研究标志了人工智能真正应用于调度问题，其后这方面出现了一系列重要的研究成果。八十年代后期，Rodammer等(1988)总结了生产调度的理论和实践方面的最新研究进展[12],他们从七个方面论述了有关生产调度的技术和方法，包括传统的调度理论、控制理论、人工智能和离散事件仿真等，同时也讨论了MRPΠ、JIT、和OPT等技术的应用情况，他们认为，生产调度无论在理论还是实践上都已经开始打破传统的界限。
九十年代，对调度问题的研究进入了高潮，各种研究手段得到了充分的发挥，同时还不断有新的研究工具被应用到调度研究当中。比较有代表性的技术有:遗传算法、人工神经网络、Petri网、模糊数学和系统仿真等，智能调度已成为调度研究的主流，其中分布式人工智能技术，特别是多代理技术在调度研究中的应用成为该领域的一个新的发展方向。近几年来，随着软件技术及其它相关技术的发展和计算机硬件性能的提高，开发智能化生产计划与控制系统的时机已慢慢成熟。目前，国外许多科研机构和软件公司都研究和开发了针对各种生产实际的生产作业计划和调度系统。在国内，许多高校和科研机构如清华大学、中科院沈阳自动化研究所和东北大学等单位参与了该领域的工作，有些成果已经在国家的CIMS示范工程中得到了一定程度的应用。但多数企业的车间生产作业计划与调度软件都是针对某生产车间定制的，它只能应用于特定的场合，而当前无论是开发者还是使用者，都迫切需要实现通用性好、适用面广、智能化程度高的生产作业计划及资源优化利用智能支撑系统。
车间生产过程的规划调度问题是车间控制的核心问题之一。如何采取有效的调度方法和优化技术，提高资源利用率，降低生产成本，成为先进制造技术在车间应用中的基础和关键。Saad等人采用基于合同网的投标机制，提出生产预留的方法来实现工艺规划和调度[13]。
孙志峻，朱剑英(2001)用遗传算法研究了具有柔性加工路径的作业车间的智能优化调度问题，提出了一种将遗传算法和分派规则相结合的调度算法，将加工计划与生产调度同时考虑，避免了加工计划和生产调度相脱节的弊端[14]。
Farhoodi在1990年提出了一个针对动态的车间调度问题的基于知识的优化方法，是基于知识的方法在调度问题中的很好的应用[15]。
赵良辉2006年结合车间调度问题的特点阐述了模拟退火算法在解决车间调度问题上的应用，提出了基于模拟退火算法的车间调度问题模型，并以Matlab为工具进行了仿真实验[16]。
王万良在2002年提出了基于神经网络的作业车间生产调度的新方法，给出了作业车间生产调度问题（JSP）的约束条件及其换位矩阵表示，提出了新的包括所有约束条件的计算能量函数表达式，得到相应的作业车间调度问题的Hopfield神经网络结构与权值解析表达式[17]。
Crauwels(1996)研究了一个单机器的批处理生产调度问题，通过数值仿真计算，比较了模拟退火、禁忌搜索、遗传算法和一种启发式算法，结果表明在该环境下启发式算法效果比较好[19]。
黄志在2006年描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法，该算法基于禁忌搜索技术。为了得到更好的结果，还将倒转技术引入到算法中。从对一组问题基准实例的实验计算结果看，该算法在合理的计算时间内对多个实例得到比2004年提出的ISSB算法更好的结果[20]。
Ouelhadj（2004）研究了钢铁生产中的连铸和热轧的生产过程，分析了一种基于代理的调度机制，设计了基于合同网络协议的两层投标机制，并将禁忌搜索算法包含在调度机制中，最后通过算例分析了该方法的效果[21]。
意大利科学家M.Dorigo、V.Maniezzo、A.Colorini等人提出了一种基于种群的模拟退化算法，从分利用，蚁群收索食物的过程与著名的商旅问题之间的相似性，通过人工模拟蚂蚁收索食物的过程求解车间作业调度问题[22]。
StefanHahndel等提出了作业车间中用于自治Agent的分布式任务规划方通过Agent之间的相互协调完成作业调度，并用面向对象的仿真环境进行了和验证[23]。
Miyashita提出在不牺牲规划/调度解的质量的条件下，用分布式的方法通Agent内与Agent之间的约束协调求解方法[24]。
CarlaP.Gomes等研究了作业车间分布式调度系统，赋予不同地位的Agent应的功能，研究同级Agent在相互作用的过程中产生的冲突问题。
韩国的先进科学与技术研究所(Korea Advaneed Institute of sciencea Teehnology)提出了一种构造多Agent系统的方法，并把它用于车间的调度，取得了良好的效果[25]。
沈阳自动化研究所张宇等研究了在敏捷制造环境下制造车间生产过程的调度问题，建立了多代理生产组织和运行模式生产过程动态调度系统框架结针对敏捷化调度的特殊性，提出了综合运用规则调度与多代理机制的动态调度法，并以仿真方法研究了其可行性[26]。
南京航天航空大学机电工程研究所乔兵等提出了一种基于合同网协议投标制的多Agent分布式动态作业车间调度方案。调度系统包括工作单元Agent、作业Agent和事件Agent[27]。
清华大学廖强等提出了一种基于现场总线的多Agent作业车间动态调度问题的解决方法。在该方法中，有一个起核心作用的Agent负责向其他辅助Agent发送调度任务，在所有辅助Agent调度完毕后，回收它们的调度结果，然后进行统统协调，最终得出一个调度方案[28]。
Shaw提出基于AI启发式搜索技术的FMS调度算法，所产生的调度由于存在争用资源的现象。Shaw发现好的启发知识有利于提高调度算法的计算效率来限制搜索，但是搜索的空间依然很大[29]。
Bruno基于专家系统来实现FMS调度，ES使用派遣规则选择送入到FMS中的工件，但即使具有高优先级的工件，如果不满足生产约束条件也不能被选中。同时，基于闭环队列网络平均值分析技术的启发率，用来检查诸如机器利用率、平均队列长度和批生产率等容量约束。利用规则库和性能分析器，通过一个仿真模型来获得系统状态轨迹，即调度结果[30]。
Kusiak提出一种使用基于规则的专家系统的FMS调度方案。正常情况下，它使用优先级规则来调度作业，但当作业由于资源冲突不能被调度时，利用决策表来选择可替换机器、刀具、夹具和物料传输设备。为解决资源冲突，Kusiak提出一个基于知识和优化算法的调度系统（KBSS），KBSS由知识库、推理机、算法库和数据库组成[31]。
Tamura等提出一种基于知识的在线调度方法，发现基于启发式派遣规则的动态调度方法由于缺乏全局观念，调度的效果依赖于特定的系统和特定的性能判据，因此提出在仿真和专家经验的基础上智能选择启发规则的动态调度方法[32]。
童刚等〔2001)提出了一种用于job一shop调度问题的改进禁忌搜索算法，该方法采用了HASH技术存储禁忌表[33]。
朱双东，夏文明提出了将Hopfield神经网络与模拟退火相结合以求解Job-Shop类调度问题的算法。该算法给出了Job-Shop类调度问题的约束条件,并且直接把问题的各种约束条件表示为Hopfield神经网络的能量函数项。为避免Hopfield神经网络容易收敛到局部极小解而产生非法调度解的缺点,将模拟退火算法应用于Hopfield神经网络求解,使Hopfield神经网络收敛到能量函数的全局最优解,从而保证神经网络输出是一个可行的调度方案[34]。
吴秀丽等针对多目标柔性作业车间调度优化无法找到唯一最优解的问题,提出多目标遗传算法和层次分析法模糊综合评判的分阶段优化策略。提出优化阶段和精选阶段的优化任务,优化阶段选出一组Pareto解集,精选阶段从Pareto解集中选出最优解;在精选阶段运用层次分析法和模糊评判集成的策略精选调度决策[35]。
潘全科等提出了用于解决作业车间调度问题的离散版粒子群算法。该算法采用基于工序的编码和新的位置更新策略,使具有连续本质的粒子群算法直接适用于调度问题。同时,克服粒子群算法容易陷入局部最优的缺陷,使粒子群算法和变邻域搜索算法的性能互补[36]。
张维存等提出一种主、从递阶结构的蚁群遗传求解算法。算法中,主级为蚁群算法,完成工件组合和加工路径选择;从级为遗传算法,完成主级约束下的设备排产。分别以工件延迟时间和设备可用能力为启发式信息,设计蚂蚁工件间和设备间的转移概率;以设备空闲时间最小为目标,设计从级染色体选择、多点交叉和多点变异3类遗传操作。从级染色体适应值取其代表调度方案中工件流通时间的倒数,从蚂蚁游历值取其对应从级染色体种群的最优适应值[37]。
潘全科等结合作业车间调度问题的关键路径理论,设计了一种具有多次退火过程的调度算法。该算法利用记忆表记录下降过程中的平衡点,当一次退火过程结束后,从表中取出各平衡点的温度、状态和抽样长度重新开始退火过程,直到记忆表为空。仿真结果表明该算法在求解质量和求解效率方面均有优势[38]。
朱笑奔，赵新，张为民基于仿真的车间作业计划系统可以增加系统的透明度,提高计划执行率，针对多品种小批量的生产模式,在eM-Plant软件上提出一种基于离散事件的仿真方案,开发了相应的系统模型和仿真算法,运行仿真系统,得到调度结果。采用上述仿真系统就某军工车间一计划周期的生产任务进行仿真,根据不同优先级的仿真算法,得到合理的车间作业计划[39]。
1.3 本课题研究的主要内容
作业计划及资源优化利用的问题对企业的生产效益有直接的影响，如何解决生产中的动态生产调度问题，成为调度研究的首要问题。优化调度算法仍然是调度研究的核心。
本文的主要内容：
1.

第2章 FMS生产计划调度理论研究
2.1 生产调度中的基本概念
调度和计划的概念界限比较模糊，定义也比较混乱，极易造成混淆。在工程应用中，经常从时间周期角度定义长期计划、中期计划、短期计划[40]；调度仅仅限定为生产故障和异常情况下动态调度或再调度。这种体系的问题在于，它仅仅代表了实现调度系统经常采用的一种典型运行模式的需求，不具有广泛意义。另一种倾向是将调度概念泛化，即将整个车间层次生产指挥范畴下的活动安排均称为调度，并将其分解为几个层次进行研究，涉及计划调度等一系列问题[41,42]。
本文不采用这两种体制，而是将计划和调度二者有机地结合起来，将计划问题定义为生产计划和作业计划，将调度问题定义为静态调度和动态调度[2]，其中作业计划和静态调度二者的意义是一致的，都是针对加工活动的排序和加工时间的确定问题。本文主要研究作业计划和静态调度的制订方法问题。这样既有利于与经典调度理论的衔接，又方便本论文研究问题的阐述。
在制造业范畴，生产调度问题是与生产计划密切相关的。生产计划是为实现某些生产目标，在满足一系列领域约束的前提下，对活动集合进行选择和排序，以实现上述生产目标的过程。调度则是在计划的基础上，从备选计划中执行一组可行计划，并且在满足对活动完成时间要求和有限共享资源约束的条件下，为每个活动分配所需资源和时间。两者的主要区别在于生产计划不涉及时间概念，调度则重点强调时间概念。
调度问题的背景十分丰富。Flow-shop和Job-shop是对实际生产系统的抽象，侧重于机器和工件两类资源，而且加工工艺路线唯一确定；FMS调度问题除涉及机器、物料两类资源外，还包括夹具、运输系统等多种资源，其工件加工有多种工艺路线可供选择（称为路径柔性），这些都使得问题变得更加复杂[43,44]。
为便于进一步开展研究，将调度问题按其应用特点分为静态和动态两大类问题[45]。静态调度：是在调度环境和任务确定已知的前提下的所谓事前调度（pre-scheduling）方案，此种调度方案对事前已知和确定的调度环境和任务有严重的依赖性；动态调度：是指调度环境和任务存在着不可预测的扰动的情况下所提供的调度方案，它不仅依赖于事前调度环境和任务，还与系统当前状态有关。动态调度的典型是规则调度方案。静态调度方案和动态调度方案之间的关系与控制系统中开环控制和闭环控制的关系相类似。
2.2 生产调度的分类
生产调度问题一般从以下四个方面进行分类[3,9] ：
1、 工件的数量
2、 机器的数量
3、 工艺和管理约束决定的加工模式
4、 优化指标
其中，1和2的含义是显而易见的，值得一提的是加工模式3，主要包括以下模式：
J：单件加工（Job-shop）
F：流水线加工（Flow-shop）
O：开放式加工（Open-shop）
F，Perm：序排列流水加工（Permutation flowshop）
K-parallel： K个机器并行加工（K-machine in parallel）
J，K-parallel：每道工序K个机器并行的单件加工（Job-shop with K-machine in parallel）
对于优化指标4，Mellor[46]列出了27个不同的指标，大体可分为三类：
① 有效利用资源为目的的指标，如 Cmax（最长完成时间）；
② 对需求的快速响应为目的的指标，如（平均完工时间）、（平均流程时间）、（平均等待时间）；
③ 以遵守交货期为目的的指标，如（最长延误时间），NT（延误交货工件数）。
2.3 生产调度问题的特点
目前大多数研究集中在作业调度上。生产调度问题具有以下几个特点[47]：
(1)复杂性：由于生产车间中工件、机器、缓存及搬运系统之间相互影响、相互作用、每个作业又要考虑它的加工时间、操作顺序、交货期等，因而相当复杂。
(2)动态随机性：在实际的生产调度系统中存在很多随机的和不确定的因素，比如作业到达时间的不确定性、设备的损坏/修复、作业交货期的改变、紧急定单等。
(3)多目标性:实际的计划调度往往是多目标的，并且这些目标间可能发生冲突。生产调度的性能指标可以是成本最低、库存费最少、生产周期最短、生产切换最少、设备利用率最高、最短的延迟，最小的提前或者拖期惩罚、三废最少等。这种多目标性导致调度的复杂性和计算量急剧增加。
(4)多约束性:生产车间中资源的数量、缓存的数量、工件的加工时间和加工顺序都是约束。此外还有一些人为的约束，如要求各机器上的负荷平衡等等。
2.4 生产调度的研究方法
在对调度问题进行研究的方法上，最初是集中在整数规划、仿真和简单的规则上。随着各种新的相关学科与优化技术的发展，在调度领域出现了许多新的优化方法，比如神经网络、模拟退火法、遗传算法、禁忌搜索法等，使得调度问题的研究向多元化方向发展，简述如下：
(1)运筹学方法
运筹学方法是将生产调度问题简化为数学规划模型，采用基于枚举思想的分枝定界法或动态规划算法解决调度最优化或近优化问题，属于精确方法。由于其计算复杂性的原因、只能实用于小规模的调度问题。
(2)基于规则的方法
对生产加工任务进行调度的传统方法是使用调度规则。该方法具有简单、易于实现、计算复杂度低等特点，能够用于动态实时调度系统中。但是近十年的研究表明并不存在一个全局最优的调度规则，它们的有效性依赖于对特殊性能需求的标准及生产条件。
(3)系统仿真的方法
基于仿真的方法不单纯追求系统的数学模型，侧重对系统中运行的逻辑关系的描述，能够对生产调度方案进行比较评价。由于制造系统的复杂性，很难用一个精确的解析模型来进行描述和分析。
(4)基于DEDS的解析模型方法
由于制造系统是一类典型的离散事件系统，因此，可以用研究离散事件系统的解析模型和方法去探讨车间调度问题，诸如排队论、极大/极小代数模型、Petri网等。调度中的排队论方法是一种随机优化方法，很难得到比较具体的细节。Petri网作为一种图形建模工具，具有很强的建模能力，对于描述系统的不确定性和随机性也具有一定的优越性。目前，Perti网模型用于FMS的调度还存在节点语义、重用性差、不能对高级的调度规则加以建模等缺点。
（5）遗传算法
遗传算法(GeneticAlgortihm)是一种基于进化论优胜劣汰、自然选择、适者生存和物种遗传思想的随机优化搜索算法，通过群体的进化来进行全局性优化搜索。
（6）模拟退火法
模拟退火方法是由Kirpartrick提出的一种随机优化方法，它把问题模拟成一个物理系统，把优化目标模拟成物理系统的能量，将优化求解过程模拟成物理系统逐步降温以达到最低能量状态的退火过程，优化搜索由一个温度参数控制。
模拟退火算法S(A)通过模拟退火过程，可找到全局(或近似)最优解。其基本思想为：把每种组合状态Si看成某一物质系统的微观状态，而将其对应的目标函数C(Si)看成该物质系统在状态Si下的内能；用控制参数T类比温度，让T从一个足够高的值慢慢下降，对每个T，用抽样法在计算机上模拟该体系在此T下的热平衡态，即对当前状态Si作随机扰动以产生一个新状态s’，如果侧C(s’)<C(s)，则接受s’为下一状态，否则以概率e一(c(s’)一c(s))接受。经过一定次数的搜索，认为系统在此温度下达到平衡，则降低温度T再进行搜索，直到满足结束条件。由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出局部极小，但它的收敛速度较慢。
（7）禁忌搜索法
禁忌搜索算法是由Glover提出的一种确定性迭代算法，其基本思想是从某一初始状态出发，对其临域进行搜索，在禁忌表的控制下，确定移动方向，直至得到满意解为止。禁忌搜索是一种迭代方法，它开始于一个初始可行解S，然后移动到领域N(S)中最好的解s’，即s’对于目标函数F(S)在领域N(S)中是最优的。然后，从新的开始点重复此法。目前TS在单机调度、并行多机调度、流水车间调度和Job-shop调度上都有应用，主要在选择初始解，确定合适的临域结构和禁忌表的处理，使用并行搜索结构提高算法的效率和有效性等方面开展工作。但是，TS算法理论还不够完善，多采用与其它算法的比较性仿真实验来说明其有效性。
（8）神经网络优化
HPofiodl神经网络模型的提出为求解各种有约束优化问题开辟了一条新途径，用Hopfield网络解决TSP问题就是其在组合优化问题中的最成功的应用之一。它的主要思路是:通过一个LyPalmov能量函数构造网络的极值，当网络迭代收敛时，能量函数达到极小，使与能量函数对应的目标函数得到优化。
(9)基于智能的调度方法
近年来受实际需要的推动，基于知识的智能调度系统和方法的研究取得了很大的进展。基于知识的调度方法是用专家系统自动产生调度或辅助人去调度。它是将传统的调度方法与基于知识的调度评价相结合的方法。各国科学家在MAS技术应用于制造业上已做了很多工作，建立了各种各样基于Agent的制造系统原型或仿真系统。
2.5 生产调度研究存在的问题
调度领域中的大部分问题都具有NP问题虽然对它的研究已有几十年的历史但至今尚未形成一套系统的方法和理论理论研究与实际应用之间还存在着很大差距尤其随着JIT Just-In-Time思想的广泛采用E/TEarliness/Tardiness调度问题即使得工件尽量按交货期完成变得越来越突出实际应用中的调度方法能够响应系统的动态变化但不能保证得到好的调度一些理论上的最优化方法能提供最优调度但由于其计算的复杂性并且忽略了很多实际因素离实际运用还有较大距离基于最优化的方法诸如动态规划算法与分枝定界算法等等由于其大多数是建立在对可能调度的部分枚举上因此只能解决小规模的调度问题距离实用还有较大距离。
由于大多调度问题属于一类NP困难组合问题因此寻找具有多项式复杂性的最优算法几乎是不可能的但因其解的最优性至今仍激发着学者们进行不断的探索各种近似启发式方法诸如基于规则的算法等由于能在合理的时间内产生比较满意的调度因此广泛应用于实际调度中但其往往对所得的调度解的次优性不能进行评估在这方面有必要探索更好的近似最优调度算法可以考虑增加合理的计算时间代价提高解的次优性各种基于统计优化的方法诸如模拟退火法遗传算法等提供了一种解决调度优化问题的新途径但同别的优化算法类似其也存在着一定程度的不足一般来说收敛到最优解很慢并且对于判断解的最优性也很困难在这方面也需要做进一步的研究在实际车间调度中车间计划与车间调度往往是分层进行的但这可能造成计划。
在实际调度中的不可行问题如何将计划与调度结合考虑以求总体的优化也是需要进一步研究的另外还有很多有待进一步研究的问题比如实际车间调度的多目标性等调度理论方法与应用的研究是一项非常艰巨的工作目前人们还在进行各种各样的探索性研究工作。
2.6 生产调度研究的发展趋势
针对上述存在的问题，目前生产调度问题形成了下面的一些策略和发展趋势：
(1)并行或分布策略:为适合不同车间控制结构与高度复杂问题的需要，不少学者利用并行或分布策略来解决车间调度问题。
(2)分解与成组策略:利用分解生产计划或GT的调度策略可以大大降低问题的复杂性和规模，求得调度问题的较优解，同时优化系统的一些性能指标。
(3)人机交互策略:大量的研究表明人机交互策略可以减小系统的搜索时间，可在有限的时间、背景知识条件下解决一些困难的调度问题。
(4)动态重调度策略:车间制造过程的随时性和不确定性需要不断的进行重调度，以处理突发的事件。基于目前的研究，对于动态调度的具体策略有周期调度、连续调度、事件驱动调度、周期与事件驱动混合调度，周期与连续调度混合等。
(5)生产计划与调度集成策略:生产计划与调度的集成研究具有全局优化的特征，也符合先进制造模式的思想，同时提高了生产系统的柔性。
(6)多目标权衡决策:实际调度问题是多目标的，且这些目标往往相互冲突，如何对调度系统的不同目标进行权衡分析，实现多目标调度化是十分必要的。
(7)异地生产调度策略:作为AM模式的关键技术之一，异地生度策略也成为近期的研究热点，具有比较广阔的应用前景。

第3章 FMS系统计划调度模型研究
3.1 FMS的概念
柔性制造系统FMS（Flexible Manufacturing Systems，简称FMS）是由数控加工设备，物料运储装置的计算机控制系统等组成的自动化制造系统，它包括多个柔性制造单元，能根据制造任务或生产的变化迅速进行调整，适用于多品种，中、小批生产。FMS具备以下特点：
硬件包括三部分：
① 两台以上的数控机床或加工中心以及其它的加工设备，包括测量机，清洗机等。
② 一套能自动装卸的运输系统，包括刀具的运储和工件及原材料的运储。具体结构可采用有轨小车、无轨小车、搬运机器人等。
③ 一套计算机控制系统及通讯网络。
软件包括：
① FMS的运行控制系统，具体包括计划、调度、异常调整等模块。
② FMS的质量保证系统。
③ FMS的数据管理和通讯网络系统。
具有的功能：
① 能自动管理零件的生产过程。
② 简单地改变软件或系统参数，便能制造出某一零件族的多种零件。
③ 物料的运输和储存必须是自动的（包括刀具等工装和工件的自动运输）。
④ 能解决多机床条件下零件的混流加工，且无须额外增加费用。
⑤ 具有优化计划调度管理功能，能实现无人化或少人化加工。
3.2 FMS系统生产计划调度框架
柔性制造系统FMS是由物料自动储运系统将若干机床连接起来，在系统控制计算机的统一控制下进行加工的自动化系统。由于FMS具有投资大、系统运行管理复杂等特点，故其生产计划调度十分重要。国内外FMS的应用实践表明，FMS的效益和优点是潜在的，单纯将FMS的硬件设备合理地组成一个系统，并不一定就能取得最优效果，在实践中，还必须以有效的系统运行管理措施为保证。FMS的运行管理是通过FMS中计算机软件系统实现的，该软件的核心是FMS生产计划与调度理论与技术，FMS的运行管理从本质上也是在系统信息集成的基础上制订出使FMS能以最优方式运行的若干决策。因此FMS的生产计划与调度理论在FMS的运行管理中起着核心作用。
FMS生产计划调度问题也称为FMS生产管理决策问题。在FMS生产计划调度过程中不断对制造资源所面临的多种选择做出判断决策，有效地实现生产管理与运行控制的最佳结合，提高系统设备的利用率，缩短生产周期，协调设备负荷等目标。FMS生产计划调度分为三个层次，即FMS生产计划、FMS作业计划（静态调度）和FMS动态调度，三者的关系如图3.1。
图3.1FMS生产计划调度系统
① FMS生产计划：其主要任务是接收订单，并根据零件交货期的先后顺序分析排定零件的优先级，并根据各零件的工时定额、交货期要求和优先级情况，进行生产任务的一次初始任务分配，将车间生产任务落实到月计划或旬计划。对于被加工的零件集合而言，初始任务分配相当于一次对加工零件的分组，它是以天为单位进行的，一组零件的数量限制在一个月（一旬或一天）所能加工完成的范围内。其主要优化目标是，在保证按订单规定的交货期内完成所有加工任务的前提下，为进一步车间的生产创造优良的运行任务环境。
② FMS作业计划（静态调度）：FMS作业计划（又称静态调度）是对FMS系统的月（旬或日）生产计划的细化，其优化目标是在满足生产任务交货期的前提下，尽可能提高设备资源的利用率，减少系统调整时间，最终使整个生产系统的生产周期最短。为此，静态调度要完成工件分组、工件组组间排序、加工设备的负荷平衡分配及工件各工序的静态排序。静态调度要完成零件工序级的排序安排，一般排序时间具体到分钟或秒级，静态调度的结果要限定具体零件工序的开始加工时间和结束加工时间。它是车间实际调度的依据。
③ 动态调度：动态调度是在FMS加工过程中进行的，它的调度对象主要是系统内正在加工和在装夹站前排队等待加工的零件，它根据系统资源的实时状态动态地安排零件的加工顺序，尽可能保证FMS作业计划的按期执行。
从FMS计划调度系统的控制结构和运行管理过程中，不难看出FMS作业计划（静态调度）是整个FMS车间管理、运行、控制的核心，它既是对FMS生产计划进一步执行所需的毛坯、设备等资源的排序，也是指挥FMS系统实际运行的重要依据，它是车间调度的核心，在FMS车间生产管理与运行中具有承上启下的作用。FMS作业计划的制定是本文的主要研究重点。
3.3 FMS作业计划
FMS作业计划是在接收月、旬或天生产计划的基础上，根据系统各种资源（设备、毛坯、夹具等）实时状态数据，以及零件工序的额定工时、各种辅助工时信息，制订FMS具体的工序级作业计划，该计划将确定规定的计划期间内各种制造设施的使用状况，各种零件按照