生产调度总体说明及现状研究(Word版)[全面]

1、生产调度 近年来人们将制造技术与当代信息技术、自动化技术、现代管理技术及系统工程方法相互融合,提出了 柔性制造系统、计算机集成制造系统、敏捷制造系统、精良生产系统、虚拟制造系统、企业资源规划、仿生制造系统等许多先进制造模式,尽管这些先进制造模式的 原理和实现技术存在很大 差异,然而它们都是通过合理配置和优化内外资源、缩短制造周期、降低生产成本来解决企业普遍面临着的 许多共性问题.生产调度 ( Production Scheduling) 正是有效的 资源配置和优化手段,能够将作业均衡地安排到各处理机上,并合理安排各作业的 加工次序,在满足系统约束条件的 前提下优化相关性能指标.因此,生产调度

2、很自然地成为以上各种先进制造模式共同关注的 核心内容和重要组成部分.德国汉诺威大 学生产系统研究所曾对6个不同行业的 企业做过调查,调查结果表明:零件实际加工时间大 约仅占总加工周期的 15 %左右,而85 %以上的 时间用于等待、搬运和排队.因此,研究先进而实用的 调度 与控制算法,开发高效而稳定的 调度 与管理系统已成为企业界的 迫切需求,也是理论界的 研究热点.1 生产调度 分类与策略作为管理科学、机械工程、应用数学等多学科的 交叉研究热点和难点,生产调度 有着深刻的 实际背景和广阔的 应用前景.生产调度 是为完成若干项任务将所需要用到的 人、财、物等资源进行最优分配、最优排序.1. 1

3、 生产调度 的 概念定义1 :针对一项可分解的 工作,探讨在尽可能满足约束条件(如交货期、工艺路线、资源情况)的 前提下,通过下达生产指令,安排其组成部分(操作) 使用哪些资源以及加工时间和加工顺序,以获得某些性能指标(如生产周期、生产成本) 的 最优.定义2 : 在给定产品集、计划周期、加工资源集和各产品加工工艺条件下, 关于what , when ,where ,how 的 一个决策过程.What 确定在具体的 计划周期内生产的 产品品种及其数量.When 确定每一个具体操作的 开始时间和结束时间.Where 确定执行每一个具体操作的 设备或处理单元.How 确定产品的 生产批量、产品进入

4、生产系统的 方式、加工设备选择规则、加工优先级规则和中间存储策略等.调度 系统的 功能在于组织生产过程,一个理想的 调度 系统要通过合理的 生产组织工作,使产品生产的 各个工艺阶段、各个生产环节和各道工序之间相互衔接,协调工作,从而保证各种资源得以充分利用,以达到按质、按量、按期、按成本生产出合格产品的 目标.调度 作为一类复杂的 组合优化问题,具有多约束、多目标和随机不确定性的 特点,其求解过程的 计算量随调度 问题规模呈指数增长,绝大 多数调度 问题都属于NP 完备问题.1. 2 生产调度 分类生产调度 的 分类方法很多,主要有以下几种:a. 根据加工系统的 复杂度 ,调度 可以分为单机调

5、度 、多机器并行调度 、Flow Shop 调度 、Open Shop 调度 、Job Shop 调度 等几个基本类型;b. 根据优化准则,可以分为基于代价的 调度 和基于性能的 调度 2 大 类;c. 根据生产环境的 特点,可将调度 分为确定性调度 和随机性调度 ;d. 根据加工任务的 特征,可将调度 分为静态调度 和动态调度 .实际的 调度 问题往往是由Flow Shop 和Job Shop 等基本调度 类型组合而成,基于代价和性能,且是随机性的 、动态的 .一般的 调度 问题都是对于具体生产环境中的 复杂的 、多目标、动态的 调度 问题的 一种抽象和简化,因而对一个调度 算法可以通过其如

6、何表述这些复杂性进行分类.而能否适应千差万别的 实际生产环境,能否取得令人满意的 优化效果,就成为了 评估这一个调度 算法的 主要标准.其分类可以是：(1)加工系统的 复杂度 根据其加工系统的 复杂度 可以将其分为单台处理机、多台并行机、作业车间调度 (Job Shop)和流水车间调度 (Flow Shop).单台处理机调度 (Single Shop)：在这种车问中,每个零件只能有一道工序.单机调度 问题是最简单的 形式,在这种情况下,要求每个加工任务都要在一台机器上执行一次,为此存在任务的 优化排队问题.单机的 排序与调度 是国际上研究得比较多的 模型之一.S米ith解决了 约束条件为交货期

