生产调度及优化方法讲义综述21

生产调度方方法综述2011.6.8提纲生产调调度的的定义调度理论的的起源源和发发展生产计计划与与生产产调度度系统生产调调度系系统的的功能生产调调度问问题特特点：：两类车车间调调度类类型流水车车间调调度问问题的简化模型启发式式方法法简介结合启启发式式算法法的改改进遗遗传算算法生产调调度的的定义义产生背背景：：随着用户对对产品品需求求的快快速变变化,以及市市场竞竞争的的日趋趋激烈烈,现代制制造企企业需需要进进行多多品种种、小小批批量生生产,这种生生产方方式使使生产产的计计划、、组组织和和控制制变得得更加加复杂杂,另外要要求企企业对对生产产过程程中所所出现现的各各种信信息进进行及及时反反馈和和处理理,因此,生产调调度问问题作作为生生产管管理系系统的的核心心内容容和关关键问问题,其研究究具有有重要要的理理论和和实用用价值值。调度的的定义义：所谓调调度,就是为为了实实现某某一目目的而而对共共同使使用的的资源源进行行时间间上的的分配配。从从数学学规划划的角角度来来说,生产调调度问问题可可表述述为在在等式式或不不等式式约束束下,对目标标函数数所进进行的的优化化。调度理理论的的起源源和发发展从上个个世纪纪50年代起起,调度问问题的的研究究就受受到应应用数数学、、运运筹学学、工工程程技术术等领领域科科学家家的重重视,科学家家们利利用运运筹学学中的的线性性规划划、整整数数规划划、目目标标规划划、动动态态规划划及决决策分分析方方法,研究并并解决决了一一系列列有代代表意意义的的调度度和优优化问题20世纪70年代,人们开开始注注意并并重视视调度度复杂杂性问问题的的研究究,提出了了用于于研究究算法法有效效性和和问题题难度度的计计算复复杂度度理论论,许多调调度问问题被被证明明NP完全问题（非多多项式式确定定问题题），，计算算复杂杂。70年代后后，经经典调调度理理论得得到发发展并并作为为了一一门基基本成成熟的的应用用数学学学科科。但但是实实际调调度问问题与与经典典调度度问题题还有有相当当的距距离。调度理理论的的起源源和发发展实际调度问问题往往往都都是非非常复复杂的的,没有确确定的的物理理和自自然规规律可可循,因此是是非常常难解解的,并且大大多是是没有有精确确解的的。因因此,仅仅依依靠经经典调调度理理论中中基于于解析析优化化的技技术和和方法法,试图解解决属属于NP完全问问题的的实际际调度度问题题,不可避避免地地会遇遇到难难以逾逾越的的障碍碍。从20世纪80年代初初开始始,人们就就一直直在尝尝试并并致力力于解解决实实际调调度问问题,调度研研究由由理论论研究究转向向应用用研究究阶段段。在在这样样的历历史背背景下下,应用人人工智智能、、计计算智智能和和实时时智能能研究究成果果,解决实实际调调度问问题的的智能能调度度方法法就走走上了了历史史的舞舞台。。智能能调度度方法法和基基于反反馈控控制的的实时时调度度理论论和方方法为为解决决实际际调度度问题题展示示了光光明的的前景景。生产计计划与与生产产调度的的区别和和联系系生产计划（（ProductionPlanning）系统：：是以以企业业生产产经营营活动动为主主要依依据，，根据据产品品的市市场需需求、、原料料供应应情况况、企企业的的生产产能力力、装装置的的检修修情况况，综综合考考虑企企业的的管理理成本本以及及生产产过程程中成成品、、半成成品的的成本本，利利用物物料平平衡、、物料料物性性数据据等进进行平平衡分分析，，根据据不同同的生生产状状态和和计划划类型型模型型，运运用优优化方方法对对企业业的生生产经经营进进行优优化设设计，，辅助助计划划人员员完年年度、、季度度、月月度计计划编编制，，为企企业决决策者者提供供相关关预测测和决决策信信息，，却把把企业业利润润最大大。与生产产经营营活动动为中中心的的因素素：原原料供供应、、产能能、市市场需需求、、生产产设备备状态态等；；以产销销平衡衡为核核心；；以利润润企业业利润润最大大化和和完成成中长长期目目标为为最终终目标标；生产计计划与与生产产调度的的区别和和联系系生产调调度（（ProductionScheduling）系统统：在在满足足装置置设备备和工工艺要要求的的条件件下，，根据据市场场的需需求，，合理理的、、最佳佳地安安排与与组织织生产产过程程，以以提高高过程程系统统的操操作最最优性性，为为企业业带来来现出出的经经济效效益。内容包括：：产品的的生产产批次次数和和每批批的量量；使用的的生产产线；；产品的的生产产顺序序和时时间安安排；；原料供供应、、水、、电、、气、、汽、、冷、、人力力等资资源保保障和和限制制；生产计计划与与生产产调度的的区别和和联系系生产调度系系统的的特点点：时间：：它将将长期期生产产计划划分解解为短短期计计划并并执行行，例例如2天、5天，这这可以以大大大降低低问题题的复复杂性性；任务：：生产产安排排和资资源分分配———涉涉及到到实际际生产产环境境的各各种约约束；核心心：：生生产产装装置置的的分分配配利利用用和和物物料料平平衡衡；目标标：：以以最最少少的的消消耗耗保保质质保保量量地地完完成成生生产产计计划划；；生产产计计划划与与生生产产调度度的的区别别和和联联系系生产产调度度的的动态态性性原材材料料供供应应延延误误；产品品交货货期期变变化化；能源源供应应不不足足；设备备出现现异异常常；市场场需求求波波动动；产品品运输输因因素素；；economicdecisionenterprisemanagementproductionschedulingprocessoptimizationprocesscontrol 过程控制、过程优化、生产调度、企业管理和经济决策五层结构的综合自动化系统

