生产调度及优化方法

生产调度方法综述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个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。流水车间调度问题的简化模型启发式方法简介定义：一个基于直观或者经验构造的算法；在可接受的花费下，给出组合优化问题的一个可行解；该可行解和最优解的偏差是无法预计的求解快速，可以得到优化的可行解经典Johnson算法CDS算法：NEH算法结合启发式算法的改进遗传算法使用启发式算法改进遗传算法第N代的种群质量：使用启发算法，产生一个基本的优化排序规律，检查第N代种群中是染色体是否都满足该规律，如果不满足则按照规律改造染色体。参见：黄宇纯王树青，《Flow-shop调度问题的遗传启发算法》，信息与控制，1996.8使用启发算法对第N代种群中的最优值进行邻域搜索，提高算法的邻域搜索能力；参见：盛立纲,顾幸生，《混合遗传NEH算法在流水车间调度中的应用》结合启发式算法的改进遗传算法使用启发算法生产初始种群：将初始种群分成若干个子种群，一部分使用随机方式生成初始种群，另一部使用启发算法，生产次优解的初始种群。启发式方法的快速性保证了这种初始化的速度。参见：王凌,郑大钟，《求解同顺序加工调度问题的一种改进遗传算法》谢谢!Welcomeyourcomments!