在过去的六十年里,排序已经成为运筹学和组合最优化中最重要和最活跃的分支之一.然而,在大多数经典排序文献中,所有的工件都必须安排在机器上进行加工,即我们不允许拒绝任何工件.但是，在实际中却并非总是如此.随着市场经济的日益全球化,市场竞争也越来越激烈.为了提高生产企业的市场竞争性，良好的生产计划和有效的成本控制已经成为企业之间竞争的关键因素.因此,为了有效的利用有限的资源获得尽可能多的利润.生产决策者有时不得不拒绝一些比较耗费资源且所带来利润较小的工件.工件可拒绝的机器排序问题的基本模型可以描述如下：有n个工件J1,...，Jn和m台机器M1,…,Mm.每个工件Jj有一个加工时间pj和拒绝费用ej.在大多数情形,我们假设所有的数据都是整数.每个工件Jj或者被接收并安排在机器上加工；或者被拒绝并且需要支付确定的拒绝费用ej.在本文中,我们研究了几个典型的工件可拒绝的机器排序问题.在第二章中,我们考虑了拒绝费用有限制的单机排序问题.考虑的目标函数分别为接收工件的最大完工时间、最大延迟、(加权)完工时间总和、(加权)误工总和以及(加权)误工总数.我们针对不同的目标函数分析了它们的计算复杂性并对其中的NP-困难问题给出了拟多项式时间算法.进一步,对带有到达时间的最小化最大完工时间问题,我们给出了一个全多项式时间近似方案.对于与工期相关的几个排序问题,我们证明了这些问题都不存在有界近似比的近似算法.在第三章中,我们考虑了工件可拒绝的单机无界平行批排序问题.在这个问题中,一个批的加工时间被定义为批里面最长工件的加工时间.在这一章中,我们主要考虑了四个问题：(1)最小化所有接收工件的完工时间与所有拒绝工件的拒绝费用之和；(2)在拒绝工件的拒绝费用之和不超过一个给定的上界的约束下最小化接收工件的完工时间和；(3)在接收工件的完工时间和不超过一个给定的上界的约束下最小化拒绝工件的拒绝费用之和；(4)找出所有的Pareto最优排序.对第一个问题,我们给出了一个多项式时间的最优算法.对其它三个问题,我们证明了它们都是NP-困难的并给出了一个拟多项式时间算法和一个全多项式时间近似方案.在第四章中,我们考虑了工件带有到达时间工件可拒绝的单机排序问题.目标为最小化接收工件的最大完工时间与拒绝工件的拒绝费用之和.首先,对工件允许劈开的离线问题,我们给出了一个多项式时间的最优算法；然后,对工件有任意多个到达时间的在线问题.不管工件是否允许劈开,我们给出了一个工件不可劈开的具有最好可能的竞争比2的在线算法.当工件至多有2个不同的到达时间时,不管工件是否允许劈开,我们给出了一个工件不可劈开的具有最好可能的竞争比1.618的在线算法.在第五章中,我们考虑了工件可拒绝的两台机器流水作业排序问题.在这个问题中,工件的完工时间被定义为它在第二台机器上的完工时间.目标为最小化接收工件的最大完工时间与拒绝工件的拒绝费用之和.首先,我们证明了甚至当所有的工件在某一台机器上的加工时间都相等或所有工件的拒绝费用都相等时,该问题都是NP-困难的.其次,对这个问题，我们给出了一个拟多项式时间算法,一个2-近似算法和一个全多项式时间近似方案.最后,对两种特殊的情形,我们分别给出了多项式时间的最优算法.在第六章中,我们考虑了工件带有到达时间工件可拒绝的多台平行机排序问题.目标为最小化接收工件的最大完工时间与拒绝工件的拒绝费用之和.当机器数m是一个固定的常数时,我们证明了该问题在一般意义下是NP-困难的：当机器数m不确定并且是输入的一部分时,我们证明了该问题是强NP-困难的.进一步我们给出了一个2-近似算法和一个全多项式时间近似方案.在第七章中,我们考虑了具有机器使用费用工件可拒绝的多台无关机排序问题.目标为最小化机器的使用费用,接收工件的全部完工时间以及拒绝工件的拒绝费用之和.对此问题.我们首先把它转化成一个已知的多项式时间可解问题,从而证明了该问题是多项式时间可解的.