流水线调度

流水线调度是计算机科学和运筹学中的一个优化问题。它是最佳作业调度的一种变体。在一般的作业调度问题中，给定n个作业J1、J2、...、Jn，它们的处理时间各不相同，需要在具有不同处理能力的m台机器上进行调度，同时尽量减少制造时间——总长度计划的时间（即，当所有作业都完成处理时）。在称为流水车间调度的特定变体中，每个作业恰好包含m个操作。作业的第i次操作必须在第i台机器上执行。没有一台机器可以同时执行多个操作。对于每个作业的每个操作，都指定了执行时间。流水车间调度是作业车间调度的一种特殊情况，其中对所有作业执行的所有操作都有严格的顺序。流水线调度也可以应用于生产设施和计算设计。一种特殊类型的流水车间调度问题是置换流水车间调度问题，其中作业在资源上的处理顺序对于每个后续处理步骤都是相同的。在最优作业调度问题的标准三字段表示法中，流水车间变体在xxx个字段中用F表示。例如，F3|表示的问题p我j{displaystylep_{ij}}|Cxxx限度{displaystyleC_{max}}是一个具有单位处理时间的3机器流水车间问题，其目标是最小化xxx完成时间。

有n台机器和m个工作。每个作业恰好包含m个操作。作业的第i次操作必须在第i台机器上执行。没有一台机器可以同时执行多个操作。对于每个作业的每个操作，都指定了执行时间。一项作业中的操作必须按指定的顺序执行。xxx个操作在xxx台机器上执行，然后（当xxx个操作完成时）第二个操作在第二台机器上执行，依此类推，直到第n次操作。但是，作业可以按任何顺序执行。问题定义意味着每台机器的作业顺序完全相同。问题是确定最佳的这种安排，即总作业执行时间最短的安排。

测序问题可以描述为确定一个序列S，以便优化一个或几个测序目标。

• （平均）流动时间，∑(w一世)F一世{displaystylesum(w_{i})F_{i}}
• 制造跨度，Cmax
• （平均）迟到，∑(w一世)吨一世{displaystylesum(w_{i})T_{i}}
• ……

Malakooti(2013)中可以找到有关性能测量的详细讨论。

正如Garey等人提出的。(1976)，流水车间调度问题的大多数扩展都是NP难的，很少有可以在O(nlogn)中最优解的；例如，F2|prmu|Cmax可以通过使用约翰逊法则得到最优解。Taillard为调度流水车间、开放车间和作业车间提供了大量的基准问题。

提出的解决流水车间调度问题的方法可以分为精确算法如分支定界和启发式算法如遗传算法。

F2|prmu|Cmax和F3|prmu|Cmax可以通过使用约翰逊规则得到最优解，但对于一般情况，没有算法可以保证解的最优性。

流水车间包含n个在时间0时同时可用的作业，并由两台串联排列的机器处理，它们之间有无限的存储空间。所有工作的处理时间都是确定的。需要在机器上安排n个作业以最小化制造时间。下面给出了两机流水车间作业调度的约翰逊规则。在最优调度中，如果min{p1i,p2j}<min{p1j,p2i}，则作业i在作业j之前。其中，p1i是作业i在机器1上的处理时间，p2i是作业i在机器2上的处理时间。类似地，p1j和p2j分别是作业j在机器1和机器2上的处理时间。对于约翰逊算法：设p1j为作业j在机器1上的处理时间，p2j为作业j在机器2上的处理时间约翰逊算法：

• 表格set1包含所有p1j<p2j的作业
• 表格set2包含所有p1j>p2j的作业，p1j=p2j的作业可以放在任一集中。
• 形成如下序列：(i)set1中的作业按顺序排在最前面，它们按p1j(SPT)的升序排列(ii)set2中的作业按p2j(LPT)的降序排列。关系被任意打破。

这种类型的调度被称为SPT(1)-LPT(2)调度。Malakooti(2013)提供了对可用解决方法的详细讨论。