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

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

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

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