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

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

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

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

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

5、化准则,可以分为基于代价的调度和基于性能的调度2 大类;c. 根据生产环境的特点,可将调度分为确定性调度和随机性调度;d. 根据加工任务的特征,可将调度分为静态调度和动态调度。实际的调度问题往往是由Flow Shop 和Job Shop 等基本调度类型组合而成,基于代价和性能,且是随机性的、动态的。一般的调度问题都是对于具体生产环境中的复杂的、多目标、动态的调度问题的一种抽象和简化，因而对一个调度算法可以通过其如何表述这些复杂性进行分类。而能否适应千差万别的实际生产环境，能否取得令人满意的优化效果，就成为了评估这一个调度算法的主要标准。其分类可以是：(1)加工系统的复杂度根据其加工系统的复杂度

6、可以将其分为单台处理机、多台并行机、作业车间调度(Job Shop)和流水车间调度(Flow Shop)。单台处理机调度(Single Shop)：在这种车问中，每个零件只能有一道工序。单机调度问题是最简单的形式，在这种情况下，要求每个加工任务都要在一台机器上执行一次，为此存在任务的优化排队问题。单机的排序与调度是国际上研究得比较多的模型之一。Smith解决了约束条件为交货期的最短加工时间的排序问题；李凯等研究了以作业完成时间之和最小化为目标函数的单机调度问题；K_asperski提出的带模糊参数的单机调度问题的5个模型J(其中3个是NP问题)等。多台并行机调度：并行机调度问题与单机调度问题有

7、些相似，不同的是每个加工任务可以在任意一台机器上加工一次，它比单机调度问题的优化问题更为突出。Bogdan Filipi等用遗传算法解决在并行机上的JsP问题；黄明等研究了带工艺约束的并行机生产调度问题p51。作业车间调度问题(Jopshop Scheduling Problem，简称为JSP)：是许多实际生产调度问题的简化模型，因此其研究具有重要的理论意义和过程价值，它也是目前研究最广泛的一类典型调度问题。其不限制作业操作的加工设备，并允许一个加工任务具有不同的加工路径，在这种车间中，机床设备的布局可以是任意的，因此零件的加工路径也是任意的，并且各零件的工序内容和数量也是任意的。传统的启发式

8、算法用于解决JSP问题其计算规模小；鉴于局部搜索算法的缺点，近年来进化计算、模拟退火、禁忌搜索、噪声方法、混沌搜索、变邻域搜索、隧道法等改进型领域搜索算法在作业车间调度领域得到了广泛的研究与应用。研究表明，遗传算法对求解作业车间调度问题具有较好的效果。Ponnambalam等首先用GA方法应用到多目标的jSp；Park和Bauffann研究了采用GA方法的具有优先约束的JsP问题【Haibin将GA与神经网络结合求解JSP问题。由于JSP问题通常存在众多的约束，使其成为非常难解的NP完全问题。流水车间调度问题(Flowshop Scheduling Problem，简称为FSP)：假设每个加工

9、任务都要在所有工序中的机器上加工一次，并有一致的加工操作和加工顺序；在这种车间中，每个零件都有相同的加工路径。这样，机床设备的布局如同流水线一样，零件一次从流水线的一端流进，最后从另一端流出。它是目前研究最广泛的一类典型调度问题，引起了许多学者的关注。整数规划和分枝定界法是寻求最优解的常用方法，但对于一些大规模甚至中等规模的问题，整数规划和分枝定界方法仍是难以解决。遗传算法、模拟退火和人工神经网络等方法已经用于求解流水车间调度问题，Masatoshi等研究了模糊交货期下的流水车间调度问题，戴绍利、王浩和黄宇纯等结合遗传算法和启发式规则求解Flow Shop调度问题，大量研究表明，3台机器以上的

10、流水车间调度问题是一个NP完全问题，至今没有一个多项式复杂性的全局优化算法。(2)加工特征加工任务或被加工工件的特征主要表述为加工任务或者被加工工件是否有优先制约、以及其他各种类型的约束条件、任意释放期或等释放期、任意加工时间或单位加工时间、加工任务是否需要拆分和组合等。 根据这一点可以把生产调度问题分为静态调度问题和动态调度问题两大类。静态车间调度(Static Scheduling)：静态调度是指所有待安排加工的加工任务或工件均处于待加工状态，进行一次调度之后，各个加工任务或工件的加工顺序就被确定，在以后的加工过程中就不再改变。车间的调度不考虑零件在加工过程中出现的意外情况，如机床突然损坏

