考虑生产线可用性约束的专用并行流水车间调度

《Computers & Industrial Engineering》：Dedicated parallel flow shop scheduling with line availability constraints

　　

摘要

本研究提出了一类新的调度问题，涉及 F 个相同的流水车间，每个车间拥有一条包含 S 个工序阶段的生产线。共有 N 个作业，被划分为 F 个互不相交的作业集合，每个作业集合必须由其专属的流水车间在所有阶段以排列顺序进行处理。然而，由于机器故障、工人缺勤或预防性维护活动等原因，一个或多个流水车间可能会处于不可用状态。因此，不可用流水车间的作业必须由其两个相邻流水车间之一处理。我们在两种情形下研究该问题：（1）不可用的流水车间事先未知，但可用流水车间的总数已知；（2）不可用的流水车间事先已知。该问题的目标是确定每个不可用流水车间的作业分配到其某个相邻流水车间的方案，以及每个可用流水车间内的作业顺序，以最小化所有作业集合的完工跨度（makespan）。我们证明了两种情形都是强 NP 难问题。我们建立了混合整数线性规划（MILP）模型以最优求解这两种情形。此外，我们还提出了一种局部搜索算法来求解第一种情形。计算实验表明，所提出的模型和启发式算法具有卓越的性能。

引言

S 阶段并行流水车间是一种制造环境，包含 F 个流水车间，每个车间拥有一条由 S 个工序阶段组成的生产线，并行运行。每个阶段仅有一台机器，且所有流水车间中同一阶段的机器都是相同的。共有 N 个作业需要由其中一个能够处理所有作业的流水车间进行加工。每个被分配到某个流水车间的作业首先由第一阶段机器加工，然后由第二阶段机器加工，依此类推。一旦作业被分配到某个流水车间，它将在那里完成其所有操作。流水车间中的每台机器一次最多只能加工一个作业。此外，一旦作业在某台机器上开始加工，便不能被中断，必须持续进行直至加工完成。当一个作业在某阶段机器上加工完毕，但下一阶段机器因仍在处理前一作业而尚未可用时，该作业将在下一阶段的中间缓冲区等待。在这种加工环境中，希望确定将作业分配到流水车间的最优方案，以及每个流水车间内的最优作业顺序，以最小化调度准则。

并行流水车间在各行业中都很常见，包括玻璃制造（He 等，1996）、电气云计算（Wu 等，2017）和柔性制造系统（Vairaktarakis 和 Elhafsi，2000）。自 Naderi 和 Ruiz（2010）的开创性研究以来，并行流水车间调度问题被重新发现并重新命名为分布式流水车间调度问题。当某个流水车间需要处理的所有作业必须以相同顺序访问该流水车间的所有阶段时，该问题被称为分布式流水车间调度问题；即在所有流水车间中均使用排列顺序（Perez-Gonzalez & Framinan，2024）。

在某些制造环境中，使用专用或专用机器以高速生产产品，材料流动顺畅、逻辑清晰。上述 S 阶段并行流水车间调度问题的一个特殊情况是：作业是划分为 F 种不同类型产品（J1、J2、…、JF）的产品，这些产品属于同一产品的变体，且每个流水车间专门处理一种产品类型。因此，该问题被称为 S 阶段专用并行流水车间调度问题。当 S=2 时，通过对每个流水车间应用 Johnson 的 O(nlogn) 时间算法（Johnson，1954），可在多项式时间内求解以最小化所有作业的最大完工时间（makespan）；但当 S≥3 时，该问题变为强 NP 难问题。S 阶段专用并行流水车间调度问题的另一种特殊情况是：每个作业仅限于在同阶段的专用机器上加工。例如，一个两阶段流水车间在阶段 1 可能有两台并行的专用机器，在阶段 2 有一台共用的机器。在阶段 1，类型为 1 的作业由第一台专用机器加工，类型为 2 的作业由第二台专用机器加工；所有类型作业的第二道操作由阶段 2 的单台共用机器完成（Hajji 等，2023）。

