流水线调度

流水线调度(英語:Flow-shop scheduling)是计算机科学运筹学中的一个最佳化問題,是最优作业调度的一个变体。在一般的作业调度问题中,我们有从这n个工作,每项工作都具有不同的完成时间。我们需要做的是最小化加工周期,也就是完成所有工作所用的时间。而在流水线调度的问题中,每项工作都需要经过m道工序,且第i道工序必须在第i台机器上完成,每台机器在同一时间最多去完成一项任务。

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

在最优作业调度问题的标准三字段表示法中,流水线调度在第一个字段中用F表示。例如用于表示三机流水线调度问题,每项工作在每道工序都有自己的加工时间,目标是最小化使最大完成时间。

目标函数

在流水线调度问题中,我们通常会去对所有工序上的工作进行排序,从而对一个或多个目标函数进行优化。通常会用到的目标函数如下:[1]

  1. (平均)流程时间 
  2. 加工周期max
  3. (平均)延迟 

时间及空间复杂度

加雷等人[2]在1976年的研究成果表明,绝大部分的流水线调度问题均属于NP困难问题,但是也存在少部分流水线调度问题能在 时间里解决,比如说 问题就是其中之一,可以通过詹森法则来实现。[3]

参考文献

  1. ^ Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. ISBN 978-1-118-58537-5.
  2. ^ Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. 页面存档备份,存于互联网档案馆) Mathematics of operations research, 1(2), 117–129.
  3. ^ Johnson, S. M. (1954). Optimal two-and three-stage production schedules with setup times included. 页面存档备份,存于互联网档案馆) Naval research logistics quarterly, 1(1), 61–68.