帶不可用區(qū)間和退化效應(yīng)的并行批排序問題.pdf

1、在制造業(yè)中,處理機(jī)由于發(fā)生故障或進(jìn)行維護(hù)、保養(yǎng)等原因,導(dǎo)致處理機(jī)不可用,產(chǎn)生一些不可用區(qū)間,并且工件的實(shí)際加工時(shí)間與開始加工時(shí)間有關(guān)。
　　本文研究的是帶有不可用區(qū)間和退化效應(yīng)的單機(jī)無界并行批排序問題。在并行批處理機(jī)中,相同一批中的工件其開始加工時(shí)間相同,完工時(shí)間也相同,并且批一旦開始加工就不可以中斷;每一批的加工時(shí)間都等于這批工件中加工時(shí)間的最大者;同批中的工件完工時(shí)間都相同,為這批的完工時(shí)間。文中批處理機(jī)為無界模型,也就是同批

2、中工件數(shù)沒有上界。本文分別給出了求解極小化最大費(fèi)用及極小化總費(fèi)用的擬多項(xiàng)式時(shí)間算法。特別當(dāng)k固定、目標(biāo)函數(shù)為誤工工件數(shù)時(shí),該問題為多項(xiàng)式時(shí)間可解的。我們還討論了工件帶有不同釋放時(shí)間時(shí),目標(biāo)函數(shù)為最大完工時(shí)間的排序問題，當(dāng)工件的加工時(shí)間分別為pj=aj+bt和pj=bjt時(shí)，給出了對(duì)應(yīng)的多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法。
　　具體研究的內(nèi)容概括如下：1．對(duì)于工件的加工時(shí)間為pj=aj+bt的情況,討論了帶有不可用區(qū)間的無界并行批排序問題。<

3、br>　　(1)對(duì)于目標(biāo)函數(shù)為最大費(fèi)用的排序問題,我們給出了一個(gè)擬多項(xiàng)式動(dòng)態(tài)規(guī)劃最優(yōu)算法。
　　(2)對(duì)于目標(biāo)函數(shù)為總費(fèi)用的排序問題,我們給出了一個(gè)擬多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法。特別當(dāng)k固定時(shí),對(duì)于目標(biāo)函數(shù)為誤工工件數(shù)時(shí),該問題為多項(xiàng)式時(shí)間可解的。
　　(3)研究了工件有不同釋放時(shí)間的排序問題,其目標(biāo)函數(shù)為最大完工時(shí)間。我們給出了求解此問題的多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法。
　　2.對(duì)于工件的加工時(shí)間為pj=bjt、帶有不可用