英语原文共 20 页，剩余内容已隐藏，支付完成后下载完整资料

结合仿真与优化的有维修约束的混合流水车间调度

摘要

基于机器连续可用假设的调度问题在以往的文献中已经得到了广泛的研究。然而，在大多数现实产业设置中，一台机器可能由于很多原因变得不可用，如意外故障（随机不可用），或者计划好的预防性维护，此时会知道哪些时间段机器不可用（确定性不可用）。在本文中，我们研究维修约束条件下的混合流水车间调度问题，以优化基于流动时间和交货期的若干目标。在此模型中，我们还考虑了设置时间（setup time），清洁时间和运输时间，本文首先分析我们如何能够整合仿真和优化，以解决这个强意义上的NP-hard实际问题。第二是通过实验研究，表明启发式算法在该问题的应用会受到机器故障时间百分比的影响。最后是要表明这种方法可以在某些情况下表现的比NEH启发式算法做的更好。

关键词：混合流水车间；维修约束；仿真；优化

1 引言

新的产业应用提出的要求不断变化。这种变革赋予了运作-生产功能一个很重要的地位。它的主要目的是寻找一个好的调度，在考虑各种可能约束的情况下使生产成本最小化。在工业生产领域中，当前的趋势表明强大的制造系统必须迅速适应市场的波动（随机请求）和内部扰动（机器故障）。机器必须能够同时且有效地制造多种类型的产品。在这样的背景下，对投资者和生产者而言，优化生产计划和调度，以及对机器的控制显得越来越重要。在这些条件下，如何确定生产速度，维修策略，调整策略和调度规则，以便使系统运作成本最小化，是如今生产系统优化领域最重要的问题。

很明显，调度问题的文献研究和现实生活中的行业事实有很大的差距。例如，在调度的期间我们假定机器总是可用的。本文主要处理一个实际的随机问题。有关于如下几个标准的调度问题:如完工时间，混合流水车间中基于维修，清洁，机器调整，运输等约束的延迟和提前。这个问题的随机因素涉及到考虑机器故障的问题。这种调度环境是一个通用的模型，它可以用于有串行车间的生产系统的建模，如半导体制造系统。

这篇文章有三个目标。首先是展示我们如何可以集成采用RAO模拟器进行的仿真和使用结合一些调度规则和启发式算法的的模拟退火算法优化来解决这一实际和随机的双重复杂性（算法的复杂性，结构和功能的复杂性）问题。其次是要展示应用于这个问题的启发式算法的性能表现如何会受到故障时间的影响。最后将我们的方法与NEH方法进行比较，后者是不考虑维修约束情况下已知的表现最好的启发式算法。

首先，我们对这个问题进行陈述，之后我们把重点放在混合流水调度和维修约束调度的文献综述上。然后，我们会介绍处理该问题的方法。最后，我们将进行实验研究，针对不同的优化目标，不同的机器故障百分比，和不同的加工类型来评估我们的启发式算法（见图1）。

图1. 混合流水车间环境

2 问题描述

在本文中,我们主要研究混合流水车间(HFS)调度问题环境。假定有u个工序，每一个工序k(1le;kle;u)有m_k个相同功能的多台并行机器，所有工件需要在所有阶段以相同的顺序进行加工。每一个工件包含一连串u个工序和依照顺序加工的相关操作序列O_i1,hellip;，O_iu（见图.4）。

在经典的流水车间问题中，每个阶段只会涉及到一台机器。在任何时候每一个工件至多只能由一个机器加工，相应的一台机器在同一时间内至多加工一个工件。为了对混合流水车间组织进行调度，做了以下基本设定：

• 所有N个工件的调度都是独立的，在时间t=0可以用于加工。
• 同一阶段的机器可以是完全相同的，相似的或者不相关的。
• 工件i在阶段k中的机器j上的加工时间P_ijk是已知和固定的。
• 每一个工件都有它自己承诺给客户的交货日期d_i。
• 任何工件的中断和分解是不允许的：一旦一个工件开始在机器上加工，就要继续进行直到完成。
• 工件可以被允许在两道工序之间进行等待，同时库存是无限制的。
• 安装，清洁和运输时间是不能够被忽略的，它们不被包含在加工时间里面。