11、、零件的交货期提前、有更紧迫的零件要求被加工等等。动态车间调度(Dynamic Scheduling)：动态调度是指加工任务或工件依次进入待加工状态，各个加工任务或工件不断进入系统接受加工，同时完成加工的加工任务或工件又不断离开，还要考虑加工环境中不断出现的不可预测的动态扰动，如操作的超时和设备的损坏等，因此动态调度要根据系统中加工任务或工件、设备等的状况，不断地进行再调度。张纪会等提出基于GA的机器学习算法，用于动态调度中的知识获取，Kim等提出了基于规则的再调度系统，Ko等提出了动念平移调整法(DSMM)、并行单元操作法(PYOM)和单元有效检测法(UVVM)等动态重调度策略1761。其他

12、还有滚动优化调度、最小影响和最小Makespan双目标的柔性过程动态调度。生产调度的柔性体现在设备使用和设备安排两个方面，设备使用的柔性是指设备可用于多个工件的多个工序的加工；设备安排的柔性是指设备加工路径不是固定和预先确定的，具有可选的路径，可以通过将若干机器组织为一条或者多条生产线加工一种工件，使得该工件生产率最大。生产调度的另一个柔性体现在柔性制造系统(Flexible Manufacturing Systems，FMS)，FMS问题包括：工件选择分配、设备分组、生产率确定和设备负荷、工具分配等问题，它的约束包括设各工具集的容量限制、设备可用时间和设各负荷等。国外对车间管理系统的研究主要

13、着重于对FMS的应用研究，因为一些制造企业，如飞机或汽车制造公司，资金力量和科技力量较为雄厚，它们直接进行了有关FMS的研究与开发，并且取得了较为明显的效果。国内对车间管理软件的研究起步较晚，智能调度系统隶属于企业资源计划(Enterprise Resource Planning，ERP)的决策支持系统，而决策支持是目前ERP发展的热点之一。近年来许多企业已经实施了完整的ERP系统，并已经形成了准确的、及时的、完整的管理决策基础数据，如何有效利用和挖掘这些信息数据，参与决策，实现决策支持已成为当前及今后ERP的发展趋势和目标。大部分工厂由于技术上的制约，它们没有找到好的车间作业调度方法，基本上

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

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

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

17、纯仿真法虽然可以考虑解析模型无法描述的因素,并且可以给使用者提供一个调度性能测试的机会,但其不可避免地存在以下问题: (1) 缺乏理论意义; (2) 应用仿真进行调度的费用很高; (3) 仿真的准确性很大程度受编程人员判断和技巧的限制。d. 基于人工智能的方法。人工智能(AI) 应用于调度系统的标志是1983年Carnegie Mellon 大学的M Fox 在博士论文中开展基于约束传播的智能调度。人工智能调度方法是基于人工智能技术和人类调度专家经验对调度问题进行建模并求解的方法总称,主要包括以下几个分支: (1) 启发式搜索算法,该方法包括宽度优先搜索、深度优先搜索、Beam 搜索、A 或A

18、算法。(2) 专家系统,它根据系统当前的状态和给定的优化目标,对知识库进行有效的搜索并进行模糊推理,选择最优的调度策略,为在线调度提供智能支持。ISIS 是第一个旨在解决Job Shop 调度问题的专家系统。调度专家系统可以产生复杂的启发式规则,利用定性和定量知识,具有智能性。但是开发周期长、费用昂贵且所需的经验和知识难以获取。(3) 基于Agent 的调度方法,该方法是针对日益广泛的分布式调度而兴起的一种新型有效调度技术,吸引了众多学者的目光。 (4) 约束规划,它是通过限制变量选取顺序和变量赋值顺序来减少搜索空间的大小。生产调度系统OPIS 产品族是比较典型的基于约束规划的调度系统。约束规

19、划方法由于考虑多种约束,所以求解代价和求解难度比较大。(5) 基于神经网络(NN) 的方法,它具有一定的学习能力,网络的权值也有明确的物理意义。但存在学习效率差,速度慢,难以表达多知识等问题。(6) 基于模糊数学的方法,针对实际调度问题的随机性和模糊性,模糊数学理论被引入调度领域并形成一个新颖的分支,例如Didier Dubois等采用基于模糊约束扩展代替清晰参数的表示法对Flow Shop 进行调度。(7) 遗传算法( GA) ,它是Holland 教授基于自然遗传进化模型提出的并行优化搜索方法,它的最大优点是利用群体间的相互作用,保持已经搜索到的信息,王凌21 对遗传算法在调度领域的应用进

