芯片制造中等待時間受限的并行批調(diào)度問題.pdf

1、本文重點(diǎn)研究任務(wù)等待時間受限的并行批處理調(diào)度問題，研究了單階段調(diào)度和雙階段調(diào)度兩個小問題，分別建立問題的約束規(guī)劃模型。第一個問題是基礎(chǔ)，求解它的“小s大S”規(guī)則也成為第二問題求解算法的一部分。
　　第一個問題是單階段等待時間受限的并行批調(diào)度問題，設(shè)計類似庫存管理中的“小s大S”規(guī)則，該調(diào)度規(guī)則最重要的參數(shù)為隊(duì)長參數(shù)和考慮等待時間受限的時間限制參數(shù)，基于該規(guī)則進(jìn)行模擬實(shí)驗(yàn)，用RSM響應(yīng)面方法進(jìn)行參數(shù)優(yōu)化，將模擬結(jié)果同在CPLEX環(huán)境

2、下用約束規(guī)劃（CP方法）求得的解進(jìn)行比較?！靶大S”規(guī)則在運(yùn)行時間、目標(biāo)函數(shù)優(yōu)化效果、操作便利性方面都比CP方面表現(xiàn)優(yōu)異。當(dāng)機(jī)器數(shù)量比較少時（接近于任務(wù)族數(shù)量），“小s大S”規(guī)則和CP方法求得解的質(zhì)量比較相似。隨著機(jī)器數(shù)量的增多，“小s大S”規(guī)則求得解中每個任務(wù)平均完工時間逐漸減少，趨近于任務(wù)的加工時間，很少出現(xiàn)任務(wù)超過受限時間才開始加工的現(xiàn)象。而CP方法解的質(zhì)量變化不顯著，運(yùn)行時間迅速加長，占用空間迅速變大。
　　第二個問題為

3、兩階段的并行批調(diào)度問題，引入上游的預(yù)處理加工機(jī)器。結(jié)合單階段批調(diào)度的“小s大S”規(guī)則，設(shè)計了兩種求解算法，分別為SPT-(s,S)算法與PSO-(s,S)算法。算法的SPT（最短加工時間規(guī)則）部分和PSO（粒子群算法）部分用于第一階段的調(diào)度，“小s大S”規(guī)則用于第二階段的調(diào)度。兩種算法都能很好的解決兩階段的并行批調(diào)度問題，SPT-(s,S)算法操作簡單，但是求解質(zhì)量不高，PSO-(s,S)算法求解速度快而且解的質(zhì)量也很好，在小規(guī)模問題中