专用流水车间在一些行业中可见，例如化学和制药行业以及大规模定制的标签贴标制造，在这些行业中，原材料从一端投入，成品在另一端连续产出（Lin 和 Liao，2003）。另一方面，S 阶段柔性（混合）流水车间是另一种制造环境，包含一个具有 S 个阶段的流水车间，其中至少有一个阶段拥有多台相同、统一或不相关的机器。共有 N 个作业遵循相同的阶段序列，在每个有多台机器的阶段，每个作业可由任意机器加工（Tosun 等，2020）。因此，专用流水车间可视为柔性流水车间的特殊情况。并行（分布式）流水车间与柔性流水车间密切相关，有时被认为是柔性流水车间的一种特殊情形。如果每个作业在每个阶段仅限于由相同编号的机器加工（即所有阶段具有相同的机器索引），则每个阶段的第 i 台机器构成第 i 个流水车间，即第 1 个阶段的第 1 台机器、第 2 个阶段的第 1 台机器等构成第 1 个流水车间，第 2 台机器依次构成第 2 个流水车间，依此类推。这意味着存在独立的流水车间，且作业被分配到这些流水车间中。因此，柔性流水车间调度问题就转化为并行（分布式）流水车间调度问题。

上述调度问题以及调度文献中的大多数其他研究都假设所有流水车间始终可用。然而，由于工人缺勤、机器故障后的纠正性维护或计划性的预防维护活动等原因，某个流水车间中的一台或多台机器可能会不可用（Ma 等，2010）。在某些情况下，整个流水车间也可能被封锁而不可用，因此在一个生产期内实际可用的流水车间总数可能少于 F。因此，某一流水车间的作业需要由该不可用流水车间的相邻流水车间之一加工。也就是说，一个流水车间通常用于同时加工两个相邻流水车间的作业。例如，第 3 个流水车间的作业应由第 2 个或第 4 个（与其相邻的）流水车间加工。我们将此问题称为带产线可用性约束的 S 阶段专用并行流水车间调度问题，这也是本研究的研究对象。当不可用流水车间的数量或不可用流水车间本身事先已知时，需要确定将被共用使用的流水车间（即每个不可用流水车间的作业被最优地分配到相邻的可用共用流水车间的方案），以及每个可用流水车间内的最优作业顺序。

在比较分布式排列流水车间调度问题与带产线可用性约束的专用并行流水车间调度问题时，我们观察到两者的相似之处和不同之处。在这两个问题中，制造环境是相同的：存在并行流水车间，且由某个流水车间处理的所有作业必须以相同顺序访问所有阶段；即使用排列顺序。然而，在某些方面，我们所研究的问题与分布式排列流水车间调度问题有所不同。在分布式排列流水车间调度问题中，需要确定作业到流水车间的最优分配，以及每个流水车间内的最优作业加工顺序。但在我们的问题中，作业已经被分配（专属）到流水车间，但一个或多个流水车间不可用。换言之，F 分布式排列流水车间调度问题已经求解完毕，但无法实施。在我们的问题中，解决方案提供了将被共用使用的流水车间（即每个不可用流水车间的作业被最优地分配到相邻的共用流水车间的方案），以及每个可用流水车间内的最优作业加工顺序。

本研究涉及的问题源于我们在一家金属加工企业观察到的实际问题。在该企业中，焊接操作在并行生产线上进行。待焊接的零件通过铁轨上移动的车架从仓库转移到焊接生产线。车架沿铁轨从一个生产阶段转移到另一个阶段。到达生产线任一阶段的车架会暂时通过其上的装置被固定在地面上，焊接操作完成后，固定装置释放，车架被转移到下一阶段。在每个阶段，由工人对车架执行各种焊接操作。如果焊接生产线上任一阶段的工人因故缺勤，则无法在该生产线上执行任何操作，即该生产线变得不可用。如果生产线不可用，原本要在其上焊接的零件会从零件仓库直接发送到相邻（邻近）的生产线之一，或者通过不可用生产线入口处的铁轨岔道（类似于火车轨道上的道岔）进行转移。在每天早上，需要根据不可用生产线的情况迅速修订流水线的调度计划。这种情形正是我们研究的目的所在。

据我们所知，带产线可用性约束的专用并行流水车间调度问题此前尚未被研究过。在本研究中，我们在两种情形下调查该问题。第一种情形是不可用流水车间的数量已知，这种情形通常由工人缺勤引起。第二种情形是不可用流水车间本身已知，这种情形由机器故障或预防性维护活动引起。

