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

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

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

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

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

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

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