聂 玲， 程 涛

(1.郑州大学 数学系 河南 郑州 450001; 2.河南工业大学 理学院 河南 郑州 450001)

0 引 言

排序问题是一类重要的组合最优化问题, 它广泛应用于管理科学、计算机科学、工农业生产和交通运输等许多领域, 一直受到国内外学术界的重视.

在经典排序问题中,总是要求每个工件必须被加工,并且其加工时间是预先给定不变的.然而,在现实生活中, 由于某些外在的因素,需要拒绝加工某些工件才能满足限定条件,这就是可拒绝排序[1-5].当然,拒绝加工一个工件需要付出一定的代价,称之为拒绝费用.本文的研究工作就是设计一种策略或算法,在原始的某个和时间有关的目标函数(最大完工时间、总完工时间、最大提前时间等) 与拒绝费用之间达到一种协调,以取得某种意义下的最优.

1 问题1|nmit|Emax

定理1对于排序问题1|nmit|Emax,STST规则得到的是最优排序.

由定理1可知,按照STST规则所得的排序是最优的,并且它的运行时间为O(n2logn).

2 问题

对于排序问题1nmitEmax,已经证明存在一个最优排序，使得工件按照STST规则在机器上加工.因此,有引理1.

定义1设σ为性能指标为f和g的双指标排序问题的一个可行排序,若不存在可行排序π使得f(π)

定义2由所有Pareto最优点构成的点集所生成的凸包的下沿界称为有效边界；有效边界上的点称为极点；极点对应的排序称为极序.

一般地,只要确定有效边界,则可求出目标函数αf+βg(α和β给定)的最小值.而此时,有效边界为分段线性的凸函数,其中每一个折点对应某一个Pareto最优点……