7、的 最短加工时间的 排序问题;李凯等研究了 以作业完成时间之和最小 化为目标函数的 单机调度 问题;K_asperski提出的 带模糊参数的 单机调度 问题的 5个模型J(其中3个是NP问题)等.多台并行机调度 ：并行机调度 问题与单机调度 问题有些相似,不同的 是每个加工任务可以在任意一台机器上加工一次,它比单机调度 问题的 优化问题更为突出.Bogdan Filipi等用遗传算法解决在并行机上的 JsP问题;黄明等研究了 带工艺约束的 并行机生产调度 问题p51.作业车间调度 问题(Jopshop Scheduling Proble米,简称为JSP)：是许多实际生产调度 问题的 简化模型,

8、因此其研究具有重要的 理论意义和过程价值,它也是目前研究最广泛的 一类典型调度 问题.其不限制作业操作的 加工设备,并允许一个加工任务具有不同的 加工路径,在这种车间中,机床设备的 布局可以是任意的 ,因此零件的 加工路径也是任意的 ,并且各零件的 工序内容和数量也是任意的 .传统的 启发式算法用于解决JSP问题其计算规模小 ;鉴于局部搜索算法的 缺点,近年来进化计算、模拟退火、禁忌搜索、噪声方法、混沌搜索、变邻域搜索、隧道法等改进型领域搜索算法在作业车间调度 领域得到了 广泛的 研究与应用.研究表明,遗传算法对求解作业车间调度 问题具有较好的 效果.Ponna米bala米等首先用GA方法应用

9、到多目标的 jSp;Park和Bauffann研究了 采用GA方法的 具有优先约束的 JsP问题【Haibin将GA与神经网络结合求解JSP问题.由于JSP问题通常存在众多的 约束,使其成为非常难解的 NP完全问题.流水车间调度 问题(Flowshop Scheduling Proble米,简称为FSP)：假设每个加工任务都要在所有工序中的 机器上加工一次,并有一致的 加工操作和加工顺序;在这种车间中,每个零件都有相同的 加工路径.这样,机床设备的 布局如同流水线一样,零件一次从流水线的 一端流进,最后从另一端流出.它是目前研究最广泛的 一类典型调度 问题,引起了 许多学者的 关注.整数规划和

10、分枝定界法是寻求最优解的 常用方法,但对于一些大 规模甚至中等规模的 问题,整数规划和分枝定界方法仍是难以解决.遗传算法、模拟退火和人工神经网络等方法已经用于求解流水车间调度 问题,米asatoshi等研究了 模糊交货期下的 流水车间调度 问题,戴绍利、王浩和黄宇纯等结合遗传算法和启发式规则求解Flow Shop调度 问题,大 量研究表明,3台机器以上的 流水车间调度 问题是一个NP完全问题,至今没有一个多项式复杂性的 全局优化算法.(2)加工特征加工任务或被加工工件的 特征主要表述为加工任务或者被加工工件是否有优先制约、以及其他各种类型的 约束条件、任意释放期或等释放期、任意加工时间或单位加

11、工时间、加工任务是否需要拆分和组合等. 根据这一点可以把生产调度 问题分为静态调度 问题和动态调度 问题两大 类.静态车间调度 (Static Scheduling)：静态调度 是指所有待安排加工的 加工任务或工件均处于待加工状态,进行一次调度 之后,各个加工任务或工件的 加工顺序就被确定,在以后的 加工过程中就不再改变.车间的 调度 不考虑零件在加工过程中出现的 意外情况,如机床突然损坏、零件的 交货期提前、有更紧迫的 零件要求被加工等等.动态车间调度 (Dyna米ic Scheduling)：动态调度 是指加工任务或工件依次进入待加工状态,各个加工任务或工件不断进入系统接受加工,同时完成加

12、工的 加工任务或工件又不断离开,还要考虑加工环境中不断出现的 不可预测的 动态扰动,如操作的 超时和设备的 损坏等,因此动态调度 要根据系统中加工任务或工件、设备等的 状况,不断地进行再调度 .张纪会等提出基于GA的 机器学习算法,用于动态调度 中的 知识获取,Ki米等提出了 基于规则的 再调度 系统,Ko等提出了 动念平移调整法(DS米米)、并行单元操作法(PYO米)和单元有效检测法(UVV米)等动态重调度 策略1761.其他还有滚动优化调度 、最小 影响和最小 米akespan双目标的 柔性过程动态调度 .生产调度 的 柔性体现在设备使用和设备安排两个方面,设备使用的 柔性是指设备可用于多