20、行了比较全面的总结。然而,遗传算法也存在计算速度较慢和早熟的问题。 (8) 模拟退火算法(SA) ,由于模拟退火算法要求具备足够高的初温和足够慢的降温速度,才可能收敛到全局最优值,是一种计算效率比较低的串行优化算法,所以一般都要对它加以改进。(9) 禁忌搜索算法( TS) ,它通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化搜索以便实现全局优化。然而禁忌搜索算法的搜索性能完全依赖于邻域结构和初始解。(10) 免疫算法( IA) ,它是最近才提出的一种新兴优化算法,是一种模拟生物免疫系统功能的全局搜索智能算法,凭借快速的收敛速度和

21、强大的全局搜索能力,免疫算法为调度问题研究开辟了新的思路。综上所述,调度研究至今尚未形成一套系统的方法和理论,理论研究与实际应用之间还存在着很大差距。实际应用中的一些调度方法能够响应系统的动态变化,但不能保证得到好的调度;一些理论上的最优化方法能提供最优调度,但由于计算复杂性,并且忽略了很多实际因素,离实际运用还有较大距离。3生产调度问题的特点生产调度问题一般可以描述为：n个工件在m台机器上加工，一个工件k道工序，每道工序可以在若干台机器上加工。每台机器在每个时刻只能加工某个工件的某道工序，而且只能在上道工序加工完成后才能开始下一道工序的加工。生产调度是根据加工对象的加工需求，运用不同的调度决

22、策规则和优化算法，规划系统的加工事件，并根据系统动态仿真运行的结果或者优化结果形成最佳的生产加工顺序，同时实现设备集和任务集的合理最优化结合调度的特点是多个工件在有限的机器上加工，每台机器在切换不同的工件生产时需要一定的准备时间。调度的决策内容包括分配决策(工件的加工顺序)和时间决策(工件各工序的加工时间)以及路径决策(工件各工序的加工设备的分配)。主要特点：（1）复杂性：从原材料到产品，各操作任务相互影响、相互作用，加之产品工艺的多样性和环境条件的不确定性，随着调度问题规模的增加，调度方案和求解调度问题所花费的时间呈指数性增加。由于NP完全问题的难解性，如今人们不再苛求能够在自己可接受的时间

23、内找出问题的最优解，而倾向于针对具体的组合优化问题设计算法，以求在尽可能短的时间内找出尽可能好的解通常所说的次优解。（2）不确定性：生产调度的不确定性主要表现在随机性和模糊性。按照不确定因素的来源。企业经营和生产过程的不确定因素可以分为系统固有的不确定性、生产过程中产生的不确定性、外部环境的不确定性、离散不确定性四类。（3）多约束：生产资源（人力、原料供应、设备生产能力）的数量、缓存容量、市场需求、产品的交货日期以及产品的工艺流程等都是约束。众多约束限制使调度问题建模和求解更为复杂。（4）多目标性：调度优化的目标多，如最短生产期、最大生产利润、最小提前拖期惩罚、最小费用及最满意程度等。这些目标

24、之间往往有抵触，使各个目标都最优往往是很困难的。生产实际中优化目标常常是多目标的综合考虑，包括成本、资源利用率、利润目标等。4离散型制造生产调度问题的分类（1）按系统处理的复杂性。副可分为单机、多机并行、Flow-Shop、Job-Shop和Open-shop。单机指的是所有工件均需在指定的单台机器上加工完成，即单机排序问题；多机并行指的是能够完成某种功能的机器不止一台的种类；Flow-Shop问题是指所有工件的加工路线完全相同，机床设备的布局如同流水线一样，零件依次从流水线的一端进入，最后从另一端流出。简称为FSSP（Flow-Shop Scheduling Problem）；而Job-Sh

25、op机床设备的布局可以是任意的，零件的加工路径也是任意的，并且各零件的工序和数量也是任意的，简称为FSSP（Job-Shop Scheduling Problem）。Open-shop指每个零件的工序之间的加工顺序是任意的，由调度者来决定。（2）基于目标指标可分为调度费用和调度性能两大类。常用的主要指标有使生产所有工件的总时间（make span）最少；使所有工件的平均驻留时间（Mean Flow Time）最少；使最大或平均延滞（Maximummean Tardiness）最小（其中延滞指产品完成日期和它的交货日期之差的绝对值）；使切换或装配（Change overSet up）的次数（费用