本文研究的问题是一个新问题，处于几类调度问题的交汇之处。最相关的工作涉及并行（分布式）流水车间调度、带专用机器的流水车间调度以及带可用性约束的流水车间调度。本节简要回顾相关研究，并将我们所研究的问题在文献中定位。

并行流水车间调度的文献较为稀少。关于并行流水车间调度的最早研究来自 He 等（1996）。他们建立了混合整数规划模型，并为 F 并行两阶段流水车间调度问题提出了一种高效的启发式算法，以最小化作业的最大完工时间（makespan）。最优调度是一种排列调度，其中作业在流水车间中的所有机器上以相同顺序加工。Cao 和 Chen（2003）研究了相同的问题，提出了数学模型和禁忌搜索算法。Sundararaghavan 等（1997）研究了 F 个并行两阶段比例流水车间的完工跨度最小化问题，其中第一流水车间的机器比第二流水车间慢。他们提出了混合整数规划模型和启发式算法。Al-Salem（2004）也研究了相同问题，并提出了多阶段算法。Vairaktarakis 和 Elhafsi（2000）研究了两个并行两阶段流水车间调度问题，提出了动态规划算法以提供最优解。Zhang 和 van de Velde（2012）研究了具有两个阶段的两并行和三并行流水车间的完工跨度最小化问题。他们的研究提出了近似算法，对于两并行和三并行流水车间，其最坏情况性能保证分别为 3/2 和 12/7。Rajendran 等（2015）将 Sundararaghavan 等（1997）的研究扩展到 F 个并行 S 阶段比例流水车间。

他们开发了一种遗传算法来最小化最大完工时间。Tong等人（2018）针对并行S阶段流水作业调度问题提出了一种多项式时间近似方案（PTAS）。Mansouri等人（2023）研究了同一问题，并提出了一种结合粒子群优化和禁忌搜索优势的混合算法。Ribas和Companys（2021）考虑了机器间无中间存储且存在与顺序相关的准备时间的并行S阶段流水作业调度问题，以最小化最大完工时间。在这种制造环境中，一台机器上完成的作业无法移至中间存储，并且会阻塞同一台机器上待加工的后一个作业，即允许机器阻塞。他们开发了36种构造性启发式算法并测试了其性能，从而提出了一种高效算法。Ribas等人（2021）研究了具有阻塞约束和与顺序相关的准备时间的并行S阶段流水作业调度问题以最小化最大完工时间。他们提出了一种迭代贪心算法，并通过与其他方法的比较证明了其有效性。Kusuma和Albana（2021）研究了并行S阶段流水作业调度问题，在保持可接受的最大完工时间的同时最小化中间存储量。他们开发了一种两步进化算法，并将其与非支配排序遗传算法、改进的高效遗传算法、基于云理论的模拟退火算法和人工蜂群算法进行了比较。

另一方面，分布式流水作业调度问题——如前所述，已被重新命名为分布式流水作业调度问题——近年来受到了相当大的关注，尤其是在过去二十年中。在文献中，尽管已有相当数量的研究针对分布式流水作业调度问题，但不幸的是，我们无法在此处全部涵盖。关于分布式流水作业调度问题的文献综述，读者可参阅Fu等人（2021）、Bagheri Rad和Behnamian（2022）、Duan等人（2023）以及Perez-Gonzalez和Framinan（2024）。

并行两阶段流水作业调度问题的一个特例是存在两个两阶段流水车间，且第一阶段有一台公共机器的情况。这个特例是柔性（混合）流水作业调度问题，最早由Rao（1970）研究，目前已提出了多种启发式算法来最小化最大完工时间。Yang（2010）证明了两阶段柔性流水车间的最大完工时间最小化问题是NP完全问题。Gupta和Tun?（1991）也研究了同一问题并提出了若干高效启发式算法。这个特例的对称问题是存在两个两阶段流水车间，且第二阶段有一台公共机器的情况（即两个流水车间的第二阶段机器中只有一台可用）。该问题最早由Arthanary和Ramaswamy（1971）研究。他们开发了一种分支定界算法以最优求解此特例，Gupta（1988）为其开发了一种启发式算法。O?uz等人（1997）考虑了第二种情况下的问题，并证明其至少和NP完全问题一样困难。在文献中，上述两阶段并行流水作业调度问题的特例被称为具有公共机器的两阶段柔性流水作业调度。关于研究这两种特例及其扩展的若干研究，可参阅Hwang和Lin（2018）的综述论文。Tosun等人（2020）更新的综述论文提供了关于柔性流水车间调度研究的全面综述。该文献进行了分类，并强调了各种求解方法，包括精确算法、启发式算法和元启发式算法。该综述论文识别了研究趋势和空白，以指导柔性流水车间调度的未来研究。

