可以按场景、约束、目标函数对流水车间调度问题分类
目录
一、按场景分类
各场景FSP论文分布情况：
二、按约束分类
不同约束FSP论文分布情况：
三、按目标函数分类
【经验积累|Classfication of Flow-Shop Scheduling Problems(流水车间调度问题的分类)】不同目标函数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
推荐阅读
- 启发式|元启发式如何跳出局部最优（）
- 算法|【整数规划算法】列生成（理论分析+Python代码实现）
- 算法|AAAI2021（面向交通流预测的时空融合图神经网络）
- 算法|图神经网络（01）-图与图学习(上)
- 神经网络|干货！图神经网络及其自监督学习
- 数据结构|数据结构学习笔记（第六章 图）
- C数据结构|C数据结构（哈夫曼树算法实现与应用）
- 数据结构|数据结构（图(Graph)【详解】）
- 数据结构|数据结构（树(Tree)【详解】）