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

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

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

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

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