帶有拒絕費用的機器排序問題.pdf

1、在最近的50年中,機器排序已經成為組合最優(yōu)化中最重要和最活躍的研究課題之一.在大多數(shù)經典的排序文獻中,所有的工件都必須安排在機器上加工.也就是說,我們不允許拒絕任何工件.然而,為了獲得最大的利潤,生產決策者經常會拒絕一些加工時間較長且利潤較小的工件.在本文中,我們主要考慮了下面兩個帶有到達時間和拒絕費用的排序問題.
　　(1)帶有到達時間和拒絕費用的單機排序問題帶有到達時間和拒絕費用的單機排序問題可以描述如下:有一臺機器和n個工件

2、J1…,Jn.每個工件Jj有一個加工時間pj和一個拒絕費用wj.工件Jj或者被拒絕并支付一個確定的拒絕費用wj;或者被接收并安排在機器上加工.目標是最小化被接收工件的最大完工時間與被拒絕工件的全部拒絕費用之和.我們定義R為所有被拒絕工件的集合。采用Graham等人[12]提出的排序問題的一般記號,這個問題記為1|rj,reject|Cmax+∑(Jj∈Rwj.首先,我們證明了這個問題是NP-困難的.其次,對這個問題,我們給出了兩個擬多項

3、式時間算法.特別地,當工件有相同的加工時間或者拒絕費用時,由上述擬多項式時間算法,這個問題是多項式時間可解的.最后,我們還給出了一個2-近似算法和一個全多項式時間近似方案.
　　(2)帶有到達時間和拒絕費用的無界平行批排序問題帶有到達時間和拒絕費用的無界平行批排序問題可以描述如下:有一臺機器和n個工件以J1,…Jn.每個工件Jj有一個加工時間pj和一個拒絕費用wj.工件Jj或者被拒絕并支付一個確定的拒絕費用wj;或者被接收并安排在

4、機器上分批加工.其中每個批的加工時間等于該批中工件的最長加工時間.目標是最小化被接收工件的最大完工時間與被拒絕工件的全部拒絕費用之和.我們定義R為所有被拒絕工件的集合.采用Graham等人[12]提出的排序問題的一般記號,這個問題記為1|p-batch,rj,reject|Cmax+∑Jj∈Rwj.首先,我們證明了這個問題是NP-困難的.其次,對這個問題,我們給出了一個擬多項式時間算法.特別地,當工件有相同的拒絕費用時,由上述擬多項式時