在大部分论文中关于处理调度问题的假设中，机器在调度的整个过程中都是完好可用的。但是，在大多数现实问题中，一台机器会由于各种原因而变得不可用。如不可预见的故障（随机不可用）或者由于定期的预防性维护期导致的不可用（也称之为空白期），这个是提前已知的（确定不可用）。在文献中有两种处理时间：“可恢复的”（r）和“不可恢复的”（nr）。这些术语定义详见如下（参考Lee，1997）。假设一个空白期中断了一个工件的加工。如果在这个工件在机器恢复重新加工后，在时间上没有任何损失或者恢复的处罚，那么这个问题被称之为可恢复的；简称“r”。另一方面，当机器再次恢复可用时，如果工件必须从头开始处理（之前加工过的地方被浪费），那么这个问题就被称之为不可恢复的；简称“nr”。在本文中，我们会涉及到这两种情况：可恢复的和不可恢复的。

在本文中有三种决策指标是在调度问题中被经常涉及考虑到的：

• 资源的有效利用：最大完成时间（或完工时间）C_max。
• 对需求的快速响应，或者在制品最小化：平均完成时间，平均流动时间，平均等待时间
• 与指定交货期的契合程度：平均延迟时间，最大延迟时间T_max和延迟工件数N_t。

在一个典型的混合流水车间调度问题的研究中，优化流程一般只考虑机器的产能和速度。但是，关于此问题的优化过程，还需要考虑到机器的可用性。我们可以通过一个简单的例子来说明这个因素。我们假定有三台机器的一个两道工序的混合流水车间模型，其中一台机器处理第一道工序，另外两台相同机器处理第二道工序，以此来同时处理三个工件（J₁、J₂、J₃）:

阶段1 阶段2

J₁ 2 4

J₂ 2 2

J₃ 2 2

图2. 没有机器可用性约束限制

我们可以通过图2所知，上述两个模式（即：在第二阶段，J₁和J₃在第一个机器上加工，J₂在在第二个机器上加工，或者相反）是相似的，因为整体完工时间一致，都是8。

但是现在如果有机器不可用这一个条件作为约束，那么结果就一般不是这个样子的。我们也通过举例来说明这个特殊情况，我们规定，在第二阶段中第二个机器是受不可用时间限制的（见图3），它的开始时间为6，结束时间为8。

图3. 有机器可用性约束限制

由上面可知，这两种情况下的总体作业时间是不同的。在这种情况下主要考虑的是机器的不可用性，而机器的容量以及速度是一样的。因此，上面的例子对于本文研究的问题有一个很好的启示作用，我们也应该考虑到机器由于维护导致的不可用约束条件：预防性维护和机器故障。

3 文献综述

3.1混合流水车间（HFS）

混合流水车间调度问题不是一个简单的问题。大部分作品都在探讨着这三个问题：处理的复杂性，建模的标准和解决方案。在处理复杂性方面的研究，目前研究工作大致分为三类：(1)两阶段的HFS，（3）三阶段的HFS，(3)k阶段的HFS（Linn amp; Zhang, 1999)。在多项式时间内解决流水车间问题的唯一类型是两机流水车间问题F2Cmax (Johnson, 1954)。F3Cmax问题是强意义上的NP-hard问题（NP-Hard或者NPH）(Garey amp; Johnson, 1979)。而即使第一阶段只有一台机器，第二阶段只有两台机器的F2（P）Cmax问题，也是强意义上的NP-hard问题(Hoogeveen, Lenstra, amp; Veltman, 1996)。同样的，也有几个特殊情况下的双工序混合流水车间问题的文献研究。Arthanary 和Ramamurthy 在1971年开发了一个分支定界法求解F2（P）Cmax问题，该算法对包含10个以上工件的问题规模是没有效率的。因此，研究人员针对一些启发式算法在多项式时间内给出了一个近似解。Lee 和 Vairaktarakis 在1994年在关于F2（P）Cmax 这个问题的最佳误差界限，给出了一种基于Johnson算法的启发式算法。这个误差值是2-(1/m)。在同一篇文章中，他们同样提出了基于Johnson的具有相同误差界限的F2（P）Cmax问题的启发式算法。而F2（P）Cmax 问题的求解方法，已经被Gupta 在1988年, Rao 在1970年和其他人研究过。Sriskandarajah 和 Sethi 在1989年提出了一个关于误差界限r((7/3)-(2/3m)le;rle;3-(1/m), Theta;(mn log n).)的研究。另外一个误差值3-(1/m) 由Langston 在1987年研究所得。Wittrock 在1988年针对每个阶段具有相同机器的k阶段的HFS问题，提出了以缩减最大完工时间的启发式作业排序研究。Brah 和 Hunsucker 在1991年完善了关于k阶段的HFS以缩减最大完工时间的分支定界法的研究。Rajendran 和 Chaudhuri 在1992年完善了关于k阶段HFS以缩减最大完工时间和总流量时间的分支定界法的算法研究。Vignier等人 在1996年研究了关于k阶段的 HFS的最小总完工时间问题。更多关于混合流水车间问题的以下科研工作者也研究过：Sahni (1976), Narasimhan 和 Panwalkar (1984)，Gupta 等人(1994)， Dessouky 等人 (1998)，Verma 和 Dessouky (1999)， Schuurman 和 Woeginger (2000) 以及 Ohno 等人 (2002)。

