在经典排序问题研究中，所有的工件都必须在机器上加工.然而实际应用中，为了减少生产费用获得更大的收益，生产商往往会拒绝一些加工时间长而收益小的工件.生产商如果选择拒绝这个工件，那么将支付一定的拒绝费用；如果选择接收该工件，那么就需要在机器上进行加工.本学位论文是在工件允许拒绝的假设下研究最小化总误工工作量和总拒绝费用的排序问题.此外，考虑到现实中往往会出现多个代理竞争同一台机器的加工资源，本文也研究了双代理限制排序问题；我们的目的是在一个代理的目标值满足一定限制的前提下让另一个代理的目标值达到最小.　　本文分两部分研究了工件可拒绝的最小化总误工工作量排序问题和双代理限制排序问题.第一部分在工件可中断和不可中断两种假设下我们研究了最小化（加权）总误工工作量和总拒绝费用的排序问题.第二部分我们则研究了工件可中断时，使得一个代理的总误工工作量小于某个门槛值的限制下最小化另一个代理的排序费用.　　本文的主要结果如下：　　?证明了排序问题此处为公式是 NP-困难的，并说明排序问题此处为公式存在此处为公式时间算法和全多项式时间近似方案.　　?给出了排序问题此处为公式的两个拟多项式时间算法和一个全多项式时间近似方案.　　?给出了排序问题此处为公式的拟多项式时间算法.　　?给出了双代理限制排序问题此处为公式时间算法.　　?对双代理限制排序问题此处为公式,说明了：当fA=YA时，问题是NP-困难的并存在拟多项式时间算法；当此处为公式时存在多项式时间算法.