查看“︁流水线调度”︁的源代码

'''流水线调度'''（{{lang-en|Flow-shop scheduling}}）是[[计算机科学]]及[[运筹学]]中的一个[[最佳化問題]]，是最优作业调度的一个变体。在一般的作业调度问题中，我们有从<math>J_1</math>到<math>J_n</math>这n个工作，每项工作都具有不同的完成时间。我们需要做的是最小化[[加工周期]]，也就是完成所有工作所用的时间。而在流水线调度的问题中，每项工作都需要经过m道工序，且第i道工序必须在第i台机器上完成，每台机器在同一时间最多去完成一项任务。

流水线调度是一种特殊的[[作业车间调度]]，所有的工作都必须按照严格的时间顺序进行。该调度模式不仅适用于生产规划，同时也适用于计算设计。排列流水线调度问题是流水线调度问题的一种特殊类型，在排列流水线调度问题中，所有工作在每道工序上的完成顺序是相同的。

在最优作业调度问题的标准三字段表示法中，流水线调度在第一个字段中用'''F'''表示。例如<math>F3|p_{ij}|C_\max</math>用于表示三机流水线调度问题，每项工作在每道工序都有自己的加工时间，目标是最小化使最大完成时间。
==目标函数==
在流水线调度问题中，我们通常会去对所有工序上的工作进行排序，从而对一个或多个目标函数进行优化。通常会用到的目标函数如下：<ref name=Malakooti>Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. {{ISBN|978-1-118-58537-5}}.</ref>
# （平均）流程时间<math>\sum (w_i) F_i </math>
# 加工周期<sub>max</sub>
# （平均）延迟<math>\sum (w_i) T_i </math>
==时间及空间复杂度==
加雷等人<ref name=Garey>Garey, M. R., Johnson, D. S., & Sethi, R. (1976). [https://pubsonline.informs.org/doi/abs/10.1287/moor.1.2.117 The complexity of flowshop and jobshop scheduling].{{closed access}} {{Wayback|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.1.2.117 |date=20220615201755 }} Mathematics of operations research, 1(2), 117–129.</ref>在1976年的研究成果表明，绝大部分的流水线调度问题均属于[[NP困难]]问题，但是也存在少部分流水线调度问题能在<math>O(nlogn)</math>时间里解决,比如说<math>F2|prmu|C_{max}</math>问题就是其中之一，可以通过詹森法则来实现。<ref name=Johnson>Johnson, S. M. (1954). [https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800010110 Optimal two-and three-stage production schedules with setup times included].{{closed access}} {{Wayback|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800010110 |date=20220322100659 }} Naval research logistics quarterly, 1(1), 61–68.</ref>

==参考文献==
{{reflist}}

{{调度问题}}
{{Authority control}}
[[Category:最佳排程]]