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

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

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

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

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

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

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

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

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