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

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

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

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

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

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