论文摘要
在最近的50年中,机器排序已经成为组合最优化中最重要和最活跃的研究课题之一.在大多数经典的排序文献中,所有的工件都必须安排在机器上加工.也就是说,我们不允许拒绝任何工件.然而,为了获得最大的利润,生产决策者经常会拒绝一些加工时间较长且利润较小的工件.在本文中,我们主要考虑了下面两个带有到达时间和拒绝费用的排序问题.（1）带有到达时间和拒绝费用的单机排序问题带有到达时间和拒绝费用的单机排序问题可以描述如下:有一台机器和n个工件J1…,Jn.每个工件Jj有一个加工时间pj和一个拒绝费用wj.工件Jj或者被拒绝并支付一个确定的拒绝费用wj;或者被接收并安排在机器上加工.目标是最小化被接收工件的最大完工时间与被拒绝工件的全部拒绝费用之和.我们定义R为所有被拒绝工件的集合。采用Graham等人[12]提出的排序问题的一般记号,这个问题记为1|rj,reject|Cmax+∑(Jj∈Rwj.首先,我们证明了这个问题是NP-困难的.其次,对这个问题,我们给出了两个拟多项式时间算法.特别地,当工件有相同的加工时间或者拒绝费用时,由上述拟多项式时间算法,这个问题是多项式时间可解的.最后,我们还给出了一个2-近似算法和一个全多项式时间近似方案.（2）带有到达时间和拒绝费用的无界平行批排序问题带有到达时间和拒绝费用的无界平行批排序问题可以描述如下:有一台机器和n个工件以J1,…Jn.每个工件Jj有一个加工时间pj和一个拒绝费用wj.工件Jj或者被拒绝并支付一个确定的拒绝费用wj;或者被接收并安排在机器上分批加工.其中每个批的加工时间等于该批中工件的最长加工时间.目标是最小化被接收工件的最大完工时间与被拒绝工件的全部拒绝费用之和.我们定义R为所有被拒绝工件的集合.采用Graham等人[12]提出的排序问题的一般记号,这个问题记为1|p-batch,rj,reject|Cmax+∑Jj∈Rwj.首先,我们证明了这个问题是NP-困难的.其次,对这个问题,我们给出了一个拟多项式时间算法.特别地,当工件有相同的拒绝费用时,由上述拟多项式时间算法,这个问题是多项式时间可解的.最后,我们还给出了一个2-近似算法和一个全多项式时间近似方案.