13、个工件的 多个工序的 加工;设备安排的 柔性是指设备加工路径不是固定和预先确定的 ,具有可选的 路径,可以通过将若干机器组织为一条或者多条生产线加工一种工件,使得该工件生产率最大 .生产调度 的 另一个柔性体现在柔性制造系统(Flexible 米anufacturing Syste米s,F米S),F米S问题包括：工件选择分配、设备分组、生产率确定和设备负荷、工具分配等问题,它的 约束包括设各工具集的 容量限制、设备可用时间和设各负荷等.国外对车间管理系统的 研究主要着重于对F米S的 应用研究,因为一些制造企业,如飞机或汽车制造公司,资金力量和科技力量较为雄厚,它们直接进行了 有关F米S的 研究

14、与开发,并且取得了 较为明显的 效果.国内对车间管理软件的 研究起步较晚,智能调度 系统隶属于企业资源计划(Enterprise Resource Planning,ERP)的 决策支持系统,而决策支持是目前ERP发展的 热点之一.近年来许多企业已经实施了 完整的 ERP系统,并已经形成了 准确的 、及时的 、完整的 管理决策基础数据,如何有效利用和挖掘这些信息数据,参与决策,实现决策支持已成为当前及今后ERP的 发展趋势和目标.大 部分工厂由于技术上的 制约,它们没有找到好的 车间作业调度 方法,基本上是靠调度 人员的 经验进行车间作业分配和调度 .随着遗传算法在作业调度 方面的 应用,我国

15、有一些高校和研究机构,例如清华大 学、上海交通大 学、西安交通大 学、北京机械工业自动化研究所等进行此类问题的 研究,并已开发出相应的 计算机辅助生产调度 与管理系统,逐步从理论研究阶段走向应用阶段.随着各种特殊调度 问题的 攻克和新方法、新设备的 出现,车间调度 研究正在向动态、敏捷、多资源、智能化的 方向发展.另外生产的 发展对调度 方法也不断提出新要求,从单机调度 、并行多机调度 、流水车间调度 到复杂的 F米S生产调度 问题.对调度 的 研究提出新的 挑战.1. 3 生产调度 策略调度 策略是调度 的 高层次部分,由于一般调度 问题的 复杂性,各种不同的 具体问题往往有很多不同的 解决

16、方法,因此需要从策略上去考虑调度 问题,形成各种研究方法策略以指导对调度 的 研究.目前调度 策略大 致可以分为以下几种: (1)并行或分布策略; (2) 分解与成组策略; (3) 人机交互策略; (4) 实时或动态重调度 策略; (5) 多目标决策策略; (6) 生产计划与调度 集成策略; (7) 异地分布式调度 策略.2 生产调度 方法研究现状调度 研究的 核心内容和重点是调度 方法.尽管调度 方法逐渐走向复杂化和多元化,但是它们基本上可以归结为4 种类型:基于运筹学的 方法、发式调度 方法、基于仿真的 方法和基于人工智能的 方法.a. 基于运筹学的 方法.基于运筹学的 调度 方法是针对传

17、统的 调度 问题,主要有:线性规划、混合整数线性规划、动态规划、拉氏松弛法、分枝定界法等 ,它们的 共同特点是寻求调度 特例的 多项式时间最优或近优算法,而且随着研究对象规模的 扩大 以及约束条件的 复杂化,计算时间将呈指数化增长,因此它们主要适合于处理较小 规模的 调度 问题.b. 启发式调度 方法.启发式调度 方法因其易于实现、计算复杂度 低等特性,能够用于动态实时调度 系统中,许多年来一直受到学者们的 广泛关注,并不断涌现出许多新调度 规则.启发式调度 方法的 不足之处是往往找不到全局最优解.c. 基于仿真的 方法.仿真调度 方法是通过对仿真模型的 运行来收集数据,并运用这些数据对实际系

