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

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

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

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

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