26、）最少；使生产总成本（包括各种生产费用，库存贮备费用，切换损耗等）最低。（3）按调度环境的特点可分为静态调度和动态调度。静态调度是指待加工的工件集合和加工时间是确定的，且生产时待加工的工件已经全部到位，即静态调度要求利用整个生产系统的全部信息，是信息完全的调度，不考虑零件在加工过程中出现的意外情况，如机床突然损坏、零件的交货期提前、插单等等；而动态调度是指加工工件的数目和相关的参数随时间变化，是信息不完全的一类调度。（4）按资源约束种类和数量可分为单资源车间调度（Single Resource Constrained）和多资源车间调度（Multi Resource Constrained）。前

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

28、定需求的前提下，工厂通过库存满足产品的需求，则凋度的主要目标是提高生产设备的利用率、缩短产品的生产周期，使工厂生产能力最大。体现该类性能指标的主要有：生产所有产品所需要的总时间即make span；产品的平均流时间（Flow Time）即产品完全通过生产过程所需要的时间；机床利用率（Machine Utilization）即最大机床设备的使用效率；人员利用率（Worker Utilization）为最大加工人员的使用效率等；它们可使过程的资源利用率与生产率最大。（2）成本指标，包括最大利润、最小化运行费用、最小投资、最大收益等，其中收益指产品销售收入，运行费用包括库存成本、生产成本和缺货损失等

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

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

31、级调度部门应根据同级领导人员的指示，按照作业计划和临时生产任务的要求，行使调度权力，发布调度命令。各级领导人员应充分发挥调度部门的作用，维护调度部门的权威。(3)生产调度工作要以预防为主。调度人员的基本任务是预防生产活动中可能发生的一切脱节现象。贯彻预防为主的原则，就是要抓好生产前的准备工作，避免各种不协调的现象产生。在组织生产的过程中，不仅要抓配套保证装配需要，还要抓毛坯保证加工需要，才能取得调度工作的主动权。(4)生产调度工作要从实际出发，要经常深入生产第一线，亲自掌握第一手资料，及时了解和准确地掌握生产活动中千变万化的情况，摸清客观规律，深入细致地分析研究问题。5. 生产调度的分工企业的

32、生产调度部门，是实施生产作业(进度)控制，进行日常生产管理，以实现生产作业计划的责任部门。因此，每个工业企业都应该按照上下贯通、左右协调、集中统一、灵活有效的原则建立起生产调度工作系统。在各个生产环节中都应设置专职的或兼职的调度机构和人员，负责处理日常生产活动中产生的各种偏差。一般大中型企业设厂级、车间和工段三级调度。即厂部以主管生产的厂长为首，设总调度室(或生产科内设调度组)执行调度业务；车间在车间主任领导下设调度组(或调度员)；工段(班组)设调度员，也可由工段长(班组长)兼任；在机修、工具、供应、运输、劳动等部门也要建立专业性质的调度组织。调度机构的分工应根据集中与分散相结合的原则，以及每

33、个企业的生产技术特点来决定。对于生产过程连续程度较高，各个生产单位之间生产活动联系紧密，生产安全问题比较突出的企业(如化工厂、冶金厂、流水作业的机械厂等)，生产调度的集中程度就要大一些。反之，厂内各个生产单位的生产活动独立程度比较高的企业(如特种工艺美术厂、单件小批生产的机械厂等)，生产调度工作的集中程度就应该相对小些，可把较多的权力下放给基层。调度人员分工，一般有以下三种方式：(1)按产品分工。由每个调度员主管一种或几种产品的调度业务。从所管产品的生产前准备、投料、生产，一直到产品完工的全过程，都由分管调度人员包干负责到底。这种分工的优点是：调度人员了解所分管产品的全过程，责任明确，特别适用

34、于生产周期长的产品和新产品。缺点是：容易发生对车间、工段的多头指挥，影响调度工作的集中统一。(2)按车间、部门分工。由每个调度人员分工主管一个或几个车间(业务部门)的调度工作，全面掌握所管车间(或部门)所有产品的生产及业务活动。这种分工的优点是：调度人员能全面了解该车间生产各种产品的情况(或该业务部门的全部情况)，便于统筹兼顾。其缺点是：不能了解产品生产的全过程，容易发生前后脱节的现象。对于品种较稳定的成批大量生产，宜采用这种分工方式。(3)按产品按车间相结合的分工。即对稳定生产的品种，实行按车间分工的方式，对特殊的、难度大的、生产周期长的产品，设专职调度员，以保证此类产品较顺利地完成生产全过

