优化调度.docx

1．概述?1.1 调度问题的提出敏捷制造作为21世纪企业的先进制造模式，综合了JIT、并行工程、精良制造等多种先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品，即是完全面向顾客的。在这种模式下如何进行组织管理，包括如何组织动态联盟、如何重构车间和单元、如何安排生产计划、如何进行调度都是我们面临的问题。其中车间作业调度与控制技术是实现生产高效率、高柔性和高可靠性的关键，有效实用的调度方法和优化技术的研究与应用已成为先进制造技术实践的基础。调度问题主要集中在车间的计划与调度方面，许多学者作了大量研究，出了不少的研究成果。制造系统的生产调度是针对一项可分解的工作（如产品制造），探讨在在尽可能满足约束条件（如交货期、工艺路线、资源情况）的前提下，通过下达生产指令，安排其组成部分（操作）使用哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优化。在理论研究中，生产调度问题常被称为排序问题或资源分配问题。1.2 调度问题的分类生产调度系统的分类方法很多，主要有以下几种：(1) 根据加工系统的复杂度，可分为单机、多台并行机、flow shop和 job shop。单机调度问题是所有的操作任务都在单台机器上完成，为此存在任务的优化排队问题，对于单机调度比较有代表性的请见文[9][10][l1]；多台并行机的调度问题更复杂，因而优化问题更突出，文[8][11]][13]研究了多台并行机的调度；flow shop型问题假设所有作业都在同样的设备上加工，并有一致的加工操作和加工顺序，文[12][13][14]研究了flow shop问题；job shop是最一般的调度类型、并不限制作业的操作的加工设备，并允许一个作业加工具有不同的加工路径。对于job shop型问题的研究，文献很多，综述文章可参见 Lawler等[15]。(2) 根据性能指标，分为基于调度费用和调度性能的指标两大类。(3) 根据生产环境的特点，可将调度问题分为确定性调度和随机性调度问题。(4) 根据作业的加工特点，可将调度问题分为静态调度和动态调度。静态调度是指所有待安排加工的工作均处于待加工状态，因而进行—次调度后、各作业的加工被确定、在以后的加工过程中就不再改变；动态调度是指作业依次进入待加工状态、各种作业不断进入系统接受加工、同时完成加工的作业又不断离开，还要考虑作业环境中不断出现的动态扰动、如作业的加工超时、设备的损坏等。因此动态调度要根据系统中作业、设备等的状况，不断地进行调度。实际调度的类型往往是 job shop型，且是动态的。1.3 生产调度的环境特征一般的调度问题都是对于具体生产环境中复杂的、动态的、多目标的调度问题的一种抽象和简化，因而，一个调度算法可以通过其如何表述这些复杂性来进行分类。由于实际生产环境是千差万别的，那末，一个调度算法就应该根据其是否能适合对应的生产环境的重要特征来进行评估。Frederick等人为了帮助区别不同的生产调度策略，给出了典型生产调度环境的五个特征，这将有助于我们了解各种不同的调度算法的应用环境。　边界条件：生产调度常常是一个重调度问题，即修改已有的生产调度去适应新的作业。为提供重调度，调度算法应能处理生产系统中有关的初始状态。类似的生产调度通常是在一个有限的时间区域里进行的，系统的最优解（或次优解）亦是在限定的边界范围内来获取。?分批大小和调整费用：为有效地解决实际生产中的调度问题，往往将任务分成多批进行，并考虑改变已有调度结果所付出的代价（调整费用）。加工路径：在实际生产中，作业的加工路径可能需要动态改变，工艺顺序可能是半有序的(semiorder)。随机事件和扰动：比如，出现关键作业、设备损坏、加工操作失败、原料短缺、加工时间/到达时间/交货期的改变等。性能指标和多目标：追求不同的性能指标往往会得到不同的优化解，同时，系统目标也以多目标为主。?　1.4 调度问题的特点实际的调度问题有以下特点：(1) 复杂性由于装卸作业、装卸设备、库场、搬运系统之间相互影响、相互作用、每个作业又要考虑它的到达时间、装卸时间、准备时间、操作顺序、交货期等，因而相当复杂。由于调度问题是在等式或不等式约束下求性能指标的优化，在计算量上往往是NP完全问题，即随着问题规模的增大，对于求解最优化的计算量呈指数增长，使得一些常规的最优化方法往往无能为力，对于这一点 Garey等[16]给出了明确的证明。即便对单机调度问题，如果考虑 n个作业而每个作业只考虑加工时间及与序列有关的准备时间时，就等价于n个城市的 TSP问题。对于一般的装卸系统，问题就变得更为复杂。(2) 动态随机性在实际的生产调度系统中存在很多随机的和不确定的因素，比如作业到达时间的不确定性、作业的加工时间也有一定的随机性，而且生产系统中常出现一些实发偶然事件，如设备