Classfication of Flow-Shop Scheduling Problems(流水车间调度问题的分类)

可以按场景、约束、目标函数对流水车间调度问题分类

目录

一、按场景分类

各场景FSP论文分布情况：

二、按约束分类

不同约束FSP论文分布情况：

三、按目标函数分类

不同目标函数FSP论文分布情况：

一、按场景分类

1) Permutation FSP (PFSP):

考虑在每台机器上要求相同的作业处理序列的排列限制[75]。PFSPs可以看作是FSPs中最简单的一类.

2)Non-Permutation FSP ( ¯PFSP):

没有排列限制 ,作业可以在机器上以不同的顺序[53]处理。很明显，¯PFSP比PFSP要困难得多.

3)No-W ait FSP ( ¯W F S P ) :

调度没有等待,一旦无等待作业的处理操作在第一台机器上启动，在任何连续的两台机器之间必须没有等待时间，直到最后一台机器[56]处理它。

4)Mixed No-W ait FSP (M ¯W F S P ) :

一些作业是无需等待的，而其他作业是常规作业[50].

5) No-Idle FSP ( ¯IF S P ) :

在无空闲机器上调度作业，从第一个作业开始到最后一个作业完成，每个机器必须在不中断的情况下处理作业[67]。

6)Mixed No-Idle FSP (M ¯IF S P ) :

同时考虑无空闲机器和常规机器

7) Blocking FSP (BFSP):

没有阻塞意味着每台机器都有一个无限容量的缓冲区，如果被处理的作业的下游机器不可用，则可以将其临时存储在缓冲区中。

但是，考虑到阻塞属性，BFSP中没有缓冲区，因此作业必须在处理之后阻塞一台机器，直到它的下游机器[4]开始处理它。

8）Assembly FSP (AFSP):

考虑生产和装配多个阶段

9）Hybrid FSP (HFSP):

HFSP通过将单台机器替换为包含一台或多台并行机器[45]的生产阶段来扩展基本FSP。至少有一个阶段包含并行机器。因此，需要考虑一个平行机分配问题。人们也称HFSP为灵活的FSP

10）Re-entrant HFSP (RHFSP):

作业多次重新进入一个阶段，但其生产路线在调度[45]之前就已经知道。

11）Distributed FSP (DFSP):

分布式DFSP，不同于以上fsp在单个流水线上调度作业，研究者研究的调度问题具有分布式性质，即多个流水线存在于一个工厂[16]或不同工厂[32]中。

各场景FSP论文分布情况：

二、按约束分类

1）due time

到期时间指的是作业的预期完成时间

2） Release Time:

作业在第一台机器上可以处理的最早时间，即作业释放时间[109]，或者机器可以处理作业的最早时间，即机器释放时间[38]，[118]。

3）Setup Time:

当一台机器上两个连续的作业需要不同的机器状态时，需要时间来切换机器状态，满足它们的生产需求[9]。

4）Time Lag：

恒定作业延时是指在两台机器([38]，[118]，[130])上处理两个连续操作之间的最短时间。时滞窗限制的是作业中两个连续操作之间的最小和最大时间间隔[80]。

5）Multiprocessor Tasks:

平行机调度

6）Heterogeneous Processors:

异构平行机，eg：只有某些机器有资格处理某个作业

7）Limited Buffers:

缓冲区大小是有限的

8）Uncertain Processing Time:

作业处理时间可变不固定

9）Dynamic Events:

考虑了动态事件的影响，如机器故障[49]，[94]，[95]，[108]，新的作业到达[94]，[95]，[108]，作业取消[94]，延迟的作业可用性[94]，[108]，动态传输等待时间[42]。

不同约束FSP论文分布情况：

三、按目标函数分类

1）Makespan:

最小化最大完工时间，最后一个作业的完成时间[75]，超过70%(137篇评论文章中的96篇)认为它是一个目标函数。

2） Total Weighted Completion Time:

加权总完工时间，加权求和所有作业[45]的完成时间。

3）Total Flow Time:

所有作业流动时间的总和，是一个被广泛关注的目标函数，需要使其最小化[89]。注意，如果不考虑作业释放时间，即作业在时间0时可用，那么总流时间等于总完成时间[46]。

4）Total Weighted Tardiness:

最小化总加权延迟，即所有工作延迟完成的加权总和，是 FSP [91] 通常考虑的目标函数。如果每个工作的加权系数相同且等于 1，则目标函数可以称为总延迟 [71]。

5）Total Weighted Earliness and Tardiness:

最小化总加权延迟和早到，所有工作的提前和迟到的线性组合被计算并最小化为目标函数值

6）Total Energy Consumption:

最小化总能耗

7）System Stability and/or Robustness:

系统稳定性或稳健性，稳定性可以通过机器分配 [49]、工作开始时间 [49]、[94]、工作完成时间 [95] 和系统参与者的不满 [108] 方面的新计划和基线计划之间的差异来衡量.稳健性可以通过预期的总流动时间[108]和新的和基线计划之间的总完成时间偏差来表示[95]。

8）Others:

将现有论文中出现频率较低的目标放入名为“Others”的类中。eg：最大迟到的最小化 [62]、平均逗留时间 [49]、投休惩罚 [49]、总碳排放 [96]、总成本 [17] 和总收益的最大化 [109]。

不同目标函数FSP论文分布情况：

 参考文献：[1] lterated Greedy Algorithms for Flow-Shop Scheduling Problems: ATutorial