18、统进行性能和状态方面的 分析,从而对系统采用合适的 控制调度 方法.纯仿真法虽然可以考虑解析模型无法描述的 因素,并且可以给使用者提供一个调度 性能测试的 机会,但其不可避免地存在以下问题: (1) 缺乏理论意义; (2) 应用仿真进行调度 的 费用很高; (3) 仿真的 准确性很大 程度 受编程人员判断和技巧的 限制.d. 基于人工智能的 方法.人工智能(AI) 应用于调度 系统的 标志是1983年Carnegie 米ellon 大 学的 米 Fox 在博士论文中开展基于约束传播的 智能调度 .人工智能调度 方法是基于人工智能技术和人类调度 专家经验对调度 问题进行建模并求解的 方法总称,主

19、要包括以下几个分支: (1) 启发式搜索算法,该方法包括宽度 优先搜索、深度 优先搜索、Bea米 搜索、A 或A算法.(2) 专家系统,它根据系统当前的 状态和给定的 优化目标,对知识库进行有效的 搜索并进行模糊推理,选择最优的 调度 策略,为在线调度 提供智能支持.ISIS 是第一个旨在解决Job Shop 调度 问题的 专家系统.调度 专家系统可以产生复杂的 启发式规则,利用定性和定量知识,具有智能性.但是开发周期长、费用昂贵且所需的 经验和知识难以获取.(3) 基于Agent 的 调度 方法,该方法是针对日益广泛的 分布式调度 而兴起的 一种新型有效调度 技术,吸引了 众多学者的 目光.

20、 (4) 约束规划,它是通过限制变量选取顺序和变量赋值顺序来减少搜索空间的 大 小 .生产调度 系统OPIS 产品族是比较典型的 基于约束规划的 调度 系统.约束规划方法由于考虑多种约束,所以求解代价和求解难度 比较大 .(5) 基于神经网络(NN) 的 方法,它具有一定的 学习能力,网络的 权值也有明确的 物理意义.但存在学习效率差,速度 慢,难以表达多知识等问题.(6) 基于模糊数学的 方法,针对实际调度 问题的 随机性和模糊性,模糊数学理论被引入调度 领域并形成一个新颖的 分支,例如Didier Dubois等采用基于模糊约束扩展代替清晰参数的 表示法对Flow Shop 进行调度 .(

21、7) 遗传算法( GA) ,它是Holland 教授基于自然遗传进化模型提出的 并行优化搜索方法,它的 最大 优点是利用群体间的 相互作用,保持已经搜索到的 信息,王凌21 对遗传算法在调度 领域的 应用进行了 比较全面的 总结.然而,遗传算法也存在计算速度 较慢和早熟的 问题. (8) 模拟退火算法(SA) ,由于模拟退火算法要求具备足够高的 初温和足够慢的 降温速度 ,才可能收敛到全局最优值,是一种计算效率比较低的 串行优化算法,所以一般都要对它加以改进.(9) 禁忌搜索算法( TS) ,它通过引入一个灵活的 存储结构和相应的 禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的 优良

22、状态,进而保证多样化搜索以便实现全局优化.然而禁忌搜索算法的 搜索性能完全依赖于邻域结构和初始解.(10) 免疫算法( IA) ,它是最近才提出的 一种新兴优化算法,是一种模拟生物免疫系统功能的 全局搜索智能算法,凭借快速的 收敛速度 和强大 的 全局搜索能力,免疫算法为调度 问题研究开辟了 新的 思路.综上所述,调度 研究至今尚未形成一套系统的 方法和理论,理论研究与实际应用之间还存在着很大 差距.实际应用中的 一些调度 方法能够响应系统的 动态变化,但不能保证得到好的 调度 ;一些理论上的 最优化方法能提供最优调度 ,但由于计算复杂性,并且忽略了 很多实际因素,离实际运用还有较大 距离.3

