基于启发式调度规则的车间作业计划算法及仿真研究

武汉科技大学硕士学位论文基于启发式调度规则的车间作业计划算法及仿真研究姓名：黄竹君申请学位级别：硕士专业：机械制造及其自动化指导教师：熊禾根20090501基于启发式调度规则的车间作业计划算法及仿真研究作者：黄竹君学位授予单位：武汉科技大学相似文献(6条)1.学位论文熊禾根模具企业动态车间作业计划研究2005模具是工业产品成形的重要工艺装备之一，是国际上公认的关键工业。近二十几年来，随着国民经济的快速发展，我国模具工业得到了蓬勃的发展。然而，与发达工业国家相比，我国的模具工业水平仍存在差距，这种差距在企业管理方面表现得尤为明显。通过对我国多家模具企业的实地调研发现，模具生产管理是模具企业管理中的瓶颈所在。由于模具生产是由订单驱动的、产品生产的一次性和制造过程的经验性，造成车间级生产的计划性差，各种变更和意外冲突频繁，车间级的计划管理是模具企业的生产管理中最为薄弱的环节，也是模具企业管理者最为棘手的问题。针对这一状况，本文将模具企业的动态车间作业计划作为研究主题，对其中的关键技术进行了系统的理论研究，并以此为基础，开发了与车间现场实时监控相结合的模具企业动态车间作业计划系统——eManScheduling。从工件到达的性质和执行过程的变化来分，车间作业计划可分为静态车间作业计划和动态车间作业计划。动态车间作业计划通常包括两方面含义：工件随机陆续到达和执行过程中动态多变。根据模具企业的生产特点，显然，相应的车间作业计划应该属于动态车间作业计划。本文首先从模具企业动态车间作业计划的建模入手，采用面向对象的思想，系统地分析了任务、资源和加工三类对象中与车间作业计划相关的各类属性，建立了相应的动态车间作业计划模型。为了探索面向实际生产条件下车间作业计划的优化求解算法，提出了一类针对模具生产特点的特殊作业计划问题——平行机问题，并设计了一种改进的遗传算法。在该算法中，提出了“资源的工时能力指数”、“冗余机器基因库”的概念，为了兼顾算法的收敛速度和群体的多样性，在交叉算子中加入了针对父代和后代的赌轮选择，并设计了基于机器负荷的LBH启发式变异算子。与其它平行机问题求解算法相比，作者所提出的算法表现出较优越的性能。然而，从算例运行的时耗来看，遗传算法对模具企业实际生产的车间作业计划来说仍缺乏适用性。为此，基于模具制造过程的特点，进一步提出了一类考虑工序相关性的动态车间作业计划问题。通过对工序相关性的定义和描述，建立了相应的动态车间作业计划问题的优化模型和析取图模型，并提出了基于优先调度规则的启发式算法。在该算法中，设计了一种将FCFS与ODD组合在一起的随机选择规则RAN(FCFS,ODD)，通过对模拟实例的仿真运行可以看出，作者所提出的启发式算法和RAN(FCFS,ODD)优先调度规则具有较优越的性能。为了使所提出的启发式算法可获得实际应用，本文从模具企业车间作业计划系统实现的角度，对其它的相关关键技术也进行了系统的研究。为兼顾算法的实用性、简便性,减少算法的运行时间，提出了车间作业计划中时间参数转换的概念和相应的转换算法；为了均衡资源负载，最大限度地、合理地利用加工资源，提出了车间作业计划中加工资源优选的模糊决策方法；针对模具加工过程中通常出现的批处理、配作和多处理机等非传统调度问题，通过引入“组合工件”、“资源组”、“资源使用单位”、“工期”等概念，首次提出了将这两类非传统调度问题转化为传统调度问题的处理方法；为使动态车间作业计划系统与车间现场实时监控系统有效地集成，提出了日程车间作业计划时间长度的定性与定量确定方法以及对监控反馈信息的处理方法，并根据模具企业车间作业计划的特点，设计了模具关键路径的逆推搜索算法。在上述理论研究成果基础上，作者基于面向对象的编程思想，采用平台无关的面向对象的编程语言Java，开发了C/S模式的模具企业动态车间作业计划系统——eManScheduling。该系统充分考虑了模具企业的生产特点，并与车间实时监控系统进行了有效集成，实现了快速的自动排程，并提供了较强大的交互处理功能。在实际模具企业中的应用表明，本系统可有效地提高模具企业车间级生产的计划性、提高资源的利用率、缩短模具的制造周期，并预测出可能出现的模具延期，以便及时作出决策。2.学位论文吴培栋实际生产系统中考虑任务相关性的作业计划规则调度算法研究与实现2004Job-Shop调度问题是产品制造业中共存的问题,它是实际生产调度问题的高度简化.解决好这一问题,是有效利用企业现有的资源、合理制定企业和车间生产计划、保证按时交货、提高企业信誉、赢得更多的客户,使企业在竞争中得以生存的关键.Job-Shop调度问题属于一种难解的组合优化问题,人们为了解决这一难题已经付出了几十年的努力,取得了相当大的成果,但要彻底解决这一难题还需要作大量的工作.该文对这一领域的若干问题进行了较为深入的研究,取得了一些有益的成果.具体工作如下:1)给出了单件车间调度问题的定义,分析了单件车间作业调度研究的特点及意义,回顾了研究求解单件车间作业调度问题的主要历程及其方法.2)将项目管理中的相关性概念应用到单件车间的生产调度中.在以前的作业计划中,只考虑同一零件的各道工序之间的完成—开始相关,这显然不能完整准确地反映机械制造企业生产系统的实际情况,得出的作业计划也自然缺乏可行性.实际的机械生产系统可能存在着完成—开始(FS)、完成—完成(FF)、开始—开始(SS)、开始—完成(SF)四种类型.在该文中将上述的四种相关性均引入作业计划算法中加于考虑,从而完整地定义和反映了实际生产系统的各种加工技术约束,保证作业计划的可行性.3)在综合分析和研究相关文献的基础上,针对实际生产系统的特点、对作业计划的要求及对算法时间复杂度与空间复杂度的考虑,该文采用了优先调度规则算法来求解作业计划问题.由于优先调度规则具有较强的问题依赖性,即不同的调度规则针对不同的问题和不同的输入表现出不同的性能,因此,该研究针对八种不同的优先调度规则,对各自的算法进行了详细的叙述;4)利用Java语言编写了相应的应用程序.进一步地利用所编写的应用程序,对Job-Shopscheduling两个经典的benchmark问题(即标杆问题)FT06和FT10进行了运算;5)设计了考虑相关性的FT06和FT10的变体问题,对两个变体问题也进行了相应的作业计划运算;6)对四个问题的作业计划结果的进行了详细的分析,结果表明了算法的正确性和可行性;进一步对不同目标时各种调度规则的性能进行了分析和评价.3.学位论文周小明基于OPT的车间作业计划管理系统的研究与实现2006本论文根据我国制造业的生产特点，通过对我国制造业车间生产计划环节普遍采用的基于MRPⅡ的车间作业计划管理系统方面的现状分析，发现其存在的不足，提出采用最优生产技术(OPT)，探讨建立优化的制造型企业车间作业计划管理系统。该车间作业计划管理系统通过识别“瓶颈”，提高“瓶颈”资源的利用率，并按“瓶颈”决定的生产节奏，对其上游工序实行拉动式生产，对其下游工序实行推动式生产，使生产中的物料流比较顺畅，减少了库存，从而真正提高了系统的有效产出，并且生成的生产作业计划具有良好的可执行性，很好地克服了ERP中MRPⅡ模型的不足。结合对OPT理论的深入研究，作者就系统若干主要问题进行了研究，同时给出了关键问题的相关算法及其实现。对于多个生产任务争夺工作中心的情况，作者探讨了利用优先调度规则安排生产的问题。在系统功能需求分析阶段设计了系统的逻辑流程图和数据流图，完成了系统的UML建模和数据库的设计。在对软件系统分析和设计的基础上确定了软件系统所采用的体系结构、采用软件系统混合开发方法，选择了适当的开发工具。最后对可视化的用户界面进行了实现。4.学位论文蔺麦田基于eM-Plant的MES调度策略研究2009制造执行系统（MES）是位于上层计划管理系统与底层工业控制之间的面向车间生产的管理信息系统，是面向车间生产管理和控制的一种有效方法。作业车间调度问题是制造执行系统研究的核心和重点之一，它对于提高企业的资源利用率、提高产品的质量、缩短交货期、降低生产成本、提高企业在市场经济中的竞争力具有重要的意义。制造企业车间生产调度问题围绕车间生产加工过程中如何配置资源而实现车间生产调度优化而展开的，从数学模型的角度看，是在满足制造系统性能指标的基础上，对可用的制造资源分配为车间生产加工任务集。本研究针对作业车间调度问题，给出了一种基于模拟退火算法和eM-Plant仿真的调度策略，并利用Delphi开发了一个车间调度系统。主要内容如下：⑴针对传统车间作业调度算法运行时间长，复杂度大的缺点，提出了基于调度规则的模拟退火算法，该算法是一种新的随机搜索方法，能按一定条件接受较差解，因而能跳出局部最优，而得到全局最优解。⑵将排序的过程分为初始排序与优化排序。采用基于多目标决策的层次分析方法，得出了各种规则与系统评价指标之间的影响度，其结论为生产计划方案的选择提供了定量的参考依据。⑶经分析及实例验证、比较，利用这种算法求解车间调度问题，计算时间短，调度结果令人满意。⑷在分析车间作业计划的数学模型的基础上，运用专业仿真软件eM-Plant细化了车间调度系统的仿真模型，针对不同的生产任务进行了仿真分析，结合eM-Plant，通过交叉、变异等遗传算法的操作，实现了基于遗传算法的车间作业调度问题优化。5.学位论文徐海军面向MES的船舶柴油机加工车间调度系统研究2008全球市场竞争激烈，上层计划管理系统受市场影响越来越大，计划的适应性问题愈来愈突出，明显感到计划跟不上变化。面对客户对交货期的苛刻要求，面对更多产品的改型和订单的不断调整，企业的决策者逐渐认识到计划的制定和执行要依赖于市场和实际的作业执行状态，而不能单纯以物料和库存来控制生产。制造执行系统是在企业的信息化建设中出现断层的情况下出现的。ERP/MRPII等系统运用的整体效果不理想，使得如何集成企业的信息已经成为当务之急。目前MRPII/ERP软件，如SAP的R/3System、利玛信息技术公司的CAPMS等，大都为企业的上层生产计划管理系统，其中有些软件是从财务管理和物料管理角度开发的，在对车间级制造执行过程的管理上较弱，基本不能完善地解决生产过程中出现的复杂多变问题，软件的适应性比较差。例如，目前的大多数MRPII/ERP商品软件只能做到零部件级生产计划，而没有做到工序级生产计划。个别商品软件虽然做到工序级生产计划，但还是比较粗糙。在实际的应用中，难以充分利用企业的所有资源和能力，造成生产时紧时松，原料、上装或辅料等短缺。因此，解决生产计划的适应性，增加底层生产过程与计划层的信息流动及共享，实施制造执行系统以及对整个制造生产过程的有效管理控制己经成为一个重要的研究课题。本课题基于车间的现代生产管理思想----制造执行系统（ManufacturingExecutionSystems，MES），针对目前以多品种、小批量离散加工为特点的制造企业中存在的任务调度、生产中异常处理周期长及在制品等待时间长等车间计划调度问题，提出了一种基于设备的Petri网模型调度方法。在稳定主生产计划的基础上，能够对车间作业进行灵活调度，并进一步对目前计划调度工作进行改进与优化。本文主要开展了以下几方面的研究：1在分析MES和车间调度问题的研究现状和发展趋势基础上，对现阶段MES仍需解决的关键问题进行了研究分析。指出现阶段对MES的研究多停留在“解决计划层与控制层的信息断层“问题上。但是由于企业实施MES的最终目标是要实现整个企业的信息集成，以保证企业信息流的畅通，因此MES的功能应该扩大到整个生产执行层的实施制造管理。ERP系统服务于长周期的生产计划，往往是经过了数周或数月才能付诸执行。在这段时间间隔中，产品的需求和市场都在变化；制造环境也会发生变化，设备故障、物料延迟以及人力缺勤等都会造成生产的混乱，导致计划的失效。如何更好地利用车间实时的生产信息，缩短反应时间，尽可能避免计划赶不上变化的发生，是MES必须要考虑的问题。因此，解决生产计划的适应性，增加底层生产过程