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

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

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

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

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

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

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