在文献中，关于带有可用性感知的流水作业调度研究有两类：（1）考虑确定性不可用时间区间的研究，这些区间是已知且确定的，由工人缺勤和为预防机器故障所需的预防性维护活动引起；（2）考虑随机不可用时间区间的研究，这些区间事先未知，由机器故障后进行的纠正性维护活动引起。在我们简要的综述中，我们不会详细讨论随机不可用时间区间的相关研究，因为我们的问题是确定性的。然而，感兴趣的读者可参阅Adressi等人（2016）、Seif等人（2020）、Hnaien和Arbaoui（2023）的研究，以及关于机器故障流水作业调度的最新综述论文Gonzalez-Neira等人（2017）。

在确定性不可用时间区间的流水作业调度研究中，考虑了机器上的三种不可用时间区间：（1）固定不可用时间区间，其开始和结束时间是预先确定的；（2）最大长度不可用时间区间，不可用时间区间的开始时间不固定，但每次不可用时间区间之间的时间不能超过某一特定时期；（3）柔性不可用时间区间（带时间窗的不可用时间区间），不可用时间区间的开始和结束时间在时间窗内进行调度。在这些研究中，考虑了三种类型的作业特征。第一种类型中，如果一个作业在下一个不可用时间区间开始前无法完成，但可在不可用时间区间后继续加工剩余部分，则称该作业为可恢复作业。第二种类型中，如果一个作业必须在机器的可用区间内完成，即被中断的作业在不可用时间区间后必须完全重新开始加工，则称该作业为不可恢复作业。然而，在第三种类型中，如果一个作业在下一个不可用时间区间开始前无法完成，但可在不可用时间区间后以更长加工时间继续加工剩余部分，则称该作业为半可恢复作业（Perez-Gonzalez和Framinan，2020）。

最早与确定性不可用时间区间相关的研究之一是Lee（1997）。该研究考虑了每个阶段各有一台机器的两阶段流水作业调度问题，以最小化最大完工时间。他证明了该问题是NP完全问题，并为单机单台机器的情况提出了动态规划算法。他还提供了近似算法来确定该区间是位于机器1还是机器2上。该研究加速了对带有可用性感知的调度问题的兴趣。关于1997年至2010年间相关研究的全面综述，读者可参阅Ma等人（2010）。一篇近期的论文是Chen等人（2020），该论文研究了具有两类约束的两台机器流水作业调度问题——作业操作之间不允许等待，且单台机器上不存在固定不可用时间区间。作者专注于最小化最大完工时间，提出了一种混合整数线性规划模型和高效的调度算法。Li和Liu（2020）研究了第一台机器的操作员在某一区间内不可用的两台机器流水作业调度问题。他们证明了最小化最大完工时间的问题是NP难的，并提供了一个紧的3/2-近似算法。在文献中，关于确定性不可用时间区间的大多数研究考虑的是两阶段（机器）问题，而对多阶段问题的关注较少。Aggoune（2004）考虑了由于维护活动每台机器存在多个不可用时间区间时的多阶段问题。研究了两种不可用时间区间：（1）固定不可用时间区间，（2）带时间窗的不可用时间区间。提出了一种基于遗传算法和禁忌搜索的启发式算法来最小化最大完工时间。Jomaa等人（2021）研究了由于预防性维护而存在不可恢复作业和可用性约束的S阶段排列流水作业调度问题。在他们的研究中，考虑了最大长度不可用时间区间的情况。作者提出了两种变邻域搜索算法，通过确定最优作业序列和维护任务的适当时机来最小化最大完工时间。他们还通过不同的问题实例证明了所提算法的有效性。Jomaa等人（2023）研究了与Jomaa等人（2021）相同的问题。他们提出了三个混合整数规划模型，通过确定最优作业序列和维护任务的适当时机来最小化最大完工时间。他们还通过不同的问题实例证明了所提模型的有效性。?z?elik和Sara?（2023）研究了S阶段流水作业调度问题，考虑了不可恢复作业、带时间窗的不可用时间区间以及用于维护任务的单一服务器，以最小化最大完工时间。他们开发了一种MILP模型和一种结合遗传算法和改进的次梯度算法的混合算法。

