帶有拒絕費(fèi)用的機(jī)器排序問題.pdf

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

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

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

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