1.2　排序问题的三参数表示

排序问题种类繁多，用简单明了的记号将一个所研究的排序问题表示出来，有利于在排序理论研究过程中规范表达一个排序问题并理解该问题，有利于从事排序理论研究的专家学者进行交流，有利于排序理论的推广、传播与应用。

将一个需要研究的问题抽象为一个排序问题，其中有需要被加工的若干“工件”，以及加工这些工件的一台或若干台“机器”，一个工件若被安排在某台机器上加工，则有一已知的加工时间，我们所做的决策就是安排加工这些工件使所考虑的“优化目标”达到最优。因此，排序问题一般涉及“工件”“机器”与“优化目标”。目前国际上通常用三参数α ｜ β ｜ γ 来表示一个排序问题，其中，参数α表示“机器环境”，参数 β表示“工件特征”，参数 γ 表示“优化目标”。

对于“机器环境”的参数，首先有单台机器排序问题与多台机器排序问题的区分，用1表示单台机器排序问题。对于多台机器排序问题，机器可分为通用平行机与专用串联机这两大类：对于平行机问题，P表示同型机问题，Q表示同类机问题，R表示非同类机问题；对于串联机问题，O表示自由作业问题，F表示流水作业问题，J表示异序作业问题。对于多台机器排序问题，用m表示机器的台数，例如F2表示2台机器的流水作业问题，P2与Pm分别表示2台机器的同型机问题与m台机器的同型机问题。如果不出现机器台数m，则表示该多台机器排序问题所得到的研究成果或算法对任意台数机器都适用，例如R就是表示任意台数机器的非同类机问题。

对于“工件特征”的参数，由于排序理论的应用领域越来越广泛，所以工件特征的描述也丰富起来。包括表示工件是否在线（on-line、on-line-list、on-line-list-nclv），工件是否具有不同的就绪时间（rj），工件是否具有共同交货期（dj＝d），工件加工是否可以中断（pmtn），工件加工是否具有前后约束关系（prec、tree、intree、outtree、chain），工件加工时间是否相等（pj＝p，pi j＝p），等等，这些都是经典排序问题中所出现的。现代排序模型的发展，势必增加工件特征的描述（唐国春等，2003），例如工件加工时间可控排序（cpt）、工件可拒绝排序（rej）、成组分批排序（GT）、同时加工排序（s-batch、p-batch）、准时排序和窗时排序（JIT）、资源受限排序（res）、工件可转包排序（subcontract）等，随着排序理论的进一步发展，将会出现更多工件特征的描述。

对于“优化目标”的参数，经典排序中优化目标函数一般是工件完工时间（C1，C2，…，Cn）的正则函数，即当优化目标是最小化时，目标函数f（C1，C2，…，Cn）关于各个变量都是非降函数，经典排序中目标函数分为最大费用问题与总费用问题两大类。

（1） 最大费用问题。包括：

最大完工时间Cmax＝max｛Cj｜j＝1，2，…，n｝；

最大延迟Lmax＝max｛Lj｜j＝1，2，…，n｝；

最大延误Tmax＝max｛Tj｜j＝1，2，…，n｝。

（2） 总费用问题。包括：

总完工时间∑Cj，带权总完工时间∑wjCj；

总延误∑Tj，带权总延误∑wjTj；

总误工工件数∑Uj，带权总误工工件数∑wjUj。

对于现代排序模型，优化目标中会增加一些其他费用，例如工件加工时间可控问题，当工件加工时间压缩时，产生工件加工时间的压缩费用；工件可拒绝排序问题，当一个工件被拒绝加工时，则产生一个惩罚费用；工件可外包排序问题，当一个工件外包时，则产生一个外包费用。

三参数表示法一般情况下可以比较清晰地将一个排序问题表达清楚，但并不能将我们所讨论的问题都表示出来，有时需要给出一个必要的阐述与解释，同时，新的排序问题会不断被提出来，参数会更加多种多样。