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

摘要

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