《柔性制造系统研究与分析.doc》由会员分享,可在线阅读,更多相关《柔性制造系统研究与分析.doc(36页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【精品文档】如有侵权,请联系网站删除,仅供学习与交流柔性制造系统研究与分析.精品文档.摘 要近年来,随着FMS系统技术的推广和实施,FMS中的生产计划问题得到理论界和工业界的普遍关注,然而,由于理论研究与工程实际缺乏很好的沟通,无论是所研究的问题还是提出的调度方法都离实用化要求有相当的差距。因此,研究一种有效、适用的算法来解决FMS系统实际生产中的计划问题是一个值得研究的课题。 本论文围绕着有实际应用背景的FMS生产调度问题,研究新的调度方法和技术及它们在实际调度问题中的应用,主要在以下几个方面作了一些研究, FMS系统计划调度模型研究,并对FMS系统计划调度进行层次划分和层次关系的分析,重点
2、论述了FMS作业计划的内容和主要完成的功能。在分析了各种常用作业计划方法的基础上,提出了制定FMS作业计划的启发式传算法,本章描述了解决FMS作业计划调度最短完工时间问题的一种快速有效的启发式算法。该算法基于一种优先指派规则和随机规则,对实例能够得到最优解或近优解。最后为典型企业提出计划调度系统方案设计。关键词:柔性制造系统FMS 作业计划 静态调度 动态调度 启发式算法ABSTRACTRecently,with the development and implement of the technology of FMS system,the problem of productive pla
3、nning and scheduling in FMS system are getting the broad attention in the dotain of theory and industry .But because of the lack of communication between the theory and the pracitce,the questions and methods of scheduling being studied are all unpractical. So,it is worth studying to find effective a
4、nd applicable algorithms to sovle the problem of productive planning and scheduling in FMS system.The paper studied a new method of scheduling and its application in the practical productive problem.We studied on model of planning and scheduling in FMS.The paper partitioned the arrangement of planni
5、ng and scheduling in FMS system and analysised the relation of all the arrangement.We also discussed the content and the function of the planning in FMS system. Based on analysing commonly used methods of activity planning,We proposed the heuristic algorithm.In this paper ,heuristic algorithm for so
6、lving the minimum makespan problem of job shop scheduling was presented.The algorithm was based on priority dispatching rule and random rule .A lot of instances showed that they could get optial or near optial by the heuristic algorithm. Finally, we proposed scheduling system design for typical ente
7、rprises.Key words: Flexible Manufacturing System Activity Planning Static Scheduling Dynamic Scheduling Heuristic Algorithm目 录摘要IABSTRACTII第1章 绪 论11.1 FMS系统生产计划调度的意义11.2 生产调度发展及国内外研究现状21.3 本课题研究的主要内容6第2章 FMS生产计划调度理论研究82.1 生产调度中的基本概念82.2 生产调度的分类82.3 生产调度问题的特点92.4 生产调度的研究方法92.5 生产调度研究存在的问题112.6 生产调度研究
8、的发展趋势12第3章 FMS系统计划调度模型研究133.1 FMS的概念133.2 FMS系统生产计划调度框架133.3 FMS作业计划15第4章 基于启发式算法的FMS作业计划方法174.1启发式算法概述174.2 FMS作业计划算法的优缺点184.3 FMS作业计划的描述模型及约束条件214.4 FMS作业计划启发式算法224.4.1 FMS调度问题的数学描述224.4.2 目标函数234.4.3 FMS调度优先规则234.4.4 启发式算法步骤244.5实验结果与分析264.5.1 FMS作业计划调度实例264.5.2 结果分析28第5章 某企业FMS生产计划调度系统方案设计295.1
9、某企业需求分析295.2 车间生产计划调度系统组成295.3 车间生产计划调度系统的开发环境与软件结构305.4 车间生产计划调度系统作用32结束语33致谢34参考文献35第1章 绪 论1.1 FMS系统生产计划调度的意义制造业是国民经济的支柱产业。没有发达的制造业,就没有国家的真正繁荣和强大。制造技术1完成制造活动所需一切技术手段的总称,是支持高质量制造业的技术后盾。计算机集成制造系统(Computer Integrated Manufacturing System, CIMS)和智能制造系统等先进制造技术的典型代表,始终把加工制造过程作为重要的研究对象之一。随着电子技术、计算机技术的发展,
10、制造设备自动化水平和加工能力得到了极大的提高,NC、CNC技术得到了普遍采用,柔性生产与制造应运而生,并迅速发展成为被广泛应用的柔性制造系统(Flexible Manufacturing System,简写FMS)。FMS在提高生产效率和产品质量、保证交货期、提高系统可靠性、加强企业应变能力等方面已取得很大效益2。但是单纯将FMS的硬件设备组成一个系统,并不一定就能取得上述效果。再加上FMS制造过程的自动化水平的提高,指挥生产过程合理、高效运行的生产计划调度问题变得更加复杂,往往超出人的正常决策能力。依靠手工制订作业计划存在以下问题:制订作业计划工作量大、烦琐,效率低;对调度员素质要求高,计划
11、质量难以保证;对生产过程监控实时性差,影响调度的动态品质;依赖人来指挥生产加工过程的传统模式已经远远不能适应FMS制造环境的需要,迫切需要研究有效的生产计划调度方法和建立实现这些生产计划调度方法的计算机生产计划调度管理系统。作业排序问题3有着深刻的实际背景,是工农业生产、国防、科研、交通运输以及各种服务行业中普遍遇到的问题。作业调度问题的研究不仅具有重大的现实意义,而且具有深远的理论意义。作业调度就是根据产品制造需求合理分配产品制造资源,进而达到合理利用产品制造资源、提高企业经济效益的目的。它是产品制造行业中共存的问题,它与FMS中的工厂管理、产品制造层次紧密相关,是FMS领域中研究的重要课题
12、。一般地说,凡是有多个不同项目要完成,就有排序问题的存在3,4。这些问题的共同特征就是要将不同的任务安排一个执行的顺序和时间,将有限的人力、物力资源分配给不同的任务,使预定的目标达到最优。由于同一台设备上可能要加工的零件有多个,一个零件可能有多道工序要到多台设备上去加工,不同零件的加工工艺路线也可能不相同,而每道工艺的加工时间也可能不相同,这就使得排序问题非常复杂。n个任务在m台机器上不同的安排顺序得出的结果差别较大,怎样安排加工顺序,才能得到最优或近似最优的结果,就是调度问题;其中,“机器”可以指工厂里的各种机床、维修工人、轮船要停靠的码头、计算机的中央处理器、存储器、输入和输出单元,即代表
13、“服务者”;而“任务”则是等待机床加工的各种零件、待修理的机器、即将停靠码头的轮船、等待处理的程序,即“服务对象”;对于一般的排序问题,“机器”和“任务”都有多个,调度问题要解决的是确定服务者对服务对象的服务顺序和时间,使目标函数达到最优。大规模、复杂约束、多目标的调度问题是目前的研究热点,是接近实际生产的优化模型。生产调度是其中一类,该问题的研究对实际生产具有重要意义:对一般的生产调度问题,总完工时间(Total Flowtime)最小促使资源稳定有效地利用、任务的快速传递及在制品库存最小5,6;而最大完工时间(makespan)最小能减小总的生产周转时间,这些都是目前现代集成制造系统FMS
14、、计算机系统和其他一些信息系统所关心的一些问题。车间作业调度是FMS领域中研究的重要课题。同时也是在实际中应用最广的运筹学分支之一,研究它对于在现有资源条件下提高工作效率和经济效益有重要作用。调度问题的研究自50年代就受到应用数学、运筹学、工程技术等领域的科学家们的重视,是一门十分古老的学科3,7,8,9。许多调度问题是NP难题,严重阻碍了调度问题研究取得重大进展和突破。象Flow-shop和Job-shop这样的典型加工问题,尽管已经对实际问题作了大量的抽象和简化,但在多数情况下仍为NP难题,更何况FMC、FMS这样的加工系统调度问题,较Flow-shop和Job-shop要复杂的多。因此,
15、仅仅依靠基于解析优化技术方法,试图解决属于NP难题的调度问题,不可避免地遇到了难以逾越的障碍,其它如仿真方法等也同样受到NP问题的困扰。由于一个好的作业调度方案不仅可以降低生产成本,而且可以提高企业产品的准时交货能力,从而增强企业的竞争力。所以,本题研究基于启发式算法的FMS作业计划方法,以满足实际工程应用中对于实时性和优解性需求。1.2 生产调度发展及国内外研究现状到目前为止,研究调度问题的主要理论仍然是产生于五十年代的经典调度理论(Classieal Seheduling Theory)。一般认为,Johnson于1954年对两台机器下作业排序问题的求解是经典调度理论产生的重要理论。他首先
16、提出了n/m/F/Cmax问题的优化算法,并且在此基础上给3/F/Cmax中特殊情况算法。Jacks在他的个研究报告里首先提出了EDD规则;Smith也提出了单机(single Machine)问题的几个优化规则。这段时期的研究成果主要是提出了针对特殊的和规模较小问题的解析优化方法,一般仅适用于单机和简单的流水车间(F1ow-Shop)问题,研究范围较窄,但这些早期的工作为经典调度理论后来的发展奠定了基础。六十年代,人们开始用一些普通的优化方法来解决调度问题,主要是一些数学规划方法(如分枝定界法和动态规划法),如story、Ignall等的研究,同时也有人开始将启发式算法应用到调度问题的研究中
17、去,如Gere、Gavt提出的方法。P.Mellor系统总结和归纳了调度问题的有关定义和概念,包括研究调度问题的12条假设、27个调度目标和一些解决问题的方法10,他注意到了调度理论同实际生产脱节的问题;conway等(1967)提出了调度问题的描述系统。六十年代末期,一个完整的经典调度理论体系开始初步形成。七十年代,问题复杂性方面的理论工作开始了,人们发现大多数调度问题都是NP-complete问题或NP-hard问题,一般很难找到解决这些问题的快速算法,因此解决调度问题的启发式算法开始成为求解调度问题的重要算法。如Campvell、Gupta、Baker、Danwnbring、Garey和
18、Gonzalez等都提出了很多重要的算法。panwalkar等回顾了二十年来调度理论的研究情况,总结和归纳出113条调度规则11,并对其进行了分类;我国学者越民义等开始研究调度问题。八十年代初期,Stephen20等从三个方面对调度问题进行了重新考察,并根据调度理论在实际中的应用情况,对未来发展做了一些分析和预测,认为调度理论与实际的结合已经成为调度研究的首要问题。这个富有挑战性的课题吸引了来自机械制造、自动化技术、计算机科学、企业管理、系统工程和应用数学等多个领域的学者,许多跨学科领域的技术和方法被应用到调度问题研究中,调度成为一种跨学科的研究领域。其中一项最引人注目的工作是以Carnegi
19、e-Melfon大学的MFox为代表的学者们开展的基于约束传播的ISIS研究。这项研究标志了人工智能真正应用于调度问题,其后这方面出现了一系列重要的研究成果。八十年代后期,Rodammer等(1988)总结了生产调度的理论和实践方面的最新研究进展12,他们从七个方面论述了有关生产调度的技术和方法,包括传统的调度理论、控制理论、人工智能和离散事件仿真等,同时也讨论了MRP、JIT、和OPT等技术的应用情况,他们认为,生产调度无论在理论还是实践上都已经开始打破传统的界限。九十年代,对调度问题的研究进入了高潮,各种研究手段得到了充分的发挥,同时还不断有新的研究工具被应用到调度研究当中。比较有代表性的
20、技术有:遗传算法、人工神经网络、Petri网、模糊数学和系统仿真等,智能调度已成为调度研究的主流,其中分布式人工智能技术,特别是多代理技术在调度研究中的应用成为该领域的一个新的发展方向。近几年来,随着软件技术及其它相关技术的发展和计算机硬件性能的提高,开发智能化生产计划与控制系统的时机已慢慢成熟。目前,国外许多科研机构和软件公司都研究和开发了针对各种生产实际的生产作业计划和调度系统。在国内,许多高校和科研机构如清华大学、中科院沈阳自动化研究所和东北大学等单位参与了该领域的工作,有些成果已经在国家的CIMS示范工程中得到了一定程度的应用。但多数企业的车间生产作业计划与调度软件都是针对某生产车间定
21、制的,它只能应用于特定的场合,而当前无论是开发者还是使用者,都迫切需要实现通用性好、适用面广、智能化程度高的生产作业计划及资源优化利用智能支撑系统。车间生产过程的规划调度问题是车间控制的核心问题之一。如何采取有效的调度方法和优化技术,提高资源利用率,降低生产成本,成为先进制造技术在车间应用中的基础和关键。Saad等人采用基于合同网的投标机制,提出生产预留的方法来实现工艺规划和调度13。孙志峻,朱剑英(2001)用遗传算法研究了具有柔性加工路径的作业车间的智能优化调度问题,提出了一种将遗传算法和分派规则相结合的调度算法,将加工计划与生产调度同时考虑,避免了加工计划和生产调度相脱节的弊端14。Fa
22、rhoodi在1990年提出了一个针对动态的车间调度问题的基于知识的优化方法,是基于知识的方法在调度问题中的很好的应用15。赵良辉2006年结合车间调度问题的特点阐述了模拟退火算法在解决车间调度问题上的应用,提出了基于模拟退火算法的车间调度问题模型,并以Matlab为工具进行了仿真实验16。王万良在2002年提出了基于神经网络的作业车间生产调度的新方法,给出了作业车间生产调度问题(JSP)的约束条件及其换位矩阵表示,提出了新的包括所有约束条件的计算能量函数表达式,得到相应的作业车间调度问题的Hopfield神经网络结构与权值解析表达式17。Crauwels(1996)研究了一个单机器的批处理生
23、产调度问题,通过数值仿真计算,比较了模拟退火、禁忌搜索、遗传算法和一种启发式算法,结果表明在该环境下启发式算法效果比较好19。黄志在2006年描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法,该算法基于禁忌搜索技术。为了得到更好的结果,还将倒转技术引入到算法中。从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内对多个实例得到比2004年提出的ISSB算法更好的结果20。Ouelhadj(2004)研究了钢铁生产中的连铸和热轧的生产过程,分析了一种基于代理的调度机制,设计了基于合同网络协议的两层投标机制,并将禁忌搜索算法包含在调度机制中,最后通过算例分析了该方法的效果21
24、。意大利科学家M.Dorigo、V.Maniezzo、A.Colorini等人提出了一种基于种群的模拟退化算法,从分利用,蚁群收索食物的过程与著名的商旅问题之间的相似性,通过人工模拟蚂蚁收索食物的过程求解车间作业调度问题22。StefanHahndel等提出了作业车间中用于自治Agent的分布式任务规划方通过Agent之间的相互协调完成作业调度,并用面向对象的仿真环境进行了和验证23。Miyashita提出在不牺牲规划/调度解的质量的条件下,用分布式的方法通Agent内与Agent之间的约束协调求解方法24。CarlaP.Gomes等研究了作业车间分布式调度系统,赋予不同地位的Agent应的功
25、能,研究同级Agent在相互作用的过程中产生的冲突问题。韩国的先进科学与技术研究所(Korea Advaneed Institute of sciencea Teehnology)提出了一种构造多Agent系统的方法,并把它用于车间的调度,取得了良好的效果25。沈阳自动化研究所张宇等研究了在敏捷制造环境下制造车间生产过程的调度问题,建立了多代理生产组织和运行模式生产过程动态调度系统框架结针对敏捷化调度的特殊性,提出了综合运用规则调度与多代理机制的动态调度法,并以仿真方法研究了其可行性26。南京航天航空大学机电工程研究所乔兵等提出了一种基于合同网协议投标制的多Agent分布式动态作业车间调度方案
26、。调度系统包括工作单元Agent、作业Agent和事件Agent27。清华大学廖强等提出了一种基于现场总线的多Agent作业车间动态调度问题的解决方法。在该方法中,有一个起核心作用的Agent负责向其他辅助Agent发送调度任务,在所有辅助Agent调度完毕后,回收它们的调度结果,然后进行统统协调,最终得出一个调度方案28。Shaw提出基于AI启发式搜索技术的FMS调度算法,所产生的调度由于存在争用资源的现象。Shaw发现好的启发知识有利于提高调度算法的计算效率来限制搜索,但是搜索的空间依然很大29。Bruno基于专家系统来实现FMS调度,ES使用派遣规则选择送入到FMS中的工件,但即使具有高
27、优先级的工件,如果不满足生产约束条件也不能被选中。同时,基于闭环队列网络平均值分析技术的启发率,用来检查诸如机器利用率、平均队列长度和批生产率等容量约束。利用规则库和性能分析器,通过一个仿真模型来获得系统状态轨迹,即调度结果30。Kusiak提出一种使用基于规则的专家系统的FMS调度方案。正常情况下,它使用优先级规则来调度作业,但当作业由于资源冲突不能被调度时,利用决策表来选择可替换机器、刀具、夹具和物料传输设备。为解决资源冲突,Kusiak提出一个基于知识和优化算法的调度系统(KBSS),KBSS由知识库、推理机、算法库和数据库组成31。Tamura等提出一种基于知识的在线调度方法,发现基于
28、启发式派遣规则的动态调度方法由于缺乏全局观念,调度的效果依赖于特定的系统和特定的性能判据,因此提出在仿真和专家经验的基础上智能选择启发规则的动态调度方法32。童刚等2001)提出了一种用于job一shop调度问题的改进禁忌搜索算法,该方法采用了HASH技术存储禁忌表33。朱双东,夏文明提出了将Hopfield神经网络与模拟退火相结合以求解Job-Shop类调度问题的算法。该算法给出了Job-Shop类调度问题的约束条件,并且直接把问题的各种约束条件表示为Hopfield神经网络的能量函数项。为避免Hopfield神经网络容易收敛到局部极小解而产生非法调度解的缺点,将模拟退火算法应用于Hopfi
29、eld神经网络求解,使Hopfield神经网络收敛到能量函数的全局最优解,从而保证神经网络输出是一个可行的调度方案34。吴秀丽等针对多目标柔性作业车间调度优化无法找到唯一最优解的问题,提出多目标遗传算法和层次分析法模糊综合评判的分阶段优化策略。提出优化阶段和精选阶段的优化任务,优化阶段选出一组Pareto解集,精选阶段从Pareto解集中选出最优解;在精选阶段运用层次分析法和模糊评判集成的策略精选调度决策35。潘全科等提出了用于解决作业车间调度问题的离散版粒子群算法。该算法采用基于工序的编码和新的位置更新策略,使具有连续本质的粒子群算法直接适用于调度问题。同时,克服粒子群算法容易陷入局部最优的
30、缺陷,使粒子群算法和变邻域搜索算法的性能互补36。 张维存等提出一种主、从递阶结构的蚁群遗传求解算法。算法中,主级为蚁群算法,完成工件组合和加工路径选择;从级为遗传算法,完成主级约束下的设备排产。分别以工件延迟时间和设备可用能力为启发式信息,设计蚂蚁工件间和设备间的转移概率;以设备空闲时间最小为目标,设计从级染色体选择、多点交叉和多点变异3类遗传操作。从级染色体适应值取其代表调度方案中工件流通时间的倒数,从蚂蚁游历值取其对应从级染色体种群的最优适应值37。潘全科等结合作业车间调度问题的关键路径理论,设计了一种具有多次退火过程的调度算法。该算法利用记忆表记录下降过程中的平衡点,当一次退火过程结束
31、后,从表中取出各平衡点的温度、状态和抽样长度重新开始退火过程,直到记忆表为空。仿真结果表明该算法在求解质量和求解效率方面均有优势38。朱笑奔,赵新,张为民基于仿真的车间作业计划系统可以增加系统的透明度,提高计划执行率,针对多品种小批量的生产模式,在eM-Plant软件上提出一种基于离散事件的仿真方案,开发了相应的系统模型和仿真算法,运行仿真系统,得到调度结果。采用上述仿真系统就某军工车间一计划周期的生产任务进行仿真,根据不同优先级的仿真算法,得到合理的车间作业计划39。1.3 本课题研究的主要内容作业计划及资源优化利用的问题对企业的生产效益有直接的影响,如何解决生产中的动态生产调度问题,成为调
32、度研究的首要问题。优化调度算法仍然是调度研究的核心。本文的主要内容:1. 研究FMS系统计划调度模型,并对FMS系统计划调度进行层次划分和层次关系的分析,论述FMS作业计划的内容与功能。2.提出基于优先规则和随机数的启发式算法。然后通过两个典型的实例,对启发式传算法和其它算法进行了比较。3.开发FMS生产计划调度系统的需求分析,及软件的组成与基本功能。设计FMS计划系统的软件结构,设计FMS作业软件人机界面。第2章 FMS生产计划调度理论研究2.1 生产调度中的基本概念调度和计划的概念界限比较模糊,定义也比较混乱,极易造成混淆。在工程应用中,经常从时间周期角度定义长期计划、中期计划、短期计划4
33、0;调度仅仅限定为生产故障和异常情况下动态调度或再调度。这种体系的问题在于,它仅仅代表了实现调度系统经常采用的一种典型运行模式的需求,不具有广泛意义。另一种倾向是将调度概念泛化,即将整个车间层次生产指挥范畴下的活动安排均称为调度,并将其分解为几个层次进行研究,涉及计划调度等一系列问题41,42。本文不采用这两种体制,而是将计划和调度二者有机地结合起来,将计划问题定义为生产计划和作业计划,将调度问题定义为静态调度和动态调度2,其中作业计划和静态调度二者的意义是一致的,都是针对加工活动的排序和加工时间的确定问题。本文主要研究作业计划和静态调度的制订方法问题。这样既有利于与经典调度理论的衔接,又方便
34、本论文研究问题的阐述。在制造业范畴,生产调度问题是与生产计划密切相关的。生产计划是为实现某些生产目标,在满足一系列领域约束的前提下,对活动集合进行选择和排序,以实现上述生产目标的过程。调度则是在计划的基础上,从备选计划中执行一组可行计划,并且在满足对活动完成时间要求和有限共享资源约束的条件下,为每个活动分配所需资源和时间。两者的主要区别在于生产计划不涉及时间概念,调度则重点强调时间概念。调度问题的背景十分丰富。Flow-shop和Job-shop是对实际生产系统的抽象,侧重于机器和工件两类资源,而且加工工艺路线唯一确定;FMS调度问题除涉及机器、物料两类资源外,还包括夹具、运输系统等多种资源,
35、其工件加工有多种工艺路线可供选择(称为路径柔性),这些都使得问题变得更加复杂43,44。为便于进一步开展研究,将调度问题按其应用特点分为静态和动态两大类问题45。静态调度:是在调度环境和任务确定已知的前提下的所谓事前调度(pre-scheduling)方案,此种调度方案对事前已知和确定的调度环境和任务有严重的依赖性;动态调度:是指调度环境和任务存在着不可预测的扰动的情况下所提供的调度方案,它不仅依赖于事前调度环境和任务,还与系统当前状态有关。动态调度的典型是规则调度方案。静态调度方案和动态调度方案之间的关系与控制系统中开环控制和闭环控制的关系相类似。2.2 生产调度的分类生产调度问题一般从以下
36、四个方面进行分类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
37、46列出了27个不同的指标,大体可分为三类: 有效利用资源为目的的指标,如 Cmax(最长完成时间); 对需求的快速响应为目的的指标,如C()(平均完工时间)、F()(平均流程时间)、W()(平均等待时间); 以遵守交货期为目的的指标,如T()(最长延误时间),NT(延误交货工件数)。2.3 生产调度问题的特点目前大多数研究集中在作业调度上。生产调度问题具有以下几个特点47:(1)复杂性:由于生产车间中工件、机器、缓存及搬运系统之间相互影响、相互作用、每个作业又要考虑它的加工时间、操作顺序、交货期等,因而相当复杂。(2)动态随机性:在实际的生产调度系统中存在很多随机的和不确定的因素,比如作业到
38、达时间的不确定性、设备的损坏/修复、作业交货期的改变、紧急定单等。(3)多目标性:实际的计划调度往往是多目标的,并且这些目标间可能发生冲突。生产调度的性能指标可以是成本最低、库存费最少、生产周期最短、生产切换最少、设备利用率最高、最短的延迟,最小的提前或者拖期惩罚、三废最少等。这种多目标性导致调度的复杂性和计算量急剧增加。(4)多约束性:生产车间中资源的数量、缓存的数量、工件的加工时间和加工顺序都是约束。此外还有一些人为的约束,如要求各机器上的负荷平衡等等。2.4 生产调度的研究方法在对调度问题进行研究的方法上,最初是集中在整数规划、仿真和简单的规则上。随着各种新的相关学科与优化技术的发展,在
39、调度领域出现了许多新的优化方法,比如神经网络、模拟退火法、遗传算法、禁忌搜索法等,使得调度问题的研究向多元化方向发展,简述如下:(1)运筹学方法运筹学方法是将生产调度问题简化为数学规划模型,采用基于枚举思想的分枝定界法或动态规划算法解决调度最优化或近优化问题,属于精确方法。由于其计算复杂性的原因、只能实用于小规模的调度问题。(2)基于规则的方法对生产加工任务进行调度的传统方法是使用调度规则。该方法具有简单、易于实现、计算复杂度低等特点,能够用于动态实时调度系统中。但是近十年的研究表明并不存在一个全局最优的调度规则,它们的有效性依赖于对特殊性能需求的标准及生产条件。(3)系统仿真的方法基于仿真的
40、方法不单纯追求系统的数学模型,侧重对系统中运行的逻辑关系的描述,能够对生产调度方案进行比较评价。由于制造系统的复杂性,很难用一个精确的解析模型来进行描述和分析。(4)基于DEDS的解析模型方法由于制造系统是一类典型的离散事件系统,因此,可以用研究离散事件系统的解析模型和方法去探讨车间调度问题,诸如排队论、极大/极小代数模型、Petri网等。调度中的排队论方法是一种随机优化方法,很难得到比较具体的细节。Petri网作为一种图形建模工具,具有很强的建模能力,对于描述系统的不确定性和随机性也具有一定的优越性。目前,Perti网模型用于FMS的调度还存在节点语义、重用性差、不能对高级的调度规则加以建模
41、等缺点。(5)遗传算法遗传算法(GeneticAlgortihm)是一种基于进化论优胜劣汰、自然选择、适者生存和物种遗传思想的随机优化搜索算法,通过群体的进化来进行全局性优化搜索。(6)模拟退火法模拟退火方法是由Kirpartrick提出的一种随机优化方法,它把问题模拟成一个物理系统,把优化目标模拟成物理系统的能量,将优化求解过程模拟成物理系统逐步降温以达到最低能量状态的退火过程,优化搜索由一个温度参数控制。模拟退火算法S(A)通过模拟退火过程,可找到全局(或近似)最优解。其基本思想为:把每种组合状态Si看成某一物质系统的微观状态,而将其对应的目标函数C(Si)看成该物质系统在状态Si下的内能
42、;用控制参数T类比温度,让T从一个足够高的值慢慢下降,对每个T,用抽样法在计算机上模拟该体系在此T下的热平衡态,即对当前状态Si作随机扰动以产生一个新状态s,如果侧C(s)C(s),则接受s为下一状态,否则以概率e一(c(s)一c(s)接受。经过一定次数的搜索,认为系统在此温度下达到平衡,则降低温度T再进行搜索,直到满足结束条件。由于模拟退火法能以一定的概率接受差的能量值,因而有可能跳出局部极小,但它的收敛速度较慢。(7)禁忌搜索法禁忌搜索算法是由Glover提出的一种确定性迭代算法,其基本思想是从某一初始状态出发,对其临域进行搜索,在禁忌表的控制下,确定移动方向,直至得到满意解为止。禁忌搜索
43、是一种迭代方法,它开始于一个初始可行解S,然后移动到领域N(S)中最好的解s,即s对于目标函数F(S)在领域N(S)中是最优的。然后,从新的开始点重复此法。目前TS在单机调度、并行多机调度、流水车间调度和Job-shop调度上都有应用,主要在选择初始解,确定合适的临域结构和禁忌表的处理,使用并行搜索结构提高算法的效率和有效性等方面开展工作。但是,TS算法理论还不够完善,多采用与其它算法的比较性仿真实验来说明其有效性。(8)神经网络优化HPofiodl神经网络模型的提出为求解各种有约束优化问题开辟了一条新途径,用Hopfield网络解决TSP问题就是其在组合优化问题中的最成功的应用之一。它的主要
44、思路是:通过一个LyPalmov能量函数构造网络的极值,当网络迭代收敛时,能量函数达到极小,使与能量函数对应的目标函数得到优化。(9)基于智能的调度方法近年来受实际需要的推动,基于知识的智能调度系统和方法的研究取得了很大的进展。基于知识的调度方法是用专家系统自动产生调度或辅助人去调度。它是将传统的调度方法与基于知识的调度评价相结合的方法。各国科学家在MAS技术应用于制造业上已做了很多工作,建立了各种各样基于Agent的制造系统原型或仿真系统。2.5 生产调度研究存在的问题调度领域中的大部分问题都具有NP问题虽然对它的研究已有几十年的历史但至今尚未形成一套系统的方法和理论理论研究与实际应用之间还
45、存在着很大差距尤其随着JIT Just-In-Time思想的广泛采用E/TEarliness/Tardiness调度问题即使得工件尽量按交货期完成变得越来越突出实际应用中的调度方法能够响应系统的动态变化但不能保证得到好的调度一些理论上的最优化方法能提供最优调度但由于其计算的复杂性并且忽略了很多实际因素离实际运用还有较大距离基于最优化的方法诸如动态规划算法与分枝定界算法等等由于其大多数是建立在对可能调度的部分枚举上因此只能解决小规模的调度问题距离实用还有较大距离。由于大多调度问题属于一类NP困难组合问题因此寻找具有多项式复杂性的最优算法几乎是不可能的但因其解的最优性至今仍激发着学者们进行不断的探
46、索各种近似启发式方法诸如基于规则的算法等由于能在合理的时间内产生比较满意的调度因此广泛应用于实际调度中但其往往对所得的调度解的次优性不能进行评估在这方面有必要探索更好的近似最优调度算法可以考虑增加合理的计算时间代价提高解的次优性各种基于统计优化的方法诸如模拟退火法遗传算法等提供了一种解决调度优化问题的新途径但同别的优化算法类似其也存在着一定程度的不足一般来说收敛到最优解很慢并且对于判断解的最优性也很困难在这方面也需要做进一步的研究在实际车间调度中车间计划与车间调度往往是分层进行的但这可能造成计划。在实际调度中的不可行问题如何将计划与调度结合考虑以求总体的优化也是需要进一步研究的另外还有很多有待
47、进一步研究的问题比如实际车间调度的多目标性等调度理论方法与应用的研究是一项非常艰巨的工作目前人们还在进行各种各样的探索性研究工作。2.6 生产调度研究的发展趋势针对上述存在的问题,目前生产调度问题形成了下面的一些策略和发展趋势:(1)并行或分布策略:为适合不同车间控制结构与高度复杂问题的需要,不少学者利用并行或分布策略来解决车间调度问题。(2)分解与成组策略:利用分解生产计划或GT的调度策略可以大大降低问题的复杂性和规模,求得调度问题的较优解,同时优化系统的一些性能指标。(3)人机交互策略:大量的研究表明人机交互策略可以减小系统的搜索时间,可在有限的时间、背景知识条件下解决一些困难的调度问题。
48、(4)动态重调度策略:车间制造过程的随时性和不确定性需要不断的进行重调度,以处理突发的事件。基于目前的研究,对于动态调度的具体策略有周期调度、连续调度、事件驱动调度、周期与事件驱动混合调度,周期与连续调度混合等。(5)生产计划与调度集成策略:生产计划与调度的集成研究具有全局优化的特征,也符合先进制造模式的思想,同时提高了生产系统的柔性。(6)多目标权衡决策:实际调度问题是多目标的,且这些目标往往相互冲突,如何对调度系统的不同目标进行权衡分析,实现多目标调度化是十分必要的。(7)异地生产调度策略:作为AM模式的关键技术之一,异地生度策略也成为近期的研究热点,具有比较广阔的应用前景。第3章 FMS系统计划调度模型研究3.1 FMS的概念柔性制造系统FMS(Flexible Manufacturing Systems,简称FMS)是由数控加工设备,物料