(TheodoreJ.Williams,1989) 企业资源计划（ERP）/制造执行系统（MES）/过程控制系统（PCS）三层结构的自动化系统

(柴天佑,2003)ERP(EnterpriseResourcePlanning)PCS(ProcessControlSystem)MES(ManufacturingExecutionSystem)生产产调调度度系系统统的的功功能能生产产计划划的的分分解解：：将将生生产产计计划划合合理理分分解解，，并并编编制制成成便便于于执执行行的的短短期期计计划划。。静态态计计划划分分解解；；在在正正常常的的生生产产条条件件下下（（生生产产设设备备状状态态正正常常，，生生产产要要素素供供应应正正常常、、产产品品储储存存物物流流销销售售正正常常）），，可可以以根根据据选选定定的的目目标标函函数数进进行行分分解解；；动态态计计划划分分解解：：又又称称滚滚动动计计划划。。指指在在生生产产要要素素存存在在扰扰动动的的情情况况下下，，遵遵循循月月生生产产计计划划，，在在生生产产信信息息在在线线反反馈馈的的基基础础上上，，以以生生产产装装置置出出力力最最大大、、以以销销定定产产、、稳稳定定满满负负荷荷生生产产等等为为分分解解原原则则，，将将计计划划分分解解成成2日或或5日不不等等的的滚滚动动作作业业计计划划。实时时监监督督：：通通过过数数据据采采集集系系统统（（SCADA）、、DSC系统统，，将将生生产产流流程程中中各各个个控控制制变变量量、、操操作作变变量量的的实实时时测测量量值值，，生生产产设设备备的的状状态态等等信信息息收收集集并并存存储储。。以以供供调调度度人人员员实实时时查查看看和和调调度度系系统统动动态态调调度度使使用用。。生产产调调度度系系统统的的功功能能平衡衡协协调调：：平平衡衡协协调调好好各各项项生生产产经经营营活活动动，，保保障障生生产产过过程程的的连连续续平平稳稳和和经经济济性性，，有有效效地地实实现现企企业业的的目目标标。。外部部协协调调：：重重点点协协调调产产、、供供、、销销、、运运的的活活动动，，保保障障产产供供销销三三者者的的平平衡衡。。内部部协协调调：：生生产产过过程程内内部部协协调调配配合合，，以以保保证证各各个个生生产产阶阶段段、、各各个个装装置置之之间间的的物物料料平平衡衡，，使使物物料料流流在在流流动动过过程程中中相相互互衔衔接接。。同同时时，，维维持持公公用用工工程程中中水水电电汽汽风风的的供供需需平平衡衡。动态态调调度度：：在在生生产产发发生生为为预预期期事事件件，，使使实实际际进进度度和和调调度度进进度度表表不不符符时时，，对对原原调调度度进进行行修修改改、、调调整整，，以以维维持持生生产产性性能能最最优优的的任任务务。统计计报报表表生产产调调度度系系统统的的功功能能平衡衡协协调调：：平平衡衡协协调调好好各各项项生生产产经经营营活活动动，，保保障障生生产产过过程程的的连连续续平平稳稳和和经经济济性性，，有有效效地地实实现现企企业业的的目目标标。。外部部协协调调：：重重点点协协调调产产、、供供、、销销、、运运的的活活动动，，保保障障产产供供销销三三者者的的平平衡衡。。内部部协协调调：：生生产产过过程程内内部部协协调调配配合合，，以以保保证证各各个个生生产产阶阶段段、、各各个个装装置置之之间间的的物物料料平平衡衡，，使使物物料料流流在在流流动动过过程程中中相相互互衔衔接接。。同同时时，，维维持持公公用用工工程程中中水水电电汽汽风风的的供供需需平平衡衡。动态态调调度度：：在在生生产产发发生生为为预预期期事事件件，，使使实实际际进进度度和和调调度度进进度度表表不不符符时时，，对对原原调调度度进进行行修修改改、、调调整整，，以以维维持持生生产产性性能能最最优优的的任任务务。统计计报报表表生产产调调度度系系统统的的功功能能流水水车车间间调调度度问问题题（（Flow-ShopschedulingproblemFSP）一般般可可以以描描述述为为：：N个工工件件在在m台机机器器上上加加工工；；一个个工工件件分分为为k道工工序序，，每每道道工工序序要要求求不不同同的的机机器器加加工工。。N个工工件件在在m台机机器器上上价价格格顺顺序序相相同同，，工工件件i在机机器器j上的的加加工工时时间间是是给给定定的的，，设设为为Tij。调度度问问题题的的目目标标函函数数是是求求N个工工件件的的最最优优加加工工顺顺序序，，使使加加工工时时间间最最小小。简言之，，不同的的产品在在多台设设备上加加工流程程固定。。生产调度度系统的的功能作业车间间调度问问题（Job-shopSchedulingProblemJSP）一般可以描述述为：给定一个个工件的的集合和和一个机机器的集集合；一每个工件件包括多多道工序序，每道道工序需需要在一一台给定定的机器器上非间间断的加加工一段段时间；；每台机器器一次最最多只能能加工一一道工序序；调度就是是把工序序分配给给机器上上某个时时间段。目标函数数是找到最最优的调调度，使使加工时时间最小小。流水车间间调度问问题的简化模型建立调度模型型流水车车间调度度问题一一般可以以如下描描述:n个工件要要在m台机器上上加工；每个工件件需要经经过m道工序，，每道道工序要要求不同同的机器来完成；n个工件在在m台机器上上加工的的顺序相相同；工件i在机器m上的加工工时间是是给定的的，设为为tij(i=1,2……n，j=1,2……m)；问题的目目标是确确定n个工件在在每台机机器上的