帶有不可用區(qū)間的批運輸排序問題.pdf

1、在實際生產(chǎn)中，因機器在加工過程中發(fā)生故障或維修等原因會使機器在某一區(qū)間不可用；而且在真實環(huán)境中，生產(chǎn)商不可能對每個工件規(guī)定工期,相反,他們要預(yù)設(shè)一些日期,完工的工件應(yīng)該在那時被交貨。我們把同時交貨的工件看做一批，交貨日期稱為批交貨期。則批的加工時間依賴于這批中所有工件的加工時間，等于所有工件的加工時間之和；批的完工時間等于這批中最后一個工件的完工時間。同批中工件的完工時間相同，都等于這批的完工時間。本文結(jié)合帶有不可用區(qū)間和批運輸?shù)那闆r，

2、在這個模型中，工件的完工時間不僅受不可用區(qū)間的限制還與它所在批有關(guān)，批交貨期等于批的完工時間。因此，工件的流水時間等于該工件所在批的批交貨期。而對于帶有一般批交貨期和提早懲罰的排序問題，本文分別討論了所有工件的加工時間相同時，兩個不同的目標(biāo)函數(shù)的極小化問題。一個工件的提早等于交貨期與完工時間的差。具體研究的內(nèi)容概括如下：
　　1.對于單機問題機器上的任意時間段為不可用區(qū)間的情況，本文討論的是目標(biāo)函數(shù)是極小化總流水時間及運輸費用之和

3、的問題。對于上述問題分析了最優(yōu)解的性質(zhì)，給出了擬多項式時間的動態(tài)規(guī)劃算法及算法的計算復(fù)雜性，并用具體的數(shù)值例子表明了算法的有效性。
　　2.對于兩臺平行機問題，其中一臺機器上的任意時間段為不可用區(qū)間的情況，本文討論的是目標(biāo)函數(shù)是極小化總流水時間及運輸費用之和的問題。對于上述問題給出了最優(yōu)解的性質(zhì)，擬多項式的動態(tài)規(guī)劃算法及算法的計算復(fù)雜性。
　　3.對于恒速機問題，考慮其中一臺機器上的某個時間段是不可用區(qū)間的情況，也討論了目標(biāo)