批處理機環(huán)境下兩階段集成調(diào)度算法研究.pdf

1、生產(chǎn)調(diào)度問題在現(xiàn)代的生活中得到廣泛的應(yīng)用，應(yīng)用于社會生活中的多個領(lǐng)域，如工廠加工生產(chǎn)制造、鋼鐵鑄造、淘寶、物流、網(wǎng)絡(luò)通訊、計算機科學(xué)與技術(shù)等。經(jīng)典調(diào)度問題在現(xiàn)實生活應(yīng)用中是有局限性的，不能完全滿足社會的需要，因此批調(diào)度問題相繼被提出，批調(diào)度問題不再被經(jīng)典調(diào)度問題所約束，而是對經(jīng)典調(diào)度問題的擴展，打破了一臺機器只能加工一個工件的束縛，實現(xiàn)了多個工件可以被一臺機器同時加工，這不僅提高了生產(chǎn)的效率而且提高了資源的利用率。隨著社會的發(fā)展，工件尺

2、寸相同的批調(diào)度問題也不能滿足社會的實際需求，因此差異工件尺寸的調(diào)度問題被研究，也更復(fù)雜。然而，本文研究的批處理機環(huán)境下兩階段集成調(diào)度問題不僅涉及到批調(diào)度問題，還涉及到產(chǎn)品交付的問題，比以上研究的任何調(diào)度問題都復(fù)雜。單機的批調(diào)度問題已經(jīng)被研究學(xué)者證明是NP難問題，因此，本文研究的兩階段問題是一個強NP難問題，深入研究具有重要意義。
　　本文開始簡單地描述了調(diào)度問題的研究背景、概念及分類，然后簡單介紹了批調(diào)度問題及產(chǎn)品交付問題，并描述

3、了批調(diào)度問題的研究現(xiàn)狀，以及批調(diào)度問題中的經(jīng)典調(diào)度問題、現(xiàn)代調(diào)度問題、差異工件尺寸的調(diào)度問題，同時介紹了產(chǎn)品交付問題的研究現(xiàn)狀。其次，分別介紹了確定性算法，啟發(fā)式算法和元啟發(fā)式算法這三種主流的批調(diào)度算法，并且介紹了算法的特點、算法的框架和算法的描述。
　　第三，本文研究了兩階段多車平行批處理機的生產(chǎn)分銷調(diào)度問題。在生產(chǎn)階段，首先對工件分批，然后把分好的批分配到平行批處理機上，并加工這些批。在分配階段，將具有相同容量的車輛調(diào)遣過來，

4、加工完成的批運送到客戶手中。本文目標值是最小化工件的總加權(quán)交付時間，并給出了一個下界算法評估所提出的算法，為解決這個NP難問題，分別提出了一種確定性啟發(fā)式算法(H)和兩種基于蟻群優(yōu)化算法(HACO，MMAS)的混合元啟發(fā)式算法，通過分析問題的性質(zhì)，定義了啟發(fā)式信息和信息素，結(jié)合局部優(yōu)化策略，蟻群首先構(gòu)造調(diào)度，此外，本文在運輸?shù)碾A段設(shè)計了一個啟發(fā)式算法用于運輸已經(jīng)加工完成的批。
　　然后，隨機生成該問題的實例，并用該實例與所提出的算