在经典排序中,我们常假设所有机器可以一直工作并且所有工件均需在机器上加工.但是在现实生活中,机器M可能会突然发生故障或者需要定期维修,在某些时间段内机器M是不能加工工件的;对于某个工件Jj,当资源有限时,生产者为了获取更大的利润,会考虑拒绝加工工件Jj.本文在经典排序的基础上,考虑到机器具有不可用区间和工件可被拒绝加工这两种情形,研究了单机排序问题和排列排序问题.第一个问题是:(?)首先,我们利用划分问题的NP-难性质证明了该问题是NP-难的.其次,给出了动态规划算法DP并分析了时间复杂度.特别地,当不可用区间的长度t受到限制时,提出了 3-近似算法,并给出了多项式时间近似方案.之后是3个具有两道工序的排列排序问题:(?)首先,我们证明了以上3个问题均是NP-难的.其次,当不可用区间的长度t受到限制时,我们改进了 SPT-LPT算法,得到能同时解决上述3个问题的M-SPT-LPT近似算法,并证明了 M-SPT-LPT算法对以上3个问题均是2-近似算法且2是紧界.