在现实生产中,加工工件在排序中越晚开始加工,它的实际加工时间就会越大。比如金融管理、钢铁生产、消防、资源分配和国防等等,任何延迟都会导致退化现象的产生。同时,工件在加工之前一般需要预加工的过程,预加工所用的时间就称为释放时间。而且,机器通常需要进行保养,或发生故障时进行维修等原因,导致机器在某一时间段内无法工作,该时间段即为机器的不可用区间。经典的排序问题一般假设所有的工件都进行加工,对于工件可拒绝的排序问题,厂家通常会拒绝一些获利相对较小的工件,拒绝工件虽然可以节约生产成本,但是需要付出一定的惩罚费用,该惩罚费用即为拒绝惩罚。比如航空业、电子工业等等。本文研究带有释放时间、退化效应、拒绝工件及不可用区间的排序问题。该问题中,所有工件的释放时间是相同的。工件可以被排在机器上进行加工,也可以被拒绝,但是需要支付一定的拒绝惩罚。机器带有一个不可用区间,在这段时间内,机器无法工作。具体内容概括如下:1.讨论了目标函数是所有加工工件的最大完工时间与所有拒绝工件的拒绝惩罚之和的单机排序问题。首先给出了拟多项式时间的动态规划算法,最后得到了全多项式近似方案,并分析了该近似方案的时间复杂性。2.讨论了目标函数是所有加工工件的加权总完工时间与所有拒绝工件的拒绝惩罚之和的单机排序问题。首先,说明了这个问题是一般意义NP-难的,然后通过划分程序的方法得到了全多项式近似方案,最后,分析了该近似方案的时间复杂性。3.讨论了两台机器排序问题。其中一台机器带有一个不可用区间,在这段时间内,机器无法工作,另外一台机器一直可用。讨论的目标函数所有加工工件的加权总完工时间与所有拒绝工件的拒绝惩罚之和。首先,说明了这个问题是一般意义NP-难的,然后通过划分程序的方法得到了全多项式近似方案,最后,分析了该近似方案的时间复杂性。