生产调度
近年来人们将制造技术与当代信息技术、自动化技术、现代管理技术及系统工程方法相互融合,提出了柔性制造系统、计算机集成制造系统、敏捷制造系统、精良生产系统、虚拟制造系统、企业资源规划、仿生制造系统等许多先进制造模式,尽管这些先进制造模式的原理和实现技术存在很大差异,然而它们都是通过合理配置和优化内外资源、缩短制造周期、降低生产成本来解决企业普遍面临着的许多共性问题。
生产调度( Production Scheduling) 正是有效的资源配置和优化手段,能够将作业均衡地安排到各处理机上,并合理安排各作业的加工次序,在满足系统约束条件的前提下优化相关性能指标。因此,生产调度很自然地成为以上各种先进制造模式共同关注的核心内容和重要组成部分。德国汉诺威大学生产系统研究所曾对6个不同行业的企业做过调查,调查结果表明:零件实际加工时间大约仅占总加工周期的15 %左右,而85 %以上的时间用于等待、搬运和排队。因此,研究先进而实用的调度与控制算法,开发高效而稳定的调度与管理系统已成为企业界的迫切需求,也是理论界的研究热点。
1 　生产调度分类与策略
作为管理科学、机械工程、应用数学等多学科的交叉研究热点和难点,生产调度有着深刻的实际背景和广阔的应用前景。生产调度是为完成若干项任务将所需要用到的人、财、物等资源进行最优分配、最优排序。
1. 1 　生产调度的概念
定义1 :针对一项可分解的工作,探讨在尽可能满足约束条件(如交货期、工艺路线、资源情况)的前提下,通过下达生产指令,安排其组成部分(操作) 使用哪些资源以及加工时间和加工顺序,以获得某些性能指标(如生产周期、生产成本) 的最优。
定义2 : 在给定产品集、计划周期、加工资源集和各产品加工工艺条件下, 关于what , when ,where ,how 的一个决策过程。
What 确定在具体的计划周期内生产的产品品种及其数量。
When 确定每一个具体操作的开始时间和结束时间。
Where 确定执行每一个具体操作的设备或处理单元。
How 确定产品的生产批量、产品进入生产系统的方式、加工设备选择规则、加工优先级规则和中间存储策略等。
调度系统的功能在于组织生产过程,一个理想的调度系统要通过合理的生产组织工作,使产品生产的各个工艺阶段、各个生产环节和各道工序之间相互衔接,协调工作,从而保证各种资源得以充分利用,以达到按质、按量、按期、按成本生产出合格产品的目标。
调度作为一类复杂的组合优化问题,具有多约束、多目标和随机不确定性的特点,其求解过程的计算量随调度问题规模呈指数增长,绝大多数调度问题都属于NP 完备问题。
1. 2 　生产调度分类
生产调度的分类方法很多,主要有以下几种:
a. 根据加工系统的复杂度,调度可以分为单机调度、多机器并行调度、Flow Shop 调度、Open Shop 调度、Job Shop 调度等几个基本类型;
b. 根据优化准则,可以分为基于代价的调度和基于性能的调度2 大类;
c. 根据生产环境的特点,可将调度分为确定性调度和随机性调度;
d. 根据加工任务的特征,可将调度分为静态调度和动态调度。
实际的调度问题往往是由Flow Shop 和Job Shop 等基本调度类型组合而成,基于代价和性能,且是随机性的、动态的。
一般的调度问题都是对于具体生产环境中的复杂的、多目标、动态的调度问题的一种抽象和简化，因而对一个调度算法可以通过其如何表述这些复杂性进行分类。而能否适应千差万别的实际生产环境，能否取得令人满意的优化效果，就成为了评估这一个调度算法的主要标准。
其分类可以是：
(1)加工系统的复杂度
根据其加工系统的复杂度可以将其分为单台处理机、多台并行机、作业车间调度(Job Shop)和流水车间调度(Flow Shop)。
单台处理机调度(Single Shop)：在这种车问中，每个零件只能有一道工序。单机调度问题是最简单的形式，在这种情况下，要求每个加工任务都要在一台机器上执行一次，为此存在任务的优化排队问题。单机的排序与调度是国际上研究得比较多的模型之一。Smith解决了约束条件为交货期的最短加工时间的排序问题；李凯等研究了以作业完成时间之和最小化为目标函数的单机调度问题；K_asperski提出的带模糊参数的单机调度问题的5个模型㈣J(其中3个是NP问题)等。
多台并行机调度：并行机调度问题与单机调度问题有些相似，不同的是每个加工任务可以在任意一台机器上加工一次，它比单机调度问题的优化问题更为突出。Bogdan Filipi等用遗传算法解决在并行机上的JsP问题；黄明等研究了带工艺约束的并行机生产调度问题p51。
作业车间调度问题(Jop．shop Scheduling Problem，简称为JSP)：是许多实际生产调度问题的简化模型，因此其研究具有重要的理论意义和过程价值，它也是目前研究最广泛的一类典型调度问题。其不限制作业操作的加工设备，并允许一个加工任务具有不同的加工路径，在这种车间中，机床设备的布局可以是任意的，因此零件的加工路径也是任意的，并且各零件的工序内容和数量也是任意的。传统的启发式算法用于解决JSP问题其计算规模小；鉴于局部搜索算法的缺点，近年来进化计算、模拟退火、禁忌搜索、噪声方法、混沌搜索、变邻域搜索、隧道法等改进型领域搜索算法在作业车间调度领域得到了广泛的研究与应用。研究表明，遗传算法对求解作业车间调度问题具有较好的效果。Ponnambalam等首先用GA方法应用到多目标的jSp；Park和Bauffann研究了采用GA方法的具有优先约束的JsP问题【．Haibin将GA与神经网络结合求解JSP问题。由于JSP问题通常存在众多的约束，使其成为非常难解的NP完全问题。
流水车间调度问题(Flow．shop Scheduling Problem，简称为FSP)：假设每个加工任务都要在所有工序中的机器上加工一次，并有一致的加工操作和加工顺序；在这种车间中，每个零件都有相同的加工路径。这样，机床设备的布局如同流水线一样，零件一次从流水线的一端流进，最后从另一端流出。它是目前研究最广泛的一类典型调度问题，引起了许多学者的关
注。整数规划和分枝定界法是寻求最优解的常用方法，但对于一些大规模甚至中等规模的问题，整数规划和分枝定界方法仍是难以解决。遗传算法、模拟退火和人工神经网络等方法已经用于求解流水车间调度问题，Masatoshi等研究了模糊交货期下的流水车间调度问题，戴绍利、王浩和黄宇纯等结合遗传算法和启发式规则求解Flow Shop调度问题，大量研究表明，3台机器以上的流水车间调度问题是一个NP完全问题，至今没有一个多项式复杂性的全局优化算法。
(2)加工特征
加工任务或被加工工件的特征主要表述为加工任务或者被加工工件是否有优先制约、以及其他各种类型的约束条件、任意释放期或等释放期、任意加工时间或单位加工时间、加工任务是否需要拆分和组合等。  根据这一点可以把生产调度问题分为静态调度问题和动态调度问题两大类。
静态车间调度(Static Scheduling)：静态调度是指所有待安排加工的加工任务或工件均处于待加工状态，进行一次调度之后，各个加工任务或工件的加工顺序就被确定，在以后的加工过程中就不再改变。车间的调度不考虑零件在加工过程中出现的意外情况，如机床突然损坏、
零件的交货期提前、有更紧迫的零件要求被加工等等。
动态车间调度(Dynamic Scheduling)：动态调度是指加工任务或工件依次进入待加工状态，各个加工任务或工件不断进入系统接受加工，同时完成加工的加工任务或工件又不断离开，还要考虑加工环境中不断出现的不可预测的动态扰动，如操作的超时和设备的损坏等，因此动态调度要根据系统中加工任务或工件、设备等的状况，不断地进行再调度。张纪会等提出基于GA的机器学习算法，用于动态调度中的知识获取，Kim等提出了基于规则的再调度系统，Ko等提出了动念平移调整法(DSMM)、并行单元操作法(PYOM)和单元有效检测法(UVVM)等动态重调度策略1761。其他还有滚动优化调度、最小影响和最小Makespan双目标的柔性过程动态调度。
生产调度的柔性体现在设备使用和设备安排两个方面，设备使用的柔性是指设备可用于多个工件的多个工序的加工；设备安排的柔性是指设备加工路径不是固定和预先确定的，具有可选的路径，可以通过将若干机器组织为一条或者多条生产线加工一种工件，使得该工件生产率最大。生产调度的另一个柔性体现在柔性制造系统(Flexible Manufacturing Systems，FMS)，FMS问题包括：工件选择分配、设备分组、生产率确定和设备负荷、工具分配等问
题，它的约束包括设各工具集的容量限制、设备可用时间和设各负荷等。国外对车间管理系统的研究主要着重于对FMSjsp编译过程的应用研究，因为一些制造企业，如飞机或汽车制造公司，资金力量和科技力量较为雄厚，它们直接进行了有关FMS的研究与开发，并且取得了较为明显的效果。国内对车间管理软件的研究起步较晚，智能调度系统隶属于企业资源计划(Enterprise Resource Planning，ERP)的决策支持系统，而决策支持是目前ERP发展的热点之一。近年来许多企业已经实施了完整的ERP系统，并已经形成了准确的、及时的、完整的管理决策基础数据，如何有效利用和挖掘这些信息数据，参与决策，实现决策支持已成为当前及今后ERP的发展趋势和目标。大部分工厂由于技术上的制约，它们没有到好的车间作业调度方法，基本上是靠调度人员的经验进行车间作业分配和调度。随着遗传算法在作业调度方面的应用，我国有一些高校和研究机构，例如清华大学、上海交通大学、西安交通大学、北京机械工业自动化研究所等进行此类问题的研究，并已开发出相应的计算机辅助生产调度与管理系统，逐步从理论研究阶段走向应用阶段。随着各种特殊调度问题的攻克和新方法、新设备的出现，车间调度研究正在向动态、敏捷、多资源、智能化的方向发展。另外生产的发展对调度方法也不断提出新要求，从单机调度、并行多机调度、流水车间调度到复杂的FMS生产调度问题。对调度的研究提出新的挑战。