生产调度及优化方法

1、生产调度方法综述2011.6.8提纲生产调度的定义调度理论的起源和烁 生产计划与生产调度系统 生产调度系统的功能生产调度问题特点： 两类车间调度类型 流水车间调度问题的简化模型 启发式方法简介结合启发式算法的改进遗传算法生产调度的定义产生背景:随着用户对产品需求的快速变化，以及市场竞争的日趋激烈， 现代制造企业需要进行多品种.小批量生产，这种生产方式 使生产的计划.组织和控制变得更加复杂，另外要求企业对 生产过程中所出现的各种信息进行及时反馈和处理個此，生 产调度问题作为生产管理系统的核心内容和关键问题，其研 究具有重要的理论和实用价值。调度的定义：所谓调度,就是为了实现某一目的而对共同使用的

2、资源进行 时间上的分配。从数学规划的角度来说，生产调度问题可表 述为在等式或不等式约束下，对目标函数所进行的优化。调度理论的起源和发袈从上个世纪50年代起，调度问题的研究就受到应用数学 引 .运筹学.工程技术等领域科学家的重视，科学家们利用 企 运筹学中的线性规划、整数规划、目标规划.动态规划 M 及决策分析方法，研究并解决了一系列有代表意义的调度 帮 和优化问题 爛 20世纪70年代，人们开始注意并重视调度复杂性问题的 研究，提出了用于研究算法有效性和问题难度的计算复杂 度理论，许多调度问题被证明NP完全问题（非多项式确定 问题），计算复杂。 70年代后,经典调度理论得到发展并作为了 一门基

3、本成熟 的应用数学学科。但是实际调度问题与经典调度问题还有 相当的距离。实际调度问题往往都是非常复杂的，没有确定的物理和自然规律可循個此是非常难解的拼且大多是没有精确解的公 。因此，仅仅依靠经典调度理论中基于解析优化的技术和 写 方法，试图解决属于NP完全问题的实际调度问题，不可避 孑 免地会遇到难以逾越的障碍。 爛从20世纪80年代初开始，人们就一直在尝试并致力于解j 决实际调度问题，调度研究由理论研究转向应用研究阶段 班 。在这样的历史背景下，应用人工智能.计算智能和实时J 智能研究成果，解决实际调度问题的智能调度方法就走上A 了历史的舞台。智能调度方法和基于反馈控制的实时调度3 理论和方

4、法为解决实际调度问题展示了光明的前景。< 生产计划与生产调度的区别和联糸生产计划(Production Planning)系统：是以企业生产经营活动为主要依据，根据产品的市场需求.原料供应情况 企业的生产能力、装置的检修情况，综合考虑企业的管 理成本以及生产过程中成品.半成品的成本，利用物料平衡、物料物性数据等进行平衡分析，根据不同的生产状态和计划类型模型，运用优化方法对企业的生产经营进行优化设计，辅助计划人员完年度.季度、月度计划编制，为 企业决策者提供相关预测和决策信息,却把企业利润最大与生产经营活动为中心的因素：原料供应、产能、市场 需求、生产设备状态等；以产销平衡为核心；以利润企

5、业利润最大化和完成中长期目标为最终目标；生产调度(Production Scheduling )系统：在满 足装置设备和工艺要求的条件下，根据市场的需 求，合理的、最佳地安排与组织生产过程，以提 高过程系统的操作最优性，为企业带来现出的经 济效益。内容包括：产品的生产批次数和每批的量；使用的生产线；产品的生产顺序和时间安排；原料供应、水、电、气、汽、冷、人力等资源保障和 限制；生产调度系统的特点:时间：它将长期生产计划分解为短期计划并执行，例如2天、5无这可以大大降低问题的复杂性;任务：生产安排和资源分配涉及到实际生产环境的各种约束;核心：生产装置的分配利用和物料平衡;目标：以最少的消耗保质保

6、量地完成生产计划;生产调度的动态性原材料供应延误; 产品交货期变化;能源供应不足;设备出现异常;市场需求波动; 产品运输因素;enterprise management过程控制、过程优化、生产调度、企业管理和经济决策五层结构的综合自动化系统(Theodore J. Williams,1989)ERP(Enterprise Resource Planning)MES(Manufacturing Execution System)PCS(Process Control System)企业资源计划（ERP） /制造执 行系统（MES） /过程控制系统（ PCS）三层结构的自动化系统（柴天佑,2003

