排序问题的分类与表示法

2018/1/2 16:35:29

　　排序问题有不同的分类方法。最常用的分类方法是按机器、工件和目标函数的特征分类。按机器的种类和数量不同，可以分成单台机器的排序问题和多台机器的排序问题。对于多台机器的排序问题，按工件加工路线的特征，可以分成单件车间排序问题和流水车间的排序问题。工件的加工路线不同，是单件车间排序问题的基本特征；而所有工件的加工路线完全相同，则是流水车间排序问题的基本特征。

　　按工件到达车间的情况不同，可以分成静态的排序问题和动态的排序问题。当进行排序时，所有工件都已到达，可以一次对它们进行排序，这是静态的排序问题；若工件是陆续到达，要随时安排它们的加工顺序，这事动态的排序问题。

　　按目标函数的性质不同，也可划分不同的排序问题。比如，同是单台机器的排序，目标是使平均流程时间最短和目标是使误期完工的工件数最少，实质上是两种不同的排序问题。按目标函数的情况，还可以划分为单目标的排序问题与多目标的排序问题。以往研究的排序问题，大都属于单目标的排序问题，而对多目标排序问题则很少研究。

　　另外，按参数的性质，可以划分为确定型排序问题与随机型的排序问题。所谓确定型的排序问题，指加工时间和其它有关参数是已知的、确定的量；而随机型排序问题的加工时间和有关参数为随机变量。这两种排序问题的解法本质上不同。

　　由机器、工件和目标函数的不同特征以及其它因素上的差别，构成了多种多样的排序问题。