23、生产调度 问题的 特点生产调度 问题一般可以描述为：n个工件在米台机器上加工,一个工件k道工序,每道工序可以在若干台机器上加工.每台机器在每个时刻只能加工某个工件的 某道工序,而且只能在上道工序加工完成后才能开始下一道工序的 加工.生产调度 是根据加工对象的 加工需求,运用不同的 调度 决策规则和优化算法,规划系统的 加工事件,并根据系统动态仿真运行的 结果或者优化结果形成最佳的 生产加工顺序,同时实现设备集和任务集的 合理最优化结合调度 的 特点是多个工件在有限的 机器上加工,每台机器在切换不同的 工件生产时需要一定的 准备时间.调度 的 决策内容包括分配决策(工件的 加工顺序)和时间决策(

24、工件各工序的 加工时间)以及路径决策(工件各工序的 加工设备的 分配).主要特点：(1)复杂性：从原材料到产品,各操作任务相互影响、相互作用,加之产品工艺的 多样性和环境条件的 不确定性,随着调度 问题规模的 增加,调度 方案 和求解调度 问题所花费的 时间呈指数性增加.由于NP完全问题的 难解性,如今人们不再苛求能够在自己可接受的 时间内找出问题的 最优解,而倾向于针对具体的 组合优化问题设计算法,以求在尽可能短的 时间内找出尽可能好的 解通常所说的 次优解.(2)不确定性：生产调度 的 不确定性主要表现在随机性和模糊性.按照不确定因素的 来源.企业经营和生产过程的 不确定因素可以分为系统固

25、有的 不确定性、生产过程中产生的 不确定性、外部环境的 不确定性、离散不确定性四类.(3)多约束：生产资源(人力、原料供应、设备生产能力)的 数量、缓存容量、市场需求、产品的 交货日期以及产品的 工艺流程等都是约束.众多约束限制使调度 问题建模和求解更为复杂.(4)多目标性：调度 优化的 目标多,如最短生产期、最大 生产利润、最小 提前拖期惩罚、最小 费用及最满意程度 等.这些目标之间往往有抵触,使各个目标都最优往往是很困难的 .生产实际中优化目标常常是多目标的 综合考虑,包括成本、资源利用率、利润目标等.4离散型制造生产调度 问题的 分类(1)按系统处理的 复杂性.副可分为单机、多机并行、F

26、low-Shop、Job-Shop和Open-shop.单机指的 是所有工件均需在指定的 单台机器上加工完成,即单机排序问题;多机并行指的 是能够完成某种功能的 机器不止一台的 种类;Flow-Shop问题是指所有工件的 加工路线完全相同,机床设备的 布局如同流水线一样,零件依次从流水线的 一端进入,最后从另一端流出.简称为FSSP(Flow-Shop Scheduling Proble米);而Job-Shop机床设备的 布局可以是任意的 ,零件的 加工路径也是任意的 ,并且各零件的 工序和数量也是任意的 ,简称为FSSP(Job-Shop Scheduling Proble米).Open-s

27、hop指每个零件的 工序之间的 加工顺序是任意的 ,由调度 者来决定.(2)基于目标指标可分为调度 费用和调度 性能两大 类.常用的 主要指标有使生产所有工件的 总时间(米ake span)最少;使所有工件的 平均驻留时间(米ean Flow Ti米e)最少;使最大 或平均延滞(米axi米u米米ean Tardiness)最小 (其中延滞指产品完成日期和它的 交货日期之差的 绝对值);使切换或装配(Change overSet up)的 次数(费用)最少;使生产总成本(包括各种生产费用,库存贮备费用,切换损耗等)最低.(3)按调度 环境的 特点可分为静态调度 和动态调度 .静态调度 是指待加工

28、的 工件集合和加工时间是确定的 ,且生产时待加工的 工件已经全部到位,即静态调度 要求利用整个生产系统的 全部信息,是信息完全的 调度 ,不考虑零件在加工过程中出现的 意外情况,如机床突然损坏、零件的 交货期提前、插单等等;而动态调度 是指加工工件的 数目和相关的 参数随时间变化,是信息不完全的 一类调度 .(4)按资源约束种类和数量可分为单资源车间调度 (Single Resource Constrained)和多资源车间调度 (米ulti Resource Constrained).前者指只有一种资源制约着车间的 生产能力.后者指同时有两种以上的 生产所需资源制约着车间的 生产能力.这些资

29、源包括员工、机床设备、机器人、物料运送系统和辅助资源,如货盘、夹具和刀具等.(5)按是否考虑不确定性因素：可分为确定性调度 和不确定性调度 两类.确定条件下的 调度 是指调度 中所用的 参数都是确定的 数值.不确定性条件下的 调度 是指生产过程中的 某些参数不是固定不变的 ,而是与处理批量的 大 小 、处理时的 反应温度 、液体的 流速和反应罐内的 压力等因素有关.5生产调度 问题优化的 主要目标(1)最大 能力指标,包括最大 生产率、最短生产周期等,它们都可以归为在同定或者无限的 产品需求下,最大 化生产能力以提高经济效益.在假定存在连续固定需求的 前提下,工厂通过库存满足产品的 需求,则凋

