在传统的排序问题中,工件的加工时间是一个确定的常数.然而,在实际生活中,由于作业的某些特性,工件的加工时间在工件等待加工的过程中可能会发生退化.比如,大火在等待扑灭的过程中,火势会逐渐变大,被扑灭所需的时间就会变长.诸如此类的例子,在医疗、金融管理、钢铁制造、资源分配和国防等中都可以找到.因此,无论是在理论和实际应用中,带退化的排序问题都具有重要的意义和价值.因此,带退化的排序问题逐渐得到国内外研究者的广泛关注和深入研究.本文所研究的是单机上带退化的时间在线排序问题,即工件随着时间的推进依次到达,且在工件到达之前,排序者对将来的信息一无所知.此外,对任意一个工件Jj,它的加工时间pj是其开工时间Sj的简单线性函数,即pj=bjSj,这里b>0是工件Jj的退化率.全文共分为五章,主要对简单线性退化工件在单机上的带拒绝在线排序和DSGR算法进行了研究.第一章首先对排序问题进行了简单的介绍,然后依次对在线排序问题、退化工件的排序问题以及带拒绝的排序问题的发展概况进行了简述.第二章对文章所涉及的一些基础定义,如竞争比、下界、三参数表示法等,以及关于DSGR算法和SRDR算法一些结论进行了详细地阐述.第三章考虑了简单线性退化工件的带拒绝在线排序问题,即每个工件都具有拒绝惩罚ej,且服从AGREEABLE条件,即对任意的两个工件Ji和Jj,如果bi