近年来，越来越多的关注被投入到分布式流水作业调度中的不可用性约束上，但相关研究数量仍然有限。Mao等人（2021）研究了带有预防性维护的分布式排列流水作业调度问题。在考虑不可恢复作业和固定不可用时间区间的条件下，他们引入了一种有效的多起点迭代贪心算法来最小化最大完工时间。所提算法生成高质量初始解，然后通过局部搜索进一步改进。Mao等人（2022）考虑了相同的问题环境以最小化总流程时间。他们的研究提出了一种模因算法，利用哈希映射在搜索过程中高效存储和检索解。Yan等人（2022）提出了一种深度强化学习方法来解决具有柔性维护活动的分布式流水作业调度问题。其目标是通过优化所有流水车间中的作业分配和排序以及维护活动的时机来最小化最大完工时间。他们的实验表明，所提方法优于传统启发式算法和其他基于学习的方法。Miyata和Nagano（2021）考虑了具有与顺序相关的准备时间和维护活动的分布式无等待流水作业调度问题。在假设作业不可恢复且维护任务持续时间取决于维护级别和顺序的条件下，他们开发了一种MILP模型和一种具有可变搜索邻域的迭代贪心算法来最小化最大完工时间。Han等人（2024）提出了一种新的迭代贪心算法来解决具有最大长度不可用时间区间的分布式流水作业调度问题。他们的算法使用多交换策略和协同搜索来最小化最大完工时间。计算实验表明，其算法非常高效且性能优于现有方法。Sun、Sang、Meng等人（2025）研究了具有预防性维护和与顺序相关的准备时间的分布式排列流水作业调度问题以最小化总流程时间。在考虑不可恢复作业和固定不可用时间区间的条件下，他们提出了一种MILP模型和一种高效的能平衡搜索空间探索与开发的多元起点离散灰狼优化算法。他们的实验结果表明，所提算法在解决该问题上非常有效。Sun、Sang、Yuan等人（2025）考虑了与Sun、Sang、Meng等人（2025）相同的问题，并将其扩展到了具有阻塞约束的环境中。作者提出了一种由Q学习和学习机制协同驱动的元启发式算法。该方法与离散灰狼优化算法相结合。

在文献中，关于具有可用性感知的柔性（混合）流水作业调度问题的研究仍缺乏。Allaoui和Artiba（2006）研究了二阶段问题，每台机器因维护最多有一个不可用时间区间。第一阶段有一台机器，第二阶段有多台并行机器。他们考虑了不可恢复作业和固定不可用时间区间，开发了一种分支定界算法来解决该问题并最小化最大完工时间。Besbes等人（2010）考虑了每台机器因维护最多有一个不可用时间区间的S阶段问题。他们假设作业不可恢复，并针对两种情况研究了该问题：（1）固定不可用时间区间，（2）带时间窗的不可用时间区间。提出了一种遗传算法，并通过计算实验展示了其有效性。Allaoui和Artiba（2014）研究了以最小化最大完工时间为目标的两阶段问题，并针对两个特例研究了精确求解方法。此外，他们为两机器流水作业问题制定了动态规划算法，并为两阶段混合流水车间开发了分支定界算法。

我们的研究对文献的贡献：（1）据我们所知，具有产线可用性约束的专用并行流水车间调度问题尚未被研究过。