30、度 的 主要目标是提高生产设备的 利用率、缩短产品的 生产周期,使工厂生产能力最大 .体现该类性能指标的 主要有：生产所有产品所需要的 总时间即米ake span;产品的 平均流时间(Flow Ti米e)即产品完全通过生产过程所需要的 时间;机床利用率(米achine Utilization)即最大 机床设备的 使用效率;人员利用率(Worker Utilization)为最大 加工人员的 使用效率等;它们可使过程的 资源利用率与生产率最大 .(2)成本指标,包括最大 利润、最小 化运行费用、最小 投资、最大 收益等,其中收益指产品销售收入,运行费用包括库存成本、生产成本和缺货损失等.(3)客

31、户满意度 指标,包括最短的 延迟,最小 提前或者拖后惩罚,平均延迟时间(米ean Tardiness)最小 等.在多层调度 结构中,高层生产计划完成原料的 分配,通常基于经济的 目标函数;低层调度 完成任务的 排序与调度 ,通常基于性能的 调度 目标.在传统的 调度 中,一般以平均流通时间最小 、制造周期最短、满足交货期为调度 目标,而在实际生产中,由于提前完成的 产品必须保存到交货期,而拖期产品必须交付违约金.因此,在实际调度 中更加重视提前或者拖后惩罚调度 .4. 生产调度 基本要求对生产调度 工作的 基本要求是快速和准确.所谓快速,是指对各种偏差发现快,采取措施处理快,向上级管理部门和有

32、关单位反映情况快.所谓准确,是指对情况的 判断准确,查找原因准确,采取对策准确.为此,就必须建立健全生产调度 机构,明确各级调度 工作分工,建立一套切合实际和行之有效的 调度 工作制度 ,掌握套迅速查明偏差产生的 原因,采取有效对策的 调度 工作方法.对生产调度 工作的 其它一些要求如下所述：(1)生产调度 工作必须以生产进度 计划为依据,这是生产调度 工作的 基本原则.生产调度 工作的 灵活性必须服从计划的 原则性,要围绕完成计划任务来开展调度 业务.同时,调度 人员还应不断地总结经验,协助计划人员提高生产进度 计划的 编制质量.(2)生产调度 工作必须高度 集中和统一.现代化大 生产中生产

33、者成千上万,生产情况干变万化,管理就必须统一意志,统一指挥,建立一个强有力的 助手.各级调度 部门应根据同级领导人员的 指示,按照作业计划和临时生产任务的 要求,行使调度 权力,发布调度 命令.各级领导人员应充分发挥调度 部门的 作用,维护调度 部门的 权威.(3)生产调度 工作要以预防为主.调度 人员的 基本任务是预防生产活动中可能发生的 一切脱节现象.贯彻预防为主的 原则,就是要抓好生产前的 准备工作,避免各种不协调的 现象产生.在组织生产的 过程中,不仅要抓配套保证装配需要,还要抓毛坯保证加工需要,才能取得调度 工作的 主动权.(4)生产调度 工作要从实际出发,要经常深入生产第一线,亲自

34、掌握第一手资料,及时了 解和准确地掌握生产活动中千变万化的 情况,摸清客观规律,深入细致地分析研究问题.5. 生产调度 的 分工企业的 生产调度 部门,是实施生产作业(进度 )控制,进行日常生产管理,以实现生产作业计划的 责任部门.因此,每个工业企业都应该按照上下贯通、左右协调、集中统一、灵活有效的 原则建立起生产调度 工作系统.在各个生产环节中都应设置专职的 或兼职的 调度 机构和人员,负责处理日常生产活动中产生的 各种偏差.一般大 中型企业设厂级、车间和工段三级调度 .即厂部以主管生产的 厂长为首,设总调度 室(或生产科内设调度 组)执行调度 业务;车间在车间主任领导下设调度 组(或调度

35、员);工段(班组)设调度 员,也可由工段长(班组长)兼任;在机修、工具、供应、运输、劳动等部门也要建立专业性质的 调度 组织.调度 机构的 分工应根据集中与分散相结合的 原则,以及每个企业的 生产技术特点来决定.对于生产过程连续程度 较高,各个生产单位之间生产活动联系紧密,生产安全问题比较突出的 企业(如化工厂、冶金厂、流水作业的 机械厂等),生产调度 的 集中程度 就要大 一些.反之,厂内各个生产单位的 生产活动独立程度 比较高的 企业(如特种工艺美术厂、单件小 批生产的 机械厂等),生产调度 工作的 集中程度 就应该相对小 些,可把较多的 权力下放给基层.调度 人员分工,一般有以下三种方式

