（机械电子工程专业论文）塑料制品生产过程的调度研究.pdf

摘要 企业能否把现有资源进行合理配置和充分利用，直接影响到产品的制造成本 和企业效益。企业资源的合理配置和优化利用很大程度上体现在车间一层的生产 活动中，所以加强车间层的生产管理与控制一直在企业生产经营活动中占有十分 重要的地位，而其生产调度是生产管理与控制中的重要部分。作者结合自己在注 塑企业流水线车间生产调度系统开发中的工作，对注塑企业的生产调度作了以下 几个方面的研究： 1 研究了有关生产调度的基本理论，总结了车间生产调度的优化方法和策略； 2 详细的介绍了禁忌搜索算法，包括禁忌搜索算法的基本概念，基本操作，禁 忌搜索算法的处理流程和基本步骤； 3 对现有注塑企业流水线上的生产调度问题进行了分析，研究； 4 对注塑企业流水线上的生产调度建立了数学模型，并对其注塑流水线上的调 度提出了基于禁忌搜索算法的调度算法； 5 通过大量的数据对算法进行了仿真； 关键字：注塑；生产调度；禁忌搜索 变三些奎兰三兰塑圭堡耋 a b s tr a c t t h ec o s ta n dp r o f i to fa r te n t e r p r i s ea r eg r e a t l yd e p e n d e n t ，i ns o m es e n s e ，o nt h e m a n u f a c t u r i n gr e s o u r c ec o n f i g u r a t i o na n du t i l i z a t i o n s h o pf l o o rs c h e d u l i n gi so n eo f t h em a i nf a c t o r st h a ta f f e c tt h er e s o u r c eu t i l i z a t i o n t h i sp a p e ra d d r e s s e st h es c h e d u l i n g p r o b l e mf o ri n j e c t i o nm o d e l i n gp r o c e s s e sa n dc o n d u c t st h ef b l l o 谢n gw o r k ： 1 p r e s e n tar e v i e wo nt h es c h e d u l i n gt h e o r i e sa n da n a l y z et h ee x i s t i n gm e t h o d so f s c h e d u l i n go p t i m i z a t i o n ； 2 i n t r o d u c et a b us e a r c hm e t h o df o rs c h e d u l i n gi nd e t a i l ，i n c l u d i n gi t sb a s i cc o n c e p t a n do p e r a t i o n s ，a n dt h ep r o c e d u r e ； 3 p r e s e n tt h es c h e d u l i n gp r o b l e mf o r 蜘e c t i o nm o l d i n gp r o c e s s e sa n dt h es t a t eo f a r t ； 4 p r e s e n tam o d e lf o rt h es c h e d u l i n gp r o b l e mo f 面e c t i o nm o l d i n gp r o c e s s e sa n da t a b ua l g o r i t h m ； 5 n u m e r i c a ls i m u l i z a t i o ni sd o n ea n di ti ss h o w nt h a tt h ea l g o r i t h mm a k e sag o o d i m p r o v e m e n t k e y l r o r d s ：i n j e c t i o nm o l d i n gp r o c e s s e s ；p r o d u c t i o ns c h e d u l i n g ；t a b us e a r c h 广东工业大学工学硕士论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个入在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含他人已经发表或撰写过的研究成果，不包括 本人或其他用途使用过的成果。与我一起工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 6 0 指导老师签字：f 9 暂7 秽易 论文作者签字：纠总，舭 ， 二零零七年五月二十五日 第一章绪论 1 1 论文研究的背景 第一章绪论 2 1 世纪的企业面临着日益激烈的国际竞争，要想赢得市场、赢得用户就必须 通过实施m r pi i e r p 来加强管理。然而上层生产计划管理受市场影响越来越大， 明显感到计划跟不上变化。面对客户对交货期的苛刻要求，面对更多产品的改型， 订单的不断调整，企业决策者认识到，计划的制订要依赖于市场和实际的作业执 行状态，而不能完全以物料和库存回报来控制生产。同时m r pi i e r p 软件主要是 针对资源计划，这些系统通常能处理昨天以前发生的事情( 作历史分析) ，亦可 预计并处理明天将要发生的事件，但对今天正在发生的事件却往往留下了不规范 的缺口。而传统生产现场管理只是一个黑箱作业，这己无法满足今天复杂多变的 竞争需要。因此如何将黑箱作业透明化，找出任何影响产品品质和成本的问题， 提高计划的实时性和灵活性，同时又能改善生产线的运行效率已成为目前每个企 业十分关心的问题。 制造执行系统( m e s ) “恰好能填补这一空白。m e s 是处于计划层和生产层操作 控制系统s f c 之间的执行层，主要负责生产管理和调度执行。它通过控制包括物料、 设备、人员、流程指令和设施在内的所有工厂资源来提高制造竞争力，提供一种 系统的在统一平台上集成诸如生产调度、质量控制、文档管理等功能的方式，从 而实现企业实时化的e r p 姬s s f c 系统。 由于不同的制造系统千差万别，特点各不相同，几乎没有可能用一种同一的 方法对所有的制造系统实行有效的生产计划和调度。制造系统可以分为三类：离 散、连续( 包括批处理制造过程) 和混合型。机械制造企业是典型的离散制造过程， 而石油化工和钢铁企业则属于连续和批处理过程。注塑加工过程等可认为是一种 混合型制造过程。在这一过程中，塑料通过注塑机成型，再经过喷油、印刷、装 配形成产品。尽管，在注塑过程中，从注塑机出来的产品是以离散的形式输出， 但注塑机的生产过程是连续的，不能间断的，并要求生产要有相当大的批量，具 有连续过程的特征。而喷油、印刷、装配是典型的离散过程。同时，在具有一定 广东工业大学工学硕士论文 规模的注塑企业中一般拥有上百甚至几百台注塑机，而喷油和印刷生产线往往只 有几条。由于每一台注塑机生产不同产品，批量又大，从而造成大量的在制品。 为了保证注塑件不损坏，传统的作法是将注塑件包装，存入仓库，喷油时从仓库 里取出、并拆去包装。完成喷油后再包装和存入仓库，印刷时再取出、再拆包装。 这样，不仅大量的在制品库存增加了制造成本，同时还有大量的包装、拆包装、 入库、出库等无效劳动，不仅造成资源浪费、消耗大量的能源，也延误交货时间。 另外，目前注塑企业基本上是按客户订单生产，一个无效的管理系统造成大量的 库存，却又往往不能按时交货。这些问题典型地属于生产过程管理和控制的问题， 需要通过改进生产计划和调度、生产过程的实施监控来改进。也就是说，需要通 过实施m e s 来实现。而生产计划与调度是m e s 的一个最主要的部分之一。因此，生 产计划与调度算法的研究对于以注塑生产为典型的一类混合制造系统m e s 来说具 有重要意义。为了改变现有的高库存、高浪费的状况，迫切需要有一个好的生产 计划与调度算法的m e s 来实施。 1 2 课题研究的来源 本课题是应某中型注塑企业的要求，为其开发一个m e s 系统。上面已经提到， 注塑加工过程是混合生产过程，公司基本上是面向订单生产的，产品品种变化大， 批量相对小。同时，注塑机台数多，每一注塑机生产不同产品，批量又相对大， 如果没有很好的生产计划和控制，以及实时的监控系统，就只能靠大量的在制品 库存来实现生产平衡。由于是面向订单生产的，按期交货是及其重要的，这对生 产计划和调度提出了更高的要求。另外，在这种混合生产系统中，调度的好坏与 生产顺序相关。此外，在系统中，安排得合理，一个人可以操作多台设备。这就 需要良好的实时监控系统。但是，到目前为止，没有这样有效的生产计划与调度 的算法，也没有对所研究的生产系统实施m e s 的例子。本课题的研究就是要解决该 企业和类似领域存在的问题，填补其空白。 第一章绪论 1 3 课题研究的意义 本课题所研究的混合生产系统在工业生产中广泛地存在。就拿注塑生产来说， 由于现在大多数的产品都在不同的程度上包含了注塑件，因此，注塑加工企业几 乎是比比皆是。) d e s 的实施能给企业带来巨大的经济效益，这已经成为大家的共 识。而m e s 的重点就在生产计划和调度，生产计划与调度算法的好坏决定了这个 制造执行系统的好与坏，因此本课题的研究将会给企业实施m e s 带来很大的帮助。 同时，由于这类企业广泛存在，生产过程基本相似，系统很容易移植，所以所研 发出来的系统本身具有很大的市场潜力，可以带来可观的经济效益。再者，本研 究将填补所研究的混合系统跹s 的空白，为提高广东和珠江三角洲地区制造业的 水平、降低消耗做出贡献。 1 4 国内外研究现状及存在的问题分析 1 4 1 生产计划与调度算法的发展过程及研究现状 在过去的几十年里，基于实际的及理论上的考虑，不断地激励着人们寻找新 的生产调度算法，其中一个重要的原因是产品制造界的市场竞争性在不断提高， 好的生产调度能提高资源的生产率及操作管理的水平，生产出具有竞争性的产 品。生产调度优化工作，因其在提高生产效率、降低生产成本等方面所起的重要 作用，正越来越受到学者们的关注。 基本上生产调度问题。4 1 都是对于具体生产环境中复杂的、动态的、多目标的 调度问题的一种抽象和简化，因而一个调度算法可以通过其如何表述这些复杂性 进行分类。一般调度算法的遇到的调度环境基本上有如下5 个：边界条件、分批大 小和调整费用、加工路径、随机事件和扰动、性能指标和多目标。 在对生产计划与调度问题进行的研究的方法上，最初是集中在整数规划，仿 真和简单的规则上，这些方法不是调度结果不理想就是难以解决复杂的问题。近 年来，随着各种新的相关学科与优化技术的建立与发展，在调度领域也出现了许 多新的优化方法。例如：神经网络方法、模拟退火法、遗传算法、禁忌搜索算法、 基于d e d s 的解析模型方法”1 等等，这些调度方法将会在第二章进行介绍。众多的 广东工业大学工学硕士论文 调度方法使得生产计划与调度问题的研究朝着多元化方向发展。 1 4 2 生产计划与调度存在的问题及解决途径 在生产调度领域中的大部分问题都具有n p 困难特性。虽然对它的研究已有几十 年的历史，但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还 存在着很大差距。实际应用中的调度方法能够响应系统的动态变化，但不能保证 得到好的调度。一些理论上的最优化方法能提供最优调度，但由于其的计算复杂 性，并且忽略了很多实际因素，离实际运用还有较大距离。大多数的研究者都是从 以下几个方面进行深入的研究： 1 ) 寻求新的最优算法。基于最优化的方法，诸如动态规划算法与分析定界算法等 等，大多数是建立在对可能调度的部分枚举上，因此只能解决小规模的生产调度问 题，距离实用还有较大距离。大多生产调度问题属于一类n p 困难组合问题，寻找 具有多项式复杂性的最优算法几乎是不可能：但因其解的最优性，至今仍激励着 学者们进行不断的探索。 2 ) 解决基于统计优化方法的计算时间复杂性问题。各种基于统计优化的方法，诸 如模拟退火法，遗传算法等，提供了一种解决调度优化问题的新途径，但同别的优 化算法类似，也存在着一定程度的枚举。一般来说收敛到最优解很慢，且对于判断 解的最优性也很困难。在这方面也需要做进一步的研究。 3 ) 探索新的近似调度算法，解决次优性的保障及定量评估问题。各种近似启发式 方法，诸如基于规则的算法等，由于能在合理的时间内产生比较满意的调度，因此 广泛应用于实际调度中，但其往往对所得的调度解的次优性不能进行评估。在这 方面有必要探索更好的近似最优调度算法，可以考虑增加合理的计算时间代价， 提高解的次优性。在这方面拉氏松弛方法具有独到的优越性，但其对偶问题求解 收敛速度、可行调度的构造是有待于进一步研究的关键问题。 4 ) 探索生产计划与调度问题的集成求解方法。在实际生产调度中，生产计划与生 产调度往往是分层进行的，但这可能造成计划在实际调度中的不可行问题，如何将 计划与调度结合考虑，以求总体的优化也是需要进一步研究的。 5 ) 另外，还有很多有待进一步研究的问题，比如实际生产调度的多目标性等。对于 上述这些方面的进一步研究。总之，对生产调度领域的研究，必然向着集成化、多 目标化、动态实用化、高度次优化方向发展。 4 第一章绪论 1 5 本文的工作 本文主要是对注塑企业的生产调度进行改进，以解决以往注塑企业调度中所 遇到的一些问题。在注塑企业中，有两个工序上的调度是非常重要的，一个是注 塑生产线上的调度，一个是喷油生产线上的调度。本文主要是以这两个工序上的 调度进行展开的。 本文的各章节的安排如下： 第一章绪论。本章主要介绍论文研究的背景，课题研究的来源，以及课题研究的 意义，国内外研究对生产计划与调度研究的现状等等。 第二章对生产计划与调度进行阐述，包括调度的算法，调度的策略等等。 第三章介绍禁忌搜索算法的概念，原理，算法流程。 第四章分析现在注塑企业调度所遇到的问题，给出改进的调度算法。 第五章对改进的调度算法进行仿真。 广东工业大学工学硕士论文 第二章生产调度理论 2 1 生产调度问题的描述 2 1 1 生产调度问题简述 生产计划与调度问题可以这样定义：对于某个可以分解的产品，在一定的约 束条件下，安排其分解的零件或工序所占用的资源、加工时间及先后顺序，以获 得产品加工时间或加工成本的最优。在生产计划调度中，会遇到很多的约束条件， 一般有以下的一些约束：产品的投产期，交货期，生产能力，加工顺序，加工设 备，加工路径和成本等等。在一些调度中，有些约束条件是必须要满足的，如交 货期，生产能力，加工顺序等；而有一些则需要尽量优化，如生产成本等。 在生产计划与调度中，可以把约束分为两种：一种是确定性，一种是非确定 性的。例如对于前面所讲的交货期，生产能力，加工顺序可以认为是确定性的， 而对于设备故障，原料供应变化一些突发的因素，不可预见的因素则认为是非确 定性的。 在生产计划与调度中，涉及到的资源往往有：原料、加工设备( 加工，运输， 存储) 、人员、资金等，这和产品的工艺有关。 生产计划与调度有一般有以下几个性能指标：加工成本最低、库存费用最少、 生产周期最短、切换时间最少、设备利用率最高、废品最少等等。在实际的生产 计划与调度中可以分为三大类： 1 最大能力指标，包括最大生产率、最短的生产周期等。它们都可以归结为 在固定或者无限的产品需求下，最大化生产能力以提高经济效益。在假定存在连 续固定需求的前提下，工厂通过库存满足产品的需求，因此，调度问题的主要目 标是提高生产设备的利用率、缩短产品的生产周期，使生产能力得到最大发挥。 2 成本指标，包括最大利润、最小的运行费用、最小投资、最大收益等，其 中收益指产品销售收入，运行费用包括库存成本，生产成本和缺货损失。 3 客户满意度指标，包括最短的延迟，最小的提前期或者拖期惩罚等。 6 第二章生产调度理论 在传统的调度中，一般以平均流通时间最小、制造周期最短、满足交货期为 调度目标。而在实际生产中，由于提前完成的产品必须保存到交货期，而提前产 品必须交付违约金，因此，在实际调度中更加重视提前或者拖期惩罚调度。 调度问题也是一个优化问题。优化问题可以自然的分为两类：一类是连续变 量的问题；另一类是离散变量的问题，称为组合优化问题。对于连续变量的优化 问题，一般是求一组实数或者一个函数；而在组合优化问题中，是从一个无限集 或者可数无限集中寻找一个对象，它可以是一个整数、集合、排列或者一个图。 生产过程般按照其输出的产品是呈连续的产品流、离散的批量、离散的数 量三种情况，分为连续生产过程、间隙生产过程和离散生产过程。在离散生产过 程中，原料相同、加工工序相同的一组产品通常是分批制造的，一定数量的产品 作为一个工件组，并且在各个工作台之间传输，而且，每个工件都有独立的个性。 机械加工是典型的离散生产过程。而在连续生产过程中，原料经由不同的专用设 备加工转变为产品。每个设备都是在稳定的工作状态，完成一项规定的生产操作， 个连续生产过程输出的产品是连续的产品流。间隙生产过程又称为批处理 ( b a t c hp r o c e s s ) ，是由一个或者多个按一定顺序执行的操作步组成。这些操作 步是离散的，而每步中的过程是连续的。间隙生产过程一般包括若干个通用设备， 多个产品在有限台设备上生产。 相应的，生产调度问题可以分为面向机加工等离散操作的车间调度问题和面 向流程工业生产过程的间隙生产调度或者成为批处理调度问题。 m a c c a r t h yl e ta 1 ( 1 9 9 3 ) ，陈荣秋( 1 9 8 7 ) 采用a b c d 体制对生产调度问 题进行了分类，其中a 、b 、c 、d 的含义为：a 是工件数量，b 是机器数，c 为工 艺和管理约束决定的加工模式，d 为优化指标。常见的加工模式有 ，单帆 j单件加工( j o bs h o p ) f 流水线加工 0开放式加工 f ，p e r m k - p a r a l l e l j ，k p a r a ll e l 优化指标d 的形式多种多样， 序排列流水线加工( p e r m u t a t i o nf l o w s h o p ) k 台机器并行加工( k - m a c h i n ei np a r a l l e l ) 每道工序有k 台机器并行的单件加工 大体上可以分为以下几类： 7 广东工业大学工学硕士论文 ( 1 ) 以有效利用资源为目标，如c m a x ( 最大完工时间) ； ( 2 ) 以对需求的快速反应为目的的指标，如c 一( 平均完工时间) 、f 一( 平均流程 时间) 、w ( 平均等待时间) ； ( 3 ) 以遵守交货期为目的的指标，如t m a x ( 最长延误时间) 、n t ( 延误交货工件数) ： 其中，如果目标函数是完成时间的非减函数，则称为正则指标，如m a k e s p a n ，否 则称为非正则指标，如提前期，随着准时制( j i t ) 生产的兴起，目标函数为非正则 的情况逐渐得到重视；另外根据调度环境的不同，可分为静态调度和动态调度； 根据系统信息是否完全，可分为确定性调度和随机调度。 2 1 2 车间调度问题 车间调度问题”l 般可以描述为：n 个工件在i l l 台机器上加工，一个工件可以 分为k 道工序，每道工序可以在若干台机器上加工。每一台机器在每个时刻只能 加工某个工件的某道工序，只能在上道工序加工完成后才能开始下一道工序的加 工，前者称为占用约束，后者称为顺序约束。 车间调度问题的决策内容包括分配决策( 工件的加工顺序) 和时间决策( 工件 各工序的加工时间) 以及路径决策( 工件工序的加工设备的分配) 。 车间调度问题的特点是多个工件在有限的机器上加工，每台机器在切换不同工 件生产时需要一定的准备时闻。切换船工次数增加有利于减少工件的库存，但导 致生产率的下降。因此，需要在库存成本和工件切换加工频率之间取得平衡。生 产的柔性体现在设备使用和设备安排两个方面。设备使用的柔性是指设备可用于 多个零件的多个工序的加工；设备安排的柔性是指工件的设备加工路径不是固定 和预先确定的，具有可选的路径，可以通过将若干设备组成为一条或者多条生产 线加工一种工作，使得该工件生产率最大。 车间调度问题的另一类研究集中于柔性制造系统( f m s ) ，f m s 由一系列n c 数 控设备组成，n c 能够单独加工多个工件，在选择了待加工工件后，所需刀具必须 分配到该设备的工具集中。f m s 问题包括：工件选择分配、设备分组、生产率确 定和设备负荷、工具分配等问题，它的约束包括设备工具集的容量限制、设备可 用时间和设备负荷等( 方剑等，1 9 9 7 ) 。 车间调度问题有复杂性、随机性、约束性、多目标性的特点： ( 1 ) 复杂性：车间中工件、机器、缓存、和搬运系统之间相互影响、相互作用。 8 第二章生产调度理论 每个工件又要考虑它的加工时间、安装时间和操作顺序等因素，因而相当复杂。 调度问题是在等式或不等式约束下求指标的优化，在计算机量上往往是n p 一完全 问题。随着问题规模的增大，其计算量急剧增加，使得一些常规的方法无能为力。 即使对于单台机床加工问题，如果有n 个工件而每个工件只考虑加工时间以及与 操作序列有关的安装时间，则这个问题就和n 个城市的t s p 问题等价。对于一般 的加工系统，问题更复杂。 ( 2 ) 随机性：车间调度中有很多随机和不确定因素，如工件到达时间的不确定性， 实际工件的加工时间也有一定的随机性。而且系统中常有突发偶然事件，如机器 故障、作业交货期的改变等。 ( 3 ) 约束性：车间调度问题中资源的数量、缓存的容量、工件到期时间以及工件 的操作顺序等都是约束。此外还有一些人为的因素，如要求各机器上的负载要平 衡等。 ( 4 ) 多目标：调度的目标很多，而且这些目标之间往往是有冲突的。k i r a n e t a 1 ( 1 9 8 4 ) 将调度目标分为三类：基于作业交货期的目标、基于作业完成时间的目 标和基于生产成本的目标，并列举了几十种调度目标。 2 1 3 流程工业调度问题 流程工业是指通过混合，分离，成型或化学反应材料增值的企业。生产过程可 以是连续的，成批的，通常需要严格的刚性过程控制和大量的资本投入。 流程工业生产属于大批量连续生产，因而强调生产过程的整体性，工艺流程相 对稳定，流程工业的生产计划和作业调度通常是紧密联系，一般难以区分。在长 期或中期生产计划中通常同时要考虑详细的工艺问题，如投产的批量( l o ts i z i n g ) 和作业安排( j o ba s s i g n m e n t ) 同时在生产计划中出现。而在小批量多品种生产的 离散制造业中，排产问题通常是在作业计划层考虑。 流程工业的生产特性决定了其调度特征”。 i 过程瓶颈、关键资源的分析是流程工业生产调度实施的前提； 2 全过程的各级生产调度大多由生产装置加工能力的调度驱动： 3 生产调度与生产计划、预测及分配计划的关系更为紧密； 4 客户定单不直接作用于整个生产过程的调度； 5 生产装置的批量优化主要由装置加工能力及所加工产品的质量指标决定； 9 广东工业大学工学硕士论文 6 各级库存存储的优化设置是生产过程提高效益的重要手段，整个生产过程的调 度可通过在生产过程中进行各级库存的设置得以分级解耦； 7 通过建立多级成本分析、利润评价体系，从而将调度的多个优化目标形成综合 目标；成本目标、利润目标等； 8 可行、柔性的调度方案是流程工业生产调度首先应达到的目标。 目前，流程工业生产计划调度的开发已经吸引各个领域的专家的高度注意，因 为它有潜力解决现实中非常困难的问题。这方面的研究不仅具有很强的理论基础， 而且，市场需求的变化，生产制造技术和管理技术的发展，也使得研究不断深入， 特别是在对变异的建模优化和满意问题。而多目标优化，大规模的搜索和车间生 产的不确定性的问题还需进一步研究，以适应实际中的需要。 2 2 调度优化方法简介 1 ) 数学规划方法( m a t h e m a t i c a lp r o g r a m m i n g ) 数学规划法在车间调度中被广泛应用，调度问题可以用整数规划法、混合整数 规划法和动态规划法。1 来描述。由于调度问题是n p h a r d 问题，计算复杂性使得这 些方法的运用受到限制。随着新的技术、更强有力的启发式规贝q 和现代计算机所 提供的计算能力的发展，使得这些方法又焕发了活力。为克服方法自身的不足， 一些学者相应地提出了分解技术。 枚举方法与拉氏松弛法( 1 a g r a n g i a nr e l a x a t i o n ) 在整数规划中，应用最多的是分枝定界法和拉氏松弛法”1 。前者是一种枚举 方法，对于较大的调度问题，要花费很大的时间，其主要存在的问题是整数约束。 为了克服这个问题，产生了拉氏松弛法，它消除了整数约束而相应地加入代价因 子。由于其在可行的时间里能对复杂的规划问题提供很好的次优解，并能对解的 次优性进行评估，近来成为解决复杂车间调度问题的一种重要方法。文 1 0 用拉 氏松弛法解决了单机调度和多台并行机调度问题。文1 中通过引入更多的拉氏乘 子松弛了操作之间的顺序约束，将这种方法用于一般的j o bs h o p 调度问题。文 1 2 提出的用动态规划算法解决作业级子问题的方法，较好地解决将子问题分解到工 序级可能出现解振荡的问题。 2 ) 基于启发式规则的调度方法 1 0 第二章生产调度理论 调度规则因其易于实现、计算复杂度低等原因，能够用于动态实时调度系统中， 许多年来一直受到学者们的广泛研究，并不断涌现出许多新调度规则。文 6 ，1 3 中总结了几条最常用的规则，例如最短加工时间优先规贝i s f t ，最短交货期优先规 贝o e d d ，先到先加工规则f c f s 等等。分析了这些规则对系统性能如作业的平均等待 时间、机床的平均利用率、作业总加工时间等的影响。调度规则是基于经验和特 定问题获得的，调度的计算时间有所减少，但所用规则只适合特定场合，故求得 的解仅是可行解而牺牲了解的最优性。 3 ) 人工智能 8 0 年代开始t a i 嘲在调度问题中的应用研究。专家系统和基于知识的系统发展较 迅速，它们有如下一些优点：( 1 ) 在决策处理过程中同时采用定性和定量的知识； ( 2 ) 能生成启发式规则，这些规则比分派规则复杂：( 3 ) 可以在整个车间信 息的基础上选择最好的启发式规则；( 4 ) 能敏锐地获得信息之间的复杂关系， 并采用特殊的技术来处理这些关系。但也存在一些不足之处，开发周期长，成本 昂贵；需要丰富的调度经验和知识，然而获取它们是比较困难和有限的；对新的 环境适应性差等。 专家系统基于知识的系统 二者均由两个部分组成：知识库和推理机制。知识库包括一些规则、过程和启发 式信息等；推理机制用来选择一种策略处理知识库中的知识，以便随时解决问题。 推理机制分为数据驱动和目标驱动两种。文“”中以一个柔性p c b ( 印刷电路板安装 系统为实例，提出了基于知识的调度方法k b s ( k n o w l e d g eb a s e ds c h e d u l i n g ) 。 些比较有名的专家系统有i s i s 、o p i s 和s o n i a 等。 分布式a i ：智能体( a g e n t s ) 由于一个单一的专家系统或基于知识的系统所具有的知识有限和处理问题能 力不强等因素，人们开始开发分布式调度系统，人工智能的对策就是智能体。一 个智能体有着与其它智能体完全不同的软件处理过程，它完全依赖自己的知识库。 在车间调度问题中，智能体系统由两大类智能体组成：任务智能体和资源智 能体。任务智能体负责处理调度中的各种任务类型作业，如物料运送、加工等。 与具体的任务相关联的任何性能指标都可以用来评价这些智能体的工作效果。每 个资源智能体负责单一或某一类资源。任务智能体将资源请求发送给相应的资源 智能体，同时捎带那些资源应该进行的一系列操作。在受到这样的一个请求后， 广东工业大学工学硕士论文 资源智能体必须根据自己的性能指标产生一个新的调度，然后根据结果决定是否 接受这个请求。为了防止没有资源智能体接受请求的情况发生，必须建立协作机 制。到目前还没有统一的规范来设计和实施协作。 4 ) 仿真调度方法 由于制造系统的复杂性，以致于很难用精确的解析模型对其进行描述分析。但 是仿真却能提供这种理想模型，可以定量地进行评估，从而对实际系统采用合适 的调度方法“”。仿真方法用于调度的优点有：( 1 ) 实验时间短，不受时空限制； ( 2 ) 可以测试不同调度决策的性能，以选择较优的调度决策；( 3 ) 能够对用分 析方法解决的问题寻求可行解等。但其也不可避免地存在一些问题：对理论贡献 不大；应用仿真进行生产调度的费用高；仿真的准确性很大程度上受编程人员的 水平的限制。 5 ) 基于d e d s 的解析模型方法 由于制造系统是一类典型的离散事件系统，因而可以用研究离散事件系统的方 法来研究调度问题，这一类型的方法主要有排队论、极大极小代数模型、p e t r i 网等。 排队网络方法。在随机库存系统、随机服务系统和p e t r i 网络系统等三类典型 d e d s 中有着广泛应用，在车间调度系统，它可以分析系统生产率、平均生产时间 等，但它很难将车间的其他资源考虑进去，很难处理系统出现异常时的情况。 p e t r i 网方法。p e t r i 网模型属于d e d s 建模事件图技术中用得最广泛的一类。 其方法的核心是将d e d s 表示成输入位置、输出位置、转移位置、转移节点和有 向弧线连接起来的二元有向图，如果记d e d s 的所有位置节点集合为p ，转移节点集 合为t ，转移方向的所有有向弧线集合为f ，则最基本的p e t r i 网可用三元素组 ( p ，t ，f ) 表示。 采用p e t r i 网方法建模具有明显的优点；( 1 ) 基于事件图的表示方法使得 模型直观，便于系统分析；( 2 ) 采用p e t r i 网建立的模型可用于直接分析模型的 有效性和合理性，识别模型是否包含诸如死锁、状态空间非有限等异常情况；( 3 ) 便于系统设计者从不同抽象层次上采用从上到下的方法对d e d s 进行仿真。 但目前p e t r i 网应用于制造系统调度存在以下问题( 1 ) 节点语义的单义性， 使得所携带的系统信息不够丰富；( 2 ) 重用性差；( 3 ) 当调度规则或方法复杂 时，建模困难。 1 2 第二章生产调度理论 6 ) 模拟退火法 模拟退火法“”( s i m u l a t e da n n e a l i n g ) 模仿晶体结晶的冷却过程，在较高温 度t s 下，系统状态为s ，能量( 即目标函数) 为e ，选择的一个邻域s ，如果， e ( s 7 ) e ( s ) 则接受s 为下一状态，否则以概率e x p ( 一( e ( s ) 一e ( s ) ) t s ) 接受s 。经 过一定次数( 称为m a r k o v 链长) 的搜索，认为系统在此温度下达到平衡，则降低温 度t s 再进行搜索，直到满足条件。模拟退火法的改进算法有加温退火法、有记忆 的模拟退火法等。由于模拟退火法能以一定的概率接受差的能量，因而有可能跳 出局部极小，但它的收敛速度较慢，很难用于实时动态调度环境。文 1 8 提出一 种改进的模拟退火法，用来解决具有最小m a k e s p a n 指标的f l o ws h o p 排序问题， 并与禁忌搜索法等进行了比较。 7 ) 禁忌搜索法 禁忌搜索法是用来搜寻组合优化问题的近优解的启发式方法，g l o v e r 在文 1 9 中叙述了它的基本原理。它的任何应用都是面向问题的，都需要定义有针对性的禁 忌搜索的结构要素：移动、邻域、记忆结构、吸入条件函数、邻域搜索策略、终 止条件、初始解。还有一系列的控制参数，如禁忌表的长度l t b ，搜寻终止条件 i s r 和吸入条件。所设计的禁忌搜索算法的性能，如寻优质量、收敛速度、搜索时 间等既取决于结构要素，又取决于控制参数。目前，禁忌搜索已广泛应用于生产 作业计划问题，但主要是以加工周期( m a k e s p a n ) 最短为目标。文 2 0 用禁忌搜索 算法研究面向j i t 的生产作业计划问题，文 2 1 用禁忌搜索算法研究最小化拖期任 务数的并行多机调度问题，而文 2 2 对混合f l o ws h o p 调度问题设计了一个简化的 禁忌搜索方案。 8 ) 神经网络优化 神经网络模仿了人类学习和对事物的预测能力，是一种并行处理模型。这种 模型根据网络拓扑结构、节点特征和训练或学习规贝| j 的不同而变化。神经网络以 数值计算代替知识推理，具有较高的可靠性和完备性，能突破串行计算的限制， 因此在计算规模、处理能力和可扩充性等方面有巨大的潜力。文 2 3 中为了解决 大规模问题，又提出一种改进的t a n kh o p f i e l d 网络的整数线性规划神经网络i l p n n 来解决j o bs h o p 调度问题。文 2 4 中也提出了一种用于解决j o bs h o p 调度问 题的神经网络方法。神经网络的复杂性是随节点数非线性增长的，在目前的计算 环境下，对于大规模、多分枝、多组合的复杂系统，神经网络可能会因结构过于 广东工业大学工学硕士论文 庞大而产生参数调整困难和收敛速度缓慢或收敛于非可行解等弊病。同时，普通 神经网络结构完全根据对问题的描述建立神经元之间的数值连接关系，缺少一定 的灵活性和柔性，难以满足多变化、多目标的f m s 实际系统的需求嘲。 9 ) 遗传算法0 6 州 g a 的基本思想来源于分子遗传学和生物进化论。其基本原理是，产生若干代表 问题候选解的成员，并组成一个群体，按照某一评价函数或算法对群体中的每个 成员进行评估，评估结果代表解的良好性。按照适者生存、优胜劣汰的原则，群 体中的某一成员愈适合，则愈有可能产生后代。利用遗传操作符对群体中的成员 进行遗传操作，产生新的后代，这种后代能继承双亲的特征。对后代进行评估， 并将其放入群体，代替上一代中较弱的成员( 非良好解) 。此过程反复执行，这 构成一代一代的群体。随着遗传过程的不断进行，越来越良好的解就可以得到。 一些学者经过研究发现，遗传算法比经典的启发式算法好，同时遗传算法比 传统的搜索技术有更强的鲁棒性，因为它不仅能解决某一特定问题，而且可以适 应不同的问题形式。文 2 8 用遗传算法解决了一类模糊流水车间调度的问题，文 2 9 对流水车间的调度设计了一种混合式的遗传算法。 遗传算法的优越性归功于它与传统搜索方法不同的特定结构： ( 1 ) g a 的工作问题是编码，对搜索问题的限制极少，对函数的一些约束条件象连 续性、可导性等不作要求，减少了要解决的问题的复杂性。 ( 2 ) g a 是同时搜索解空间内的许多点，因而可以有效地防止搜索过程中收敛到局 部最优解，并获得全局最优解，与其它单点搜索的方法相比，在计算时间上也有 较大的优势。 ( 3 ) g a 使用遗传操作时是按概率在解空间进行搜索，因而既不同于随机查找，也 不同枚举查找那样盲目的穷举，而是一种有目标、有方向的启发式搜索。 2 3 生产调度问题的调度策略 由于一般的调度问题的复杂性，各种不同的具体问题往往有很多不同的解决 方法，因此需要从策略上去考虑调度问题1 ，形成各种研究方法策略以指导调度 的研究。目前调度的策略有并行或分布策略、分解与成组策略、人机交互策略、 动态重调度策略、多目标优化策略等等。 1 4 第二章生产调度理论 ( 1 ) 并行和分布策略 由于般调度问题很复杂，一旦问题规模加大就更难求解，因此不少研究者提 出并行或分解的策略来解决调度问题。姜作廉等( 1 9 9 4 ) 使用组合优化的分级决 策方法和b a b 相结合，在并行机系统上，构造了并行算法m b a b ，解决了规模较大的 流水车问调度问题。康一梅等( 1 9 9 7 ) 提出用m i m d 并行机实现j o bs h o p 实时调度 的并行算法。多智能体系统的研究是目前分布式人工智能领域的研究热点。大量 的研究表明多智能体系统特别适用于解决复杂问题，尤其是那些经典方法无法解 决的单元间有大量交互作用的问题。由于调度问题的复杂性和并发性等特点，最 近多智能体己在在调度上得到了较多的应用。k a p h k e t a 1 ( 1 9 9 6 ) 将每个代 理对应为一个加工中心，采用事件驱动的动态调度，研究了代理之间的调度策略 共享及如何协调各个代理的行为以完成一个全局调度目标。李飒等( 2 0 0 0 ) 针对 随机性j o bs h o p 调度问题，提出了一种基于多智能体的车间调度方法，实现了代 理之间协商解决矛盾的动态调度，并建立了相应的制造资源数据库。多智能体系 统不但速度快、可靠性高、可扩展性强、能处理带有空间分布的问题、对不确定 性数据和知识有较好的容错性：而且，由于是高度模块化系统，因而能澄清概念和 简化设计。因此它必将得到更加广泛的应用。 ( 2 ) 分解与成组策略 利用分解和成组调度策略可以大大降低问题的计算复杂性和规模，求得调度 问题的较优解。h i r a b a y a s h ie ta 1 ( 1 9 9 4 ) 提出一种分解决策，先将工件分批， 再对每批工件进行子调度，通过随机组合子调度来构成整体调度。成组技术( g t ) 在制造系统中己得到广泛应用，其基本思想是根据工件、机器等之间的相似性将 它们分组，这样利用组内的相似性可大大地提高工作效率。顾擎明等( 1 9 9 8 ) 研 究了柔性制造系统中工件的加工调度问题，通过对加工路线作弱化处理来提高调 度质量。即在工艺约束条件下确定工序的成组优化，利用遗传算法可以有效地解 决这一过程的寻优问题。王成尧等( 1 9 9 9 ) 基于成组技术和启发式规则( e d d ：s p t ) 较好地解决了平行机台最小拖期调度问题。 ( 3 ) 动态重调度策略( 方剑，1 9 9 7 ) 由于实际的加工系统具有随机性和不确定性，静态调度的结果很难适应实际生 产的需要，往往需要重新调度。特别在动态环境下，调度本身就是不断地动态重 调度的过程。c h e n 提出一种实时反馈调度的策略根据系统运行过程中缓存中的工 广东工业大学工学硕士论文 件来实时在线调度。当系统状态发生变化时就进行调度称为连续调度。y a m a m o t o 分别研究了五台加工中心的实际制造系统在机器发生故障时的重调度问题。连续 调度可很快地跟踪系统状态的变化，但对一个大的制造系统来说，系统状态变化 快，这样系统可能一直处于重调度状态，而且计算时间的要求也可能无法满足实 际需求。另一种调度策略是周期性调度，即每隔一段时间就重新调度一次。周期 性调度避免了连续调度的缺点，但它对突发事件反应慢，可能会导致系统性能的 下降。l a u r a 提出将两者结合的周期性和事件驱动调度策略。定义一些关键事件， 如机器出现故障、工件的到期很紧。当关键事件发生时，立即重新调度，否则周 期性调度。为了减少重调度的计算量，r o n g ( 1 9 9 8 ) 针对实际生产中产生重调度的 因素，提出一种构造二进制数的启发式策略，它只对受调度因素影响的工件和工 序来重调度。滚动优化的思想很早就被应用于生产调度。与常规调度方法相比， 滚动调度可避免生产的大幅度波动。在滚动调度中，对某一些区间内的工件( 工 件窗口) 进行调度。但按时间只对此区间内的部分工件进行实际加工，然后再向 工件窗口中加入新工件来形成滚动。滚动调度不仅可以应付f m s 中的不确定性和突 发偶然事件，而且每次只对工件窗口内的工件进行调度，可使问题求解规模大大 减小，李岩等( 1 9 9 6 ) 将遗传算法运用于滚动窗口内的工件调度，翁妙风( 2 0 0 0 ) 提出了基于并行进化规划、周期性和事件驱动的两种有( 无) 窗口的重调度策略， 这样做虽然不能得到全局最优解，但利用滚动机制仍然得到较为满意的解。 ( 4 ) 多目标决策 实际调度问题往往是多目标的，如最短生产期、最大生产利润，而且这些目标 往往相互冲突。对多目标优化问题，数学规划中的处理方法有约束法、评价函数 法、分层序列法和功效系数法等。车间调度中的多目标决策往往要结合具体问题 d a v i de ta 1 ( 1 9 9 3 ) 在重调度时考虑了双重目标，既要保持调度的效率又要减 少重调度的代价，这两个目标是相互冲突的。他们采用两种方法：将两目标加权 和作为目标或采用基于树扩展的双重目标梯度下降法。此外还有研究者根据规则 估计各目标函数强弱，通过加权和来解决多目标和有冲突目标的调度问题( 黄小 原等，1 9 9 5 ) 。 ( 5 ) 人机交互策略 由于调度问题的复杂性，至今还未形成一套系统的理论与方法。为了考虑实际 调度中存在的各种复杂因素及调度的多目标性，以取得好的调度结果，往往需要 1 6 第二章生产调度理论 好的人机交互策略与手段去利用和启发调度决策者的经验知识。例如s l o m pe ta l ( 1 9 9 2 ) 提出了f m s 中用于作业调度的一种交互工具。 2 4 本章小节 生产计划与调度问题就是一个生产资源的优化配置问题。本章首先简单介绍了 生产计划与调度的一些相关概念，并把生产计划与调度问题分为车间调度问题， 和流程工业调度问题进行了阐述。随后分析了调度常用的优化方法，并着重研究 了调度的策略问题。 1 7 广东工业大学工学硕士论文 第三章禁忌搜索算法 禁忌搜索( t a b us e a r c h 或t a b o os e a r c h ，简称t s ) 。1 “的思想最早由 g l o v e r ( 1 9 8 6 ) 提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法， 是对人类智力过程的一种模拟。t s 算法通过引入一个灵活的存储结构和相应的禁 忌准则来避免迂回搜索，并通过藐视准则来赦免些被禁忌的优良状态，进而保 证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算