7、）生产调度糸统的功能生产计划的分解：将生产计划合理分解，并编制成便于执 行的短期计划。静态计划分解；在正常的生产条件下(生产设备状态正常，生产要 素供应正常、产品储存物流销售正常)，可以根据选定的目标函 数进行分解；动态计划分解:又称滚动计划。指在生产要素存在扰动的情况下,遵循月生产计划，在生产信息在线反馈的基础上，以生产装置出力最大、以销定产、稳定满负荷生产等为分解原则，将计划分解 成2日或5日不等的滚动作业计划o实时监督：通过数据采集系统(SCADA) . DSC系统， 将生产流程中各个控制变量.操作变量的实时测量值，生 产设备的状态等信息收集并存储。以供调度人员实时查看 和调度系统动态调

8、度使用。平衡协调：平衡协调好各项生产经营活动，保障生产过程 的连续平稳和经济性，有效地实现企业的目标。外部协调：重点协调产、供、销、运的活动，保障产供销三者的平衡。内部协调：生产过程内部协调配合，以保证各个生产阶段、各个装置之间的物料平衡，使物料流在流动过程中相互衔接。同时，维持公用工程中水电汽风的供需平衡O动态调度：在生产发生为预期事件，使实际进度和调度进 度表不符时，对原调度进行修改.调整，以维持生产性能 最优的任务。平衡协调：平衡协调好各项生产经营活动，保障生产过程 的连续平稳和经济性，有效地实现企业的目标。外部协调：重点协调产、供、销、运的活动，保障产供销三者的平衡。内部协调：生产过程

9、内部协调配合，以保证各个生产阶段、各个装置之间的物料平衡，使物料流在流动过程中相互衔接。同时，维持公用工程中水电汽风的供需平衡O动态调度：在生产发生为预期事件，使实际进度和调度进 度表不符时，对原调度进行修改.调整，以维持生产性能 最优的任务。统计报表生产调度糸统的功能> 流水车间调度问题(Flow-Shop scheduling problem FSP)一般可以描述为： N个工件在m台机器上加工； 一个工件分为k道工序，每道工序要求不同的机器加工。 N个工件在m台机器上价格顺序相同，工件i在机器j上的 加工时间是给定的，设为Tij。调度问题的目标函数是求N个工件的最优加工顺序，使加工

10、时间最小。简言之，不同的产品在多台设备上加工流程固定。> 作业车间调度问题(Job-shop Scheduling Problem JSP)一般可以描述为：给定一个工件的集合和一个机器的集合； 一每个工件包括多道工序，每道工序需要在一台给定的机 器上非间断的加工一段时间；每台机器一次最多只能加工一道工序；调度就是把工序分配给机器上某个时间段。目标函数是找到最优的调度，使加工时间最小。流水车间调度问题的简化模型建立调度模型流水车间调度问题一般可以如下描述： n个工件要在m台机器上加工；每个工件需要经过m道工序，每道工序要求不同的机器 来完成；n个工件在m台机器上加工的顺序相同；工件i在机器

11、m上的加工时间是给定的，设为tjj (i = 1,2n, j = 1, 2m);问题的目标是确定n个工件在每台机器上的最优加工顺序， 使最大流程时间达到最小。流水车间调度问题的简化模型""令C(jk)表示工件j：在机器k上的加工完工时间) 表示工件的调度厠么，对于无限中间存储方式个工件山台机器訂 流水车间调度问题的完工时间可表示为：C(ji H)二 ；C (jj j k.) -C (j| (k - 1 .)+ t|k; k=2?m(：(ji 川=C(j_»1.) +Lj| ； i =2( "-if打桃丿=niiix4.C (jj_| tk'1 ；

12、C(j訂k -1J: +肛；i =2i,r订i；It最大流程时崗为= C(jB,m)，调度目标则是确定工件的加工顺 序弓1“2*我得C唤最小。启发式方法简介定义:一个基于直观或者经验构造的算法;在可接受的花费下，给出组合优化问题的一个可 行解；该可行解和最优解的偏差是无法预计的求解快速，可以得到优化的可行解 经典Johnson算法> CDS算法:NEH算法结合启发式算法的改进遗传算法使用启发式算法改进遗传算法第N代的种群质量：使用启 发算法，产生一个基本的优化排序规律，检查第N代种群 中是染色体是否都满足该规律，如果不满足则按照规律改 造染色体。参见：黄宇纯 王树青，Flowshop调度问题的遗传启发算法,信息与控 制，1996.8使用启发算法对第N代种群中的最优值进行邻域搜索，提 高算法的邻域搜索