3.2有维修约束的调度

在关于两机流水车间问题研究中，不考虑维修约束的以总生产时间最小化为目标的双机流水车间调度可能是此领域第一个被研究者考虑的“多机”问题。关于这个问题的最佳解决方案正是由Johnson所提出。自从那时以来，这个问题经历了几个方面的扩展和变化：Lee (1997)， Lee (1991, 1996)， Lee 和 Chen (2000)， Lee, Lei, 和 Pinedo (1997) 以及 Liu 和 Sanlaville (1995)，这些研究人员对早期的相关研究贡献做了全面的回顾。我们关心的此问题的一个变化形式是预防性维修的出现，它们的研究成果总结如下。Lee 在1997年证明了一般意义上的一台机器上的预防周期问题是一个强意义上的NP-hard问题。他还开发了在一个时期只有一台机器情况下的伪多项式动态规划模型。他还提出了时间复杂度O(n log n)的启发式算法，同时也证明分析了误差值。Schmidt 在2000年对机器有限可用的调度问题做了更加详尽的研究。他为单台机器、并行机器和流水车间问题提供了研究结果。他通过枚举优化算法以及启发式算法分析出了一些结论。Chen 在1995年研究了考虑第一台机器上的预防性约束的双机流水车间调度问题。他们证明了Lee给出的界限是紧的，并且提出了一个改进的启发式算法。Kubiak，Blazewicz，Formanowicz和 Schmidt 在2002年提出了在两机恢复期（r）一些预防性维修阶段的问题。他们表明最小化最大完工时间也是强意义上的NP-hard问题。同时，他们通过研究概括了最优解的一些特有性质，并且为此提出了一种分支定界法的解决方案。Blazewicz， Breit，Formanowicz， Kubiak和 Schmidt 在2001年也研究了相同的问题。他们分析了基于构建方法和局部搜索的启发式算法。Lee 在1991年阐明关于考虑预防性约束的最小化最大完工时间的问题,这也是一个是强意义上的NP-hard问题。Lee对于至多有一个预防性周期的问题进行研究，发现这个预防周期出现在计划周期的开始阶段。

Glazebrook 在1984年研究了单一机器故障问题，并且制定了有折扣的马尔可夫链的判定过程。Birge， Frenk， Mittenhall 和 Rinnooy Kan 在1990年基于前者的研究进行了普遍性细分过程的研究。Allahverdi 和 Mittenhal 在1994年表明通过改变处理时间，随机故障的并行机问题可以被转换为一个等效的确定性的并行机问题。当然，这个问题遵循了一个广义的泊松过程，它以尽量减少预期平均流量时间和故障为基准。Mittenthall 和Ragavachari在1993年研究的问题是，当一台机器的处理时间是确定的情况下，机器的随机故障是否遵循泊松过程。

4 启发式算法

在HFS调度著作中，启发式算法和分支定界法是大多被采用两种方法。当我们面对强意义上的NP-hard问题的时候，最佳的解决方案是在不合理的时间用准确的方法，比如在本文中，通过牺牲最优解来保证能够更加有效地计算出来合理的解决方案。当然，我们要用尽可能少的优化方案获得尽可能高的效率。这些启发式算法通过简化成一个不需要维护约束的算法来调度混合流水车间。这些依赖于该问题的具体知识，同时依据问题的特殊性能而得出的启发式算法可分为以下几个种类：（1）定义工件的优先级。（2）转化成更简单的问题，例如双机的问题。（3）使用直接寻找良好的序列等其他方法，比如给定序列，通过邻域搜索的方法进行改进，如仿真模拟退火法和禁忌搜索方法。

在本文中所有的启发式算法适合通过两个连续的步骤解决问题：首先通过考虑一台虚拟机，它减少了混合流水车间过程，使其变得更加常规化。这等于说一个工件i在阶段k中的机器j

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[151920]，资料为PDF文档或Word文档，PDF文档可免费转换为Word