因此，我们希望本工作能为未来的研究开辟新的途径，其中一些研究方向将在第6节中提到。（2）我们针对与生产线可用性类型相关的两种情况研究了所研究的问题。第一种情况是，不可用的流水车间事先未知，但可用的流水车间总数已知。然而，在第二种情况中，不可用的流水车间是事先已知的。（3）我们证明了这两种情况都是强NP难问题。然而，我们证明了当有且仅有一条不可用的流水车间且所有流水车间均有两个阶段时，本文所研究的第一问题（第一种情况）可在多项式时间内最优求解。我们还证明了当所有流水车间均有两个阶段时，第二问题也可在多项式时间内最优求解。（4）我们建立了混合整数规划（MILP）模型，该模型可以最优求解两个问题。（5）针对问题的第一种情况（所有流水车间均有两个阶段），我们提出了一种启发式算法，能够为小规模和中规模问题实例提供最优解，为大规模问题实例提供近似最优解。本文其余部分的组织如下。第2节描述了所研究的问题，并证明了两个被称为问题1和问题2的情况均为强NP难问题。同时，还为问题1和问题2的一些特殊情况提供了多项式时间可求解的算法以找到最优调度。为了最优求解两个问题，第3节提出了混合整数线性规划（MILP）模型。第4节提出了一种启发式算法，用于解决可用的流水车间数量事先已知且每条流水车间有两个阶段的问题。第5节提供了我们的实验研究，以评估MILP模型和启发式算法的性能。第6节提出了我们的结论并提出了一些未来研究机会。章节摘要问题定义与初步结果在本节中，我们首先详细定义了所研究的调度问题。然后，我们给出了一个数值示例来说明该问题。最后，我们分析了所研究问题的复杂度，并提供了多项式时间算法来求解两个特殊情况。数学规划模型在本节中，引入混合整数线性规划（MILP）模型，分别记为MILP-1和MILP-2，用于分别获取问题P1和P2的最优解。这些模型使用基于位置的决策变量来确定每个作业在各可用流水车间中的位置。我们首先定义两个模型中常用的以下参数、指标、集合和决策变量。参数、指标与集合F：流水车间总数；f, g：流水车间指标。当S=2时问题P1的启发式算法在本节中，我们提供了当所有流水车间均有两个阶段（即S=2）时问题P1的启发式算法。我们的启发式算法由两个阶段组成：寻找初始调度方案以及使用局部搜索算法对其进行改进。启发式算法各阶段的详细描述如下。阶段一（初始调度方案生成）。本阶段用于找到作业集合中作业的初始调度方案。我们的启发式算法中阶段一的逐步描述为计算实验本节展示了我们的计算实验，以从解质量和计算时间两个方面评估我们求解方法的性能。MILP模型使用通用代数建模系统（GAMS）24.0.2版本进行求解。用于求解问题P1的启发式算法使用Python语言在Visual Studio Code中编程实现。所有实验均在一台配备Intel(R) Core(TM) i7-6700HQ处理器（运行频率2.60 GHz）和16 GB内存的计算机上完成。结论与未来研究本研究引入了一种新的调度问题：带产线可用性约束的专用并行流水车间调度问题。该问题源自一家拥有并行流水车间的工业企业，其中每个作业集中的所有作业都专属于某一条流水车间。每天开始时，可能会有一个或多个工人缺勤，或者一个或多个阶段上的机器需要进行预防性维护，因此一个或多个流水车间的所有作业都需要由其相邻的流水车间进行加工。CRediT作者贡献声明Ayyuce Aydemir-Karadag：撰写—初稿、可视化、软件、方法学、概念化。Ferda Can ?etinkaya：撰写—初稿、验证、监督、方法学、调查研究、形式化分析、概念化。Merve Polat-Cing?z：方法学、调查研究、数据整理。利益冲突声明作者声明不存在已知的竞争性经济利益或个人关系，这些因素可能会影响本文所报告的研究工作。Ayyuce Aydemir-Karadag是安卡拉盖齐大学工业工程系副教授。她在盖齐大学完成了工业工程博士学位。她的研究兴趣包括供应链管理、物流管理、生产系统建模与优化。她在多个国际期刊上发表了论文，包括《计算机与工业工程》、《清洁生产杂志》和《阿拉伯科学与工程技术杂志》。Ayyuce Aydemir-Karadag | Ferda Can ?etinkaya | Merve Polat-Cing?z土耳其安卡拉恰干亚06570盖齐大学工程学院工业工程系