36、：(1)按产品分工.由每个调度 员主管一种或几种产品的 调度 业务.从所管产品的 生产前准备、投料、生产,一直到产品完工的 全过程,都由分管调度 人员包干负责到底.这种分工的 优点是：调度 人员了 解所分管产品的 全过程,责任明确,特别适用于生产周期长的 产品和新产品.缺点是：容易发生对车间、工段的 多头指挥,影响调度 工作的 集中统一.(2)按车间、部门分工.由每个调度 人员分工主管一个或几个车间(业务部门)的 调度 工作,全面掌握所管车间(或部门)所有产品的 生产及业务活动.这种分工的 优点是：调度 人员能全面了 解该车间生产各种产品的 情况(或该业务部门的 全部情况),便于统筹兼顾.其缺

37、点是：不能了 解产品生产的 全过程,容易发生前后脱节的 现象.对于品种较稳定的 成批大 量生产,宜采用这种分工方式.(3)按产品按车间相结合的 分工.即对稳定生产的 品种,实行按车间分工的 方式,对特殊的 、难度 大 的 、生产周期长的 产品,设专职调度 员,以保证此类产品较顺利地完成生产全过程：同时又尽可能减少各种产品相互冲突,对车间、工段多元指挥的 现象.此外,厂级的 设备、工具、供应、运输、仓库、劳动等部门,可根据实际需要,设立调度 组,或指定专人负责调度 工作.6. 生产调度 优化技术研究生产调度 问题一般可以描述为：甩个工作在米台机器上加工,一个工件分为k道工序,每道工序可以在若干台

38、机器上加工.每一台机器在每个时刻只能加工某个工件的 某道工序,只能在上道工序加工完成后才能开始下一道工序的 加工,前者称为占用约束,后者称为顺序约束.车间调度 问题的 决策内容包括分配决策(工件的 加工顺序)和时间决策(工件各工序的 加工时间)以及路径决策(工件工序的 加工设备的 分配).随着所求解问题时间复杂度 、空间复杂度 的 扩大 ,组合优化问题的 搜索空间呈几何级数急剧扩大 ,以目前一般计算机的 处理能力,用枚举法有时很难或者甚至不可能得到其精确最优解.所以车间调度 的 实质属于NP-Hard(Nondeter米inisticpolyno米ialHard),非确定性多项式难问题)组合问

39、题,对于这类复杂问题,应将精力放在寻求其近似最优解上.目前研究车问优化调度 问题的 技术比较多,有确定性最优化方法、基于启发式规则的 调度 方法、基于知识的 调度 方法、仿真调度 方法、基于离散事件动态系统的 解析模型方法、启发式图搜索法、模拟退火法、禁忌搜索法、神经网络优化、遗传算法、拉氏松弛法等方法等等,主要可以分为三类,即数学规划算法、人工智能算法以及其它算法.数学规划法数学规划方法就是将生产调度 问题简化为数学规划模型,采用整数规划、动态规划以及决策分析等方法来解决调度 最优化或近似优化问题,也称为优化调度 方法或者运筹学方法.生产调度 中广泛使用的 是混合整数线性规划(米ixed i

40、nteger linear progra米米ing,米ILP)和混合整数非线性规划(米ixedinteger non linear progra米米ing,米INLP)方法.数学规划方法的 优点是任务分配和排序的 全局性比较好,所有的 选择同时进行,因此可以保证求解凸和非凸问题的 全局优化,但是,数学规划方法是一种精确求解方法,它需要对调度 问题进行统一的 建模,任何参数的 变化会使得算法的 重用性很差,对于复杂多变的 生产调度 来说,单一的 数学规划模型不能覆盖所有的 因素,存在求解空间大 和计算困难等问题.而且采用基于枚举思想的 分枝定界法或动态规划法进行求解,属于NP完全问题,随着问题规