35、程：同时又尽可能减少各种产品相互冲突，对车间、工段多元指挥的现象。此外，厂级的设备、工具、供应、运输、仓库、劳动等部门，可根据实际需要，设立调度组，或指定专人负责调度工作。6. 生产调度优化技术研究生产调度问题一般可以描述为：甩个工作在m台机器上加工，一个工件分为k道工序，每道工序可以在若干台机器上加工。每一台机器在每个时刻只能加工某个工件的某道工序，只能在上道工序加工完成后才能开始下一道工序的加工，前者称为占用约束，后者称为顺序约束。车间调度问题的决策内容包括分配决策(工件的加工顺序)和时间决策(工件各工序的加工时间)以及路径决策(工件工序的加工设备的分配)。随着所求解问题时间复杂度、空间复

36、杂度的扩大，组合优化问题的搜索空间呈几何级数急剧扩大，以目前一般计算机的处理能力，用枚举法有时很难或者甚至不可能得到其精确最优解。所以车间调度的实质属于NP-Hard(NondeterministicpolynomialHard)，非确定性多项式难问题)组合问题，对于这类复杂问题，应将精力放在寻求其近似最优解上。目前研究车问优化调度问题的技术比较多，有确定性最优化方法、基于启发式规则的调度方法、基于知识的调度方法、仿真调度方法、基于离散事件动态系统的解析模型方法、启发式图搜索法、模拟退火法、禁忌搜索法、神经网络优化、遗传算法、拉氏松弛法等方法等等，主要可以分为三类，即数学规划算法、人工智能算法

37、以及其它算法。数学规划法数学规划方法就是将生产调度问题简化为数学规划模型，采用整数规划、动态规划以及决策分析等方法来解决调度最优化或近似优化问题，也称为优化调度方法或者运筹学方法。生产调度中广泛使用的是混合整数线性规划(mixed integer linear programming，MILP)和混合整数非线性规划(mixedinteger non linear programming，MINLP)方法。数学规划方法的优点是任务分配和排序的全局性比较好，所有的选择同时进行，因此可以保证求解凸和非凸问题的全局优化，但是，数学规划方法是一种精确求解方法，它需要对调度问题进行统一的建模，任何参数的变

38、化会使得算法的重用性很差，对于复杂多变的生产调度来说，单一的数学规划模型不能覆盖所有的因素，存在求解空间大和计算困难等问题。而且采用基于枚举思想的分枝定界法或动态规划法进行求解，属于NP完全问题，随着问题规模的扩大，会发生组合爆炸，以致很难用来求解大规模的调度问题，因此，这类方法通常是一种解决小规模调度问题的有效算法。由于数学规划方法自身的局限性，人们在运用时，不得不附加一些脱离实际环境的大规模定制企业生产调度优化问题研究假设，这在一定程度上导致了其理论研究与实际应用之间的差距，通常在采用数学划法进行调度问题研究时都针对实际问题进行建模研究。Coxhead(1994)m1使用几个经典的MILP

39、模型对炼油厂的调度优化进行建模；Schuster和Allen(1998)建立了一个线性规划模型来分配食品加工厂里的稀有资源；Adelman等人采用整数规划技术来分配电缆生产厂里的光纤；Rainer EBurkard等面向化工企业建立了一个通用的MINLP模型，目标是最小化最大完工时间(makspan)，确定投产批量，该文章提出采用贪婪启发算法，并与其它启发式算法进行比较。Roslof等人(2001)魄1开发了一种基于MILP的算法来求解生产调度和重调度(reseheduling)问题，并且在造纸厂和制药厂进行了应用等等。PattersonJH(1984)“1针对大部分计划问题属于NP完全问题，

40、数学规划如分枝定界法(BAB)中对实际问题求解的计算量太大的困难，为了提高效率而采用各种改进形式的BAB算法，或者简化计算技术。Koeis G R等(1988)嘲提出一种基于外部逼近的两步法。Pinto J等提出了一种面向连续生产，基于外逼近法和Bender分解法的解决方法。Diaz MS等(1996)运用两步法法求解实际优化调度问题”。王朝晖等(1997)田1采用Lagrangian松弛法在一定程度上减少了求解时间。数学规划方法对所有参数值的确定和排序决策具有全局的观点。因此，可以同时进行所有选择，可以得到面向凸问题的最优结果。即使求解过程在达到最优结果前终止，也能提供面向凸问题的最优解的范

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

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

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