現(xiàn)代調(diào)度若干問(wèn)題研究.pdf

1、在經(jīng)濟(jì)全球化、貿(mào)易自由化和社會(huì)信息化的新形勢(shì)下，傳統(tǒng)的相對(duì)穩(wěn)定的世界市場(chǎng)逐步呈現(xiàn)出動(dòng)態(tài)多變的特征，企業(yè)之間過(guò)去是在局部區(qū)域內(nèi)進(jìn)行競(jìng)爭(zhēng)，而現(xiàn)在是在全球范圍內(nèi)進(jìn)行競(jìng)爭(zhēng)；同行業(yè)之間、跨行業(yè)之間的相互滲透、相互競(jìng)爭(zhēng)日益激烈，因此，企業(yè)的經(jīng)營(yíng)戰(zhàn)略發(fā)生了很大變化，以最低的成本、最好的質(zhì)量、最快的上市速度、最優(yōu)的服務(wù)來(lái)滿足不同顧客的需求，成為現(xiàn)代企業(yè)適應(yīng)市場(chǎng)需求、提高競(jìng)爭(zhēng)力的關(guān)鍵因素。如何作到上述幾點(diǎn)呢?調(diào)度在其中的作用是不容忽視的，因?yàn)楹玫恼{(diào)度方案

2、可以降低在制品庫(kù)存，縮短產(chǎn)品的生產(chǎn)周期，提高生產(chǎn)率，提高客戶定單交付期滿足率。 另外，就調(diào)度本身而言，由于隨著社會(huì)的發(fā)展，出現(xiàn)了許多新的問(wèn)題，所以傳統(tǒng)的調(diào)度模型就不能滿足人們的需求了，為了幫助企業(yè)適應(yīng)新形式，解決新問(wèn)題，繼續(xù)開展對(duì)調(diào)度問(wèn)題的理論研究具有重要的現(xiàn)實(shí)意義?；诖?，本文在調(diào)度方面作了如下工作：一．研究了三個(gè)單機(jī)維修調(diào)度問(wèn)題： 本文研究的三個(gè)單機(jī)維修調(diào)度問(wèn)題都是對(duì)以前模型的擴(kuò)展，其中問(wèn)題1是將以前文獻(xiàn)研究的單機(jī)維修調(diào)度問(wèn)題的

3、目標(biāo)函數(shù)—工件的完成時(shí)間和推廣為加權(quán)完成時(shí)間和來(lái)進(jìn)行研究。由于問(wèn)題1是強(qiáng)NP-hard的，所以本文對(duì)該問(wèn)題給出了三個(gè)啟發(fā)式算法、一個(gè)遺傳算法、一個(gè)綜合遺傳算法和一個(gè)分枝定界算法，并通過(guò)仿真實(shí)驗(yàn)對(duì)這些算法進(jìn)行了評(píng)價(jià)。問(wèn)題2是在以前文獻(xiàn)研究的單機(jī)維修調(diào)度問(wèn)題的目標(biāo)函數(shù)—工件的完成時(shí)間和上加上一個(gè)使附加費(fèi)用不超過(guò)事先給定的一個(gè)常數(shù)這個(gè)約束來(lái)進(jìn)行研究的，分兩種情形進(jìn)行討論，對(duì)第一種情形：工件的加工不允許中斷的情形給出一個(gè)多項(xiàng)式復(fù)雜度的最優(yōu)算法，

4、對(duì)第二種情形：工件的加工允許中斷的情形，由于此時(shí)問(wèn)題2是強(qiáng)NP-hard的，因此本文首先研究了問(wèn)題2的最優(yōu)調(diào)度的性質(zhì)，然后基于性質(zhì)給出一個(gè)啟發(fā)式算法。問(wèn)題3是在問(wèn)題1的目標(biāo)函數(shù)上加一項(xiàng)附加費(fèi)用而得到的，它也是強(qiáng)NP-hard的，所以對(duì)該問(wèn)題本文給出一個(gè)基于局部搜索的啟發(fā)式算法。 二．新建立并討論了兩個(gè)批處理機(jī)隨機(jī)調(diào)度模型： 本文以超市(配送中心等)進(jìn)貨及半導(dǎo)體制造業(yè)中的老化(burn-in)操作為背景新建立了第一個(gè)批處理

5、機(jī)隨機(jī)調(diào)度模型，針對(duì)六個(gè)與交貨期有關(guān)的目標(biāo)函數(shù)得到六個(gè)問(wèn)題，分機(jī)器不允許空閑和允許空閑兩種情況進(jìn)行了討論．當(dāng)機(jī)器不允許空閑時(shí)，對(duì)這六個(gè)問(wèn)題分別給出了與其等價(jià)的確定優(yōu)化問(wèn)題，針對(duì)確定優(yōu)化問(wèn)題：研究了最優(yōu)調(diào)度的性質(zhì)．對(duì)其中的第一個(gè)問(wèn)題給出一個(gè)啟發(fā)式算法，一個(gè)整數(shù)規(guī)劃模型，對(duì)它的一種特殊情形給出了一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的最優(yōu)算法；對(duì)其中的第二個(gè)問(wèn)題給出兩個(gè)啟發(fā)式算法，對(duì)它的一種特殊情形給出了一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的最優(yōu)算法；對(duì)其中的第五和第六個(gè)問(wèn)

6、題分別給出了一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的最優(yōu)算法． 當(dāng)機(jī)器允許空閑時(shí)，對(duì)每個(gè)問(wèn)題只給出了與其等價(jià)的確定優(yōu)化問(wèn)題，針對(duì)確定優(yōu)化問(wèn)題研究了最優(yōu)調(diào)度的性質(zhì)． 本文以每隔一段固定時(shí)間向某一貨物集散地(或超市、港口等)發(fā)一輛車的貨物運(yùn)輸為背景新建立了第二個(gè)批處理機(jī)隨機(jī)調(diào)度模型，針對(duì)六個(gè)與交貨期有關(guān)的目標(biāo)函數(shù)得到六個(gè)問(wèn)題，對(duì)這六個(gè)問(wèn)題分別進(jìn)行了討論，給出了與其等價(jià)的確定優(yōu)化問(wèn)題，針對(duì)確定優(yōu)化問(wèn)題研究了最優(yōu)調(diào)度的性質(zhì)，對(duì)其中的一個(gè)問(wèn)題給出了