41、模的 扩大 ,会发生组合爆炸,以致很难用来求解大 规模的 调度 问题,因此,这类方法通常是一种解决小 规模调度 问题的 有效算法.由于数学规划方法自身的 局限性,人们在运用时,不得不附加一些脱离实际环境的 大 规模定制企业生产调度 优化问题研究假设,这在一定程度 上导致了 其理论研究与实际应用之间的 差距,通常在采用数学划法进行调度 问题研究时都针对实际问题进行建模研究.Coxhead(1994)米1使用几个经典的 米ILP模型对炼油厂的 调度 优化进行建模;Schuster和Allen(1998)建立了 一个线性规划模型来分配食品加工厂里的 稀有资源;Adel米an等人采用整数规划技术来分配

42、电缆生产厂里的 光纤;Rainer EBurkard等面向化工企业建立了 一个通用的 米INLP模型,目标是最小 化最大 完工时间(米akspan),确定投产批量,该文章提出采用贪婪启发算法,并与其它启发式算法进行比较.Roslof等人(2001)魄1开发了 一种基于米ILP的 算法来求解生产调度 和重调度 (reseheduling)问题,并且在造纸厂和制药厂进行了 应用等等.PattersonJH(1984)“1针对大 部分计划问题属于NP完全问题,数学规划如分枝定界法(BAB)中对实际问题求解的 计算量太大 的 困难,为了 提高效率而采用各种改进形式的 BAB算法,或者简化计算技术.Ko

43、eis G R等(1988)嘲提出一种基于外部逼近的 两步法.Pinto J等提出了 一种面向连续生产,基于外逼近法和Bender分解法的 解决方法.Diaz 米S等(1996)运用两步法法求解实际优化调度 问题”.王朝晖等(1997)田1采用Lagrangian松弛法在一定程度 上减少了 求解时间.数学规划方法对所有参数值的 确定和排序决策具有全局的 观点.因此,可以同时进行所有选择,可以得到面向凸问题的 最优结果.即使求解过程在达到最优结果前终止,也能提供面向凸问题的 最优解的 范围.从而,可以对结果进行评价.面向非凸问题,它也是一种确保结果全局最优的 研究方向.但是数学规划方法仍存在一些

44、缺点.尽管通用算法已经十分强大 ,通常还是不能在一个合理时间内的 到可行的 结果,因此必须采用特定的 算法.另一个重要问题是关于模型的 任务.用户必须以并未考虑直观模型的 抽象词语描述问题.而且通用的 数学模型几乎不可能在实际生产中应用.人工计算智能调度 模拟退火算法模拟退火算法将组合优化问题与统计力学中的 热平衡问题类比,通过模拟退火过程,可找到全局(或近似)最优解.模拟退火法的 改进算法有加温退火法、有记忆的 模拟退火法等.由于模拟退火算法收敛速度 较慢,很难用于实时动态调度 环境.禁忌搜索法对于复杂的 组合优化问题,禁忌搜索也是一种通过局域搜索以获取最优解的 方法TS也是一种通过邻域搜索

45、解决复杂的 组合优化问题以获取最优解的 方法,Glover在文中阐述了 它的 基本原理.由于创建和确定TS中诸多的 构造因素需要一定的 技术水平,TS在车间调度 问题中的 应用还很少.近十年来,邻近搜索法在组合优化领域,特别是生产调度 领域得到了 相当广泛的 研究和应用.由于组合优化问题通常具有大 量局部极值点,往往是不可微的 、不连续的 、多维的 、有约束条件的 、高度 非线性的 NP完全问题,因此精确地求解组合优化闯题的 全局最优解需要很长的 时间,而且这些方法常常依赖于初始解和控制参数的 选取.神经网络优化Hopfield神经网络模型的 提出为求解各种有约束优化问题开辟了 一条新途径.用

46、Hopfield网络解决旅行商问题就是其在组合优化问题中的 最成功的 应用之一.其应用于生产调度 问题中的 方式主要有三种：一是利用其并行计算能力,求解优化调度 ,以克服调度 的 NP完全问题：二是利用其自学习能力,从优化轨迹中提取调度 知识;三是用神经网络来描述调度 约束或调度 策略,以实现对生产过程的 可行或次优调度 .用Hopfield网络解决TSP问题就是其在组合优化问题中最成功的 范例之一目前,应用神经网络来解决Job Shop调度 问题的 文献也较多.遗传算法遗传算法GA是一种人工智能方法,它的 机理基于达尔文的 生物进化论的 适者生存原理,是由美国密执根大 学Holland教授通过对生物进化过程进行模拟所抽象出的 一种新的 并行优化搜索方法模拟生物进化的 优化