《生产线上的调度问题与局内策略的研究》由会员分享，可在线阅读，更多相关《生产线上的调度问题与局内策略的研究（67页珍藏版）》请在金锄头文库上搜索。
1、摘要 论文题目:生产线上的调度问题及局内策略的研究 指导教师: 管理科学与工程 辛春林 徐寅峰 签名: 签名: 摘要 本文运用竞争策略研究了生产线上的三个具有实际应用背景的 局内调度问题，即生产线上的k - 配送小车调度问题、局内流水线排故 问题、局内故障产品处理问题，建立了与之对应的数学模型，设计了 不同的竞争策略，得出了一些对企业生产管理具有指导意义的结论。 对于生产线上的 k - 配送小车调度问题，应用复位策略得出竞争比为 k + 2 ，又设计了另一种竞争策略一局部双覆盖策略 口 D C S ) ，得出竞 争比为k ，运用这两种竞争策略简单地分析了该问题的一个特例一局 内k - 电梯调度
2、问题， 该问题从竞争比来看， 局部双覆盖策略优于复位 策略;对于局内流水线排故问题，设计了三种不同的竟争策略，证明 采用均分 流水 线策略( A 6 D S ) , 竞争比 为I 十 ; ， 采用最优分 割策略 ( 刀 砚 夕 ) ， 竞 争比 为1 十 称采 用 等 分 工 序 策 略( 尺 舰 夕 ) ， 竞 争比 为1 十 贪 从竞争比 来看， 最优分割策略优于其他两种策略， 分析了该问 题的一 个 特 例( 工 序 等 距 的 情 况 ) ， 三 种 竞 争 策 略 得 出 的 竞 争 比 均 为 I + L m ,- J ; 对于局内故障产品处理问题，设计了两种竞争策略，证明采用优先
3、返 修 策 略 I ( “) ， 竞 争 比 为 (2 - 1 ) . ， 采 用 优 先 返 修 策 略 I I ( 1 1 ) ， 竞 争 比 为 仁 一 击) 奇 ， 对 这 两 种 策 略 做 出 了 比 较 并 相 应 的 给 出 了 比 较结果， 即从竞争比 来看，当Y 竞 争 比 为 仁 一 f). 箭 ; 采 用 优 先 返 修 策 略 II ( P R R S I I ) ， 竞 争 比 为 (2 - 击 ) 箭 ; 最 后 ， 对 局 内 故 障 产 品 处 理 问 题 的 两 种 策 略 做 出 了 比 较 并给出了比较结果。在本章最后部分指出了进一步的研究工作。 第三部
4、分是第6 章， 对论文进行了总结，总结了主要工作及论文 中有待进一步改进之处。 其中的第3 , 4 , 5 章是本文的核心内容和重点， 体现了作者的主 要工作。 西安交通大学硕士学位论文 问题的背景和研究意义 生产调度问题的理论综述、 局内问题与 竟争策略，调度问题的一些实例 生产线上的 k - 配 送小车调度问题 局内流水线排 故问题 局内故障产品 处理问题 图 卜3论文结构 生产调度、局内问题和竞争策略 z 生产调度、局内问题和竞争策略 2 . 1 生产调度问题的理论综述 2 . 1 . 1 生产调度问题 所谓调度，直观地说，就是对加工过程进行作业计划。对加工过 程的合理调度， 可有效提高
5、资源的利用率和生产的效益 ” 。 对生产过 程任务调度问题的研究源于2 0 世纪5 0 年代，由于该问题的实用性和 重要性，随之在运筹学和工业工程等学科中形成一个独立的分支方 向。 近几十年来，随着市场竞争的加剧和客户需求的个性，现代生产 正朝着 “ 品种多样、批量变小、注重交期、减少库存”的方向发展， 制造系统的调度问题愈来愈受到重视。 2 . 1 .2 生产调度问题的分类 通常， 按照企业生产方式和加工作业方式的不同，可以将生产调 度问题作不同的分类。 功 开环车间型和闭环车间型调度问题 从宏观的角度，可以按生产方式的类型，把调度问题分类为 “ 开 环车间 ( o p e n s h o
6、p ) 型” 和 “ 闭 环车间 ( c l o s e d s h o p ) 型” 。 开环车间型生产方式的特点是，不考虑库存的设立，所生产产品 的订单均直接来自 于顾客。闭环车间型生产方式的特点是，顾客 需求的产品均由库存提供，生产任务一般只由产品存储策略来决 定。两类不同的生产方式导致它们在调度问题上的重大差别。 对于开环车间型调度问题，生产调度只归结为对工件的加工 排序，即订单所要求的产品在每台机器设备上的加工排序。对于 闭环车间型调度问题，生产调度不仅包括对工件加工的排序，而 且涉及对产品批量大小的计划，即同时要对各类产品决定与库存 补充过 程相关联的 批量大小 ( l o t -
7、 s i z i n g ) . . 由 此可见， 相对于开环 车间型调度问题，闭环车间型调度问题在求解和分析上要复杂得 多。 闭环车间型调度问题的实质归结为，寻找一个调度策略，在 满足由于生产工艺要求所导致的约束下，使调度策略所确定的产 品生产批量和机器加工排序下某个性能指标如生产费用为最小。 其中，对一组产品的需求表现为一组需求过程，与生产相关的总 费用一般包括产品的库存普用、固定的开工准各费用和可变的生 西安交通大学硕士论文 产费用等。 闭环车间型调度问题通常称之为“ 批量大小调度问题， 。 对应地，开环车间型调度问题可称为 “ 加工排序调度问题” 。 2 ) J o b - S h o
8、 p 调度问 题和F l o w - S h o p 调度问 题 在开环车间型调度问题中，J o b - S h o p( 任务作业)和 F l o w - S h o p( 流水作业)是两类最基本和重要的调度问题。 通常对于开环车间型调度问题，研究对象是由 M 台机器 沁， ， 二 ， M m 加 工。 种 工 件夕 , ， 一 ， J 的 一 条 生 产 线 ， 其中 ， 称 所 加工的工件为任务 ( j o b ) ，工件在机器上的加工为操作 ( o p e r a t i o n ) ，工件基于加工工艺所决定的限制在某些机器M上 的 加 工 顺 序 为 约 束 条 件， 并 且， 设吼
9、为 第i 个 工 件砚 在 第 .1 个 机 器M ， 上的 操作，同 时 设 每个操 作O J 所需要的 作 业时间 是固 定 的。对此类生产线，调度问题即加工排序问题的提法是，要对每 台 机 器 M ， 来 确 定。 个 工 件J ; ( i 一 1 , . - . , n ) 的 一 个 加 工 顺 序 ， 在 与 工 艺约束条件相容的前提下，使所指定的某个性能指标达到最优， 即最大或最小。 因 此， J o b - S h o p 和F l o w - S h o p 调度问 题的 定义如下: 对于开环车间型加工排序问题， 若按工艺要求不同工件具有 不同的 加工顺序， 则称其为J o
10、b - S h o p 调度问 题。 若按工艺要求， 每个工件都有相同的 加工顺序， 则称其为F l o w - S h o p 调度问 题。 2 . 1 .3 生产调度问题类型的简明表示法 一个离散制造系统的调度问题， 其基本特征可以有 “ 工件类数” 、 “ 机器数” 、 “ 工件流经机器形态类型” 、 “ 性能指标类型” 等来完全刻 划。 因此， 通常采用 n / m / A / B ” 的简明表示法来描述调度问题的类型， 以规范和简洁调度问题的表达方式。 在 n / m / A / B ”的表示法中，各个符号所代表的含义为: n( 以数字表示) ，用来代表工件类数。 m( 以数字表示)
11、 ，用来代表机器数。 A( 以字母表示) ，用来表示工件流经机器形态的类型。例如，若 取其为F ， 则代表F l o w - S h o p( 流水线) 或称为串 行加工线; 若取其 为P ， 则代表P e r m u t a t i o n F l o w - S h o p( 置换流水线) ; 若取其为G ， 则 代表一般J o b - S h o p( 任务作业)问题。 生产调度、局内问 题和竞争策略 B 以 符号表示) ， 用来表示性能指标的 类型。 例如， B 取C m - 代 表 完 成 所 有 作 业 的 最 大 时 间 蠕一 m a x 乌。 2 . 1 .4 生产调度问题的求
12、解方法 总体而言，可把求解调度问题的方法区分为 “ 精确求解方法”和 “ 近似求解方法”两类。属于精确求解方法的策略，包括有各种解析 形式的解、分支定界法等。 属于近似求解方法的策略，包括有基于规 则的启发式调度方法、邻域搜索方法等。 2 . 2 局内问题 局内问 题和竟争策略的研究起始于S t e a t o r 和T a rj a n的工作。经 过近二十年的研究和发展，随着局内问题的大量发现， 有关的研究成 果层出不穷， 新研究方向， 有关的论文也与日俱增，它已成为一个非常值得注意的 参见文献 于 氏 一 10 ， 。 局内问 题 ( O n - l i n e P r o b l e m
13、) ， 亦可称之为联机问题和在线问 题， 它提出于上一世纪七十年代至八十年代初期，但是直至 S l e a t o r和 T a 巧 a n 提出将局内策略与最优的局外策略进行比较，局内问 题才得以 广泛和系统的研究起来。局内问题是对应于局外问题 ( o f f - l i n e P r o b l e m)而言的，在我们的现实生活中，这类局内问题的例子随处 可见。几乎每个人都有过这样一种体验:当你对某段时间的工作或生 活进行回顾和总结时，你总是情不自 禁的在想，要是我当初这样做， 现在就会更好一些。其实此时你面对的就是一个局内与局外的问题。 当你进行回顾与总结时，你置身于局外，可以看到事物
14、的全部，从而 易于评论， 得出 对你而言的最佳方式。 可是当你经历这些事件时， 你 通常只能看到事物的一部分， 所以很难做出最优决策。这就是我们通 常所说的:当局者迷，旁观者清。 大千世界时时刻刻处于运动变化之中，运动是物质的固有属性。 现实生活中的许多经济现象通常都具有非常强的动态特征， 一切事物 通常都是随着时间的 推移而不断变化的。 但是人们在面对现实生活中 的具体问题时，总是忽略或者无法把这些动态因素考虑进去。 人们对 于这些现象一般是先进行数学上的抽象， 然后用静态或统计的方法来 加以研究和处理。从优化的理论和方法上看， 经典的优化理论大多是 西安交通大学硕士论文 站在旁观者的立场上
15、看问题，即首先确定已知条件， 然后在假设这些 已知条件不变的基础上给出最优方案 ( 即最优解) 。条件一旦发生变 化， 这种方法所给出的最优方案就会失去其最优性。 物质世界总是瞬 息万变的， 在各种各样的决策中， 不确定的因素总是存在。 如果这种 变化的不确定因素对所考虑的问题影响很大， 那么将如何处理这些不 确定因素而做出较佳决策呢? 为了能更好的说明此类问题，我们先来看一个例子: 设有一连通的图G ，其 n顶点均为服务对象，且可以随时提出服 务要求，现有k 辆车按照服务要求提出的先后顺序来往服务于n 个顶 点之间。假定k 辆车的初始位置已经确定。考虑如下问题: 1 )事先给出一个要求服务的
16、顶点序列，如何调度车辆最节省? 2 )如果服务要求是在服务过程中一个个的接到的，及在每一时 刻只能知道在此以前的要求与服务过程， 那么， 如何调动车辆 比较节省? 该问题就是著名的k - 车服务问题，其优化的目 标函数是车辆行驶 的总里程数。问题 1 )是个局外问题，而问题 2 )是个局内问题。两 者的不同点在于可知的服务要求是全部还是局部。问题 1 )的最优解 并不难找，可是问题 2 )就有些棘手。这是因为服务要求对调动方案 有着致命的影响。 这种影响不仅对当前的调度决策和以后的调度决策 产生影响， 而且对以前的调度决策也有着致命的影响。 所以这种影响 是这对整个方案而言。这正是局内问题进行研究的原因所在。 综上所述，局内问题就是一类决策者置身于事件的发生
