闫力君, 赵玉芳

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)



极小化加权总完工时间的可拒绝单机排序问题

闫力君, 赵玉芳

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)

在经典的排序问题中,工件的加工时间是固定不变的。然而,在实际生产中,工件的实际加工时间会发生变化。同时,机器通常需要进行保养,或发生故障时进行维修等原因,导致机器在某一时间段内无法工作,即机器的不可用区间。研究带有到达时间、退化效应和拒绝工件,及机器带有不可用区间的单机排序问题。在这一模型中,工件的开始加工时间越晚,其实际加工时间越大,实际加工时间是与其开始加工时间有关的函数。该问题中工件允许被拒绝。如果工件被拒绝,那么需要支付拒绝惩罚。讨论的目标函数是接受工件的加权总完工时间与所有拒绝工件的拒绝惩罚之和。首先说明该问题是一般意义NP-难的,进而利用划分程序的方法给出了一个全多项式近似方案,最后分析了该近似方案的时间复杂性。

拒绝惩罚; 退化效应; 全多项式近似方案; 不可用区间

在经典的排序问题中,工件的实际加工时间是一个固定参数。但是,在实际生产中,工件的实际加工时间不一定是固定的。文献[1-4]研究了带有退化效应模型的单机排序问题,其中工件的实际加工时间与其开始加工时间有关。分别研究了最大完工时间、总完工时间、加权总完工时间等问题。文献[5-6]研究了工件允许被拒绝的排序问题,分别研究了最大完工时间、加权总完工时间问题。……