27757.工件可拒絕及加工時間可變的排序問題研究

1、分類號:O22學(xué)校單位代碼:10446曲阜師范大學(xué)博士學(xué)位論文論文題目:工件可拒絕及加工時間可變的排序問題研究研究生姓名:鄒娟學(xué)科、專業(yè):數(shù)學(xué)、應(yīng)用數(shù)學(xué)研究方向:組合最優(yōu)化導(dǎo)師姓名、職稱:張玉忠教授論文完成時間:2014年3月曲阜師范大學(xué)博士學(xué)位論文工件可拒絕及加工時間可變的排序問題研究摘要排序問題是組合優(yōu)化的一個重要分支它廣泛地應(yīng)用于工農(nóng)業(yè)生產(chǎn)、運輸業(yè)、管理科學(xué)和計算機科學(xué)等諸多領(lǐng)域.分批排序、工件加工時間可變、工件可拒絕以及工件可外

2、包的排序都是新型的排序問題因此吸引了國內(nèi)外眾多學(xué)者的關(guān)注.本文對這幾類問題進行了研究做了如下工作.第一章介紹了排序問題的相關(guān)基本知識并簡要概括了本論文的研究成果.第二章考慮了工件的加工時間是開工時間的線性增加函數(shù)的同類機排序問題.目標(biāo)函數(shù)分別是極小化總完工時間和極小化機器上的總負載.當(dāng)退化率(惡化率)相同時這兩個問題是多項式時間可解的.當(dāng)加工時間是其開工時間的一般線性增加函數(shù)時對于極小化機器上的總負載問題給出了一個全多項式時間近似方案.

3、當(dāng)加工時間是其開工時間的簡單線性函數(shù)時對于極小化所有工件被送到目的地的時間這一目標(biāo)函數(shù)也給出了一個全多項式時間近似方案.第三章研究的是工件可拒絕的繼列分批排序問題.每個工件或者安排在單機上成批加工或者被拒絕需要支付拒絕費用.考慮兩種拒絕模型第一種模型是極小化接受工件的排序目標(biāo)值與拒絕工件的拒絕總費用之和.其中排序目標(biāo)分別是最大完工時間總完工時間最大延遲以及加權(quán)總誤工工件數(shù).對于前兩個問題給出了兩個多項式時間算法來求解.對于后兩個問題給出

4、了有效的偽多項式時間算法.第二種模型是在拒絕費用有約束的條件下極小化接受工件的最大完工時間對于該問題給出了一個全多項式時間近似方案.第四章考慮了工件具有就緒時間、加工時間可退化以及工件可拒絕的排序問題.機器環(huán)境分別是單機和平行機.工件的加工時間是其開工時間的簡單線性函數(shù).對于單機問題目標(biāo)函數(shù)是極小化接受工件的最大延遲與拒絕工件的拒絕總費用之和.證明了該問題是強NP困難的.當(dāng)工件的就緒時間與交貨期一致時給出了一個全多項式時間近似方案.對于

5、平行機問題目標(biāo)函數(shù)是極小化所有接受工件被送到目的地的時間與拒絕工件的拒絕總費用之和.當(dāng)工件具有相同的就緒時間給出了一個全多項式時間近似方案.特別地當(dāng)所有工件都被接受時給出了一個啟發(fā)式算法.第五章考慮了工件具有就緒時間、工件加工時間可退化以及工件可拒絕的無界平行批排序問題.工件或者被接受在批處理機上加工或者被拒絕支付一定的拒絕費用.工件的加工時間是其開工時間的簡單線性函數(shù).目標(biāo)函數(shù)是極小化接受工件的最大完工時間與拒絕工件的拒絕總費用之和.