加工時間非常數(shù)的排序與調(diào)度模型研究.pdf

1、排序與調(diào)度問題是一類重要的組合最優(yōu)化問題。在經(jīng)典排序與調(diào)度問題中,通常假設(shè)工件的加工時間為常數(shù)。但在許多實際問題中,工件的加工時間可能與其開工時間或所排位置有著某種聯(lián)系,由此產(chǎn)生一些新型排序與調(diào)度問題。這些加工時間非常數(shù)的新型排序與調(diào)度問題比經(jīng)典調(diào)度問題更為復(fù)雜,絕大多數(shù)都是NP-難問題?？紤]實際應(yīng)用的需要,研究這些新型排序與調(diào)度問題存在多項式算法的情況很有必要。這些問題的多項式算法一方面可以對某些問題給出求解方法,另一方面還可以為解決

2、其它問題提供近似算法。
　　本文結(jié)合現(xiàn)代排序與調(diào)度問題研究具有加工時間非常數(shù)的幾類排序問題。研究的基本思路都是先根據(jù)考慮問題構(gòu)建模型,然后考慮問題的計算復(fù)雜性,因為這些問題大多都是NP-難的,因此從一些特殊情況入手,給出問題在可解情況下的多項式時間最優(yōu)算法,然后再對一般情況給出啟發(fā)式算法并分析最壞情形下界或者給出動態(tài)規(guī)劃算法。
　　本文研究以下幾方面問題:
　?、排c已經(jīng)加工過工件之和有關(guān)的排序與調(diào)度問題
　　考慮

3、了五種排序與調(diào)度問題模型,分別是:一般學(xué)習(xí)效應(yīng)的模型、已經(jīng)加工過的工件加工時間的指數(shù)函數(shù)的學(xué)習(xí)效應(yīng)模型、對數(shù)效應(yīng)模型、成組技術(shù)下的學(xué)習(xí)效應(yīng)模型。對于具有學(xué)習(xí)效應(yīng)下單臺機器問題,最大完工時間問題利用經(jīng)典的SPT序的性質(zhì)均可以得到最優(yōu)解。總完工時間問題在不考慮成組技術(shù)時也可以利用SPT性質(zhì)得到最優(yōu)解。具有成組技術(shù)的學(xué)習(xí)效應(yīng)下,每組中的工件個數(shù)相等,利用分組個數(shù)和安裝時間滿足一致關(guān)系可以得到問題的最優(yōu)解。具有學(xué)習(xí)效應(yīng)的流水機排序與調(diào)度問題更為

4、復(fù)雜,考慮機器具有某些優(yōu)勢關(guān)系和給定工件在所有機器上的加工時間相同兩種情形。對于目標(biāo)函數(shù)為最大完工時間和總完工時間問題分別給出多項式時間算法。對于具有老化效應(yīng)時,考慮了最大完工時間最小化和總完工時間最小化問題,討論了0<￡,a111aM<<,1aM3三種情形,當(dāng)老化因子11aM<<時,該問題的最優(yōu)解仍然沒有得到解決。1
　?、茣r間相關(guān)和學(xué)習(xí)效應(yīng)下的排序與調(diào)度問題
　　工件的到達時間依賴資源分配問題,對于最大完工時間問題和資源

5、消耗量總和問題進行分析。給出了資源消耗量限制下最小化最大完工時間問題的最優(yōu)解。對于給定的工件序列,提出最大完工時間限制下最小化資源消耗量的最優(yōu)分配方案。時間相關(guān)和指數(shù)學(xué)習(xí)效應(yīng)的問題,證明最大完工時間問題和總完工時間問題具有多項式時間算法。而總權(quán)完工時間問題、最大延遲問題、總折扣完工時間問題和總誤工個數(shù)問題不存在多項式時間算法。經(jīng)典的算法作為問題的啟發(fā)式算法,得出問題的最壞情況的誤差界。并證明在某些特殊情況下這些問題具有多項式時間算法。對

6、于RW問題給出了動態(tài)規(guī)劃算法,當(dāng)批工件的完工時間和批的規(guī)模滿足一致關(guān)系,給出了多項時間算法。最后研究了成組技術(shù)下的退化和學(xué)習(xí)效應(yīng)問題。
　?、桥c工期相關(guān)的排序與調(diào)度問題
　　具有位置退化的共同交貨期問題,分析了工件的退化率不相同和相同兩種情形,并把這兩個問題轉(zhuǎn)化為指派問題進行求解。機器具有多次維修的問題,共同交貨期分為包括維修區(qū)間和不包括維修區(qū)間兩種情形討論,并給出相應(yīng)的算法和時間復(fù)雜性。利用共同工期指派方法和松弛工期指派方

7、法,研究了工期費用函數(shù),提前工件費用和放棄加工的工件的懲罰費用之和最小化的工期指派問題。
　?、戎匦屡判蚺c調(diào)度問題
　　本節(jié)的主要貢獻是把重新排序與調(diào)度問題引入退化效應(yīng)和學(xué)習(xí)效應(yīng)概念。研究了序列錯位和時間錯位擾動下的總誤工問題,提出了多項式時間算法或者擬多項式時間算法、動態(tài)規(guī)劃算法。
　　與前人的研究相比,本文有以下幾個主要的創(chuàng)新點:其一,根據(jù)電腦操作系統(tǒng)VISTA和WIN7的實際,提出機器和工人相關(guān)的學(xué)習(xí)效應(yīng)同時發(fā)生

8、的模型,該模型具有更一般性和普適性。根據(jù)當(dāng)前研究學(xué)習(xí)效應(yīng)相關(guān)的排序與調(diào)度學(xué)習(xí)模型中,出現(xiàn)當(dāng)工件的數(shù)目增加比較多時,給定的工件的實際加工時間可能會突然降到0或者會突然變得更大現(xiàn)象;結(jié)合這樣方面的實際生產(chǎn)需要,提出了對數(shù)相關(guān)和指數(shù)相關(guān)的學(xué)習(xí)效應(yīng)模型。改進了以往模型的不足。其二,通過調(diào)研發(fā)現(xiàn),在實際的生產(chǎn)中,客戶往往是根據(jù)生產(chǎn)商的實際的生產(chǎn)能力提供訂單的。客戶提供加工的工件并不一定是提前到達,因此考慮到達時間和資源量有關(guān)的問題是很現(xiàn)實的,也是