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

1、本文重點(diǎn)研究任務(wù)等待時(shí)間受限的并行批處理調(diào)度問(wèn)題，研究了單階段調(diào)度和雙階段調(diào)度兩個(gè)小問(wèn)題，分別建立問(wèn)題的約束規(guī)劃模型。第一個(gè)問(wèn)題是基礎(chǔ)，求解它的“小s大S”規(guī)則也成為第二問(wèn)題求解算法的一部分。
　　第一個(gè)問(wèn)題是單階段等待時(shí)間受限的并行批調(diào)度問(wèn)題，設(shè)計(jì)類似庫(kù)存管理中的“小s大S”規(guī)則，該調(diào)度規(guī)則最重要的參數(shù)為隊(duì)長(zhǎng)參數(shù)和考慮等待時(shí)間受限的時(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)行時(shí)間、目標(biāo)函數(shù)優(yōu)化效果、操作便利性方面都比CP方面表現(xiàn)優(yōu)異。當(dāng)機(jī)器數(shù)量比較少時(shí)（接近于任務(wù)族數(shù)量），“小s大S”規(guī)則和CP方法求得解的質(zhì)量比較相似。隨著機(jī)器數(shù)量的增多，“小s大S”規(guī)則求得解中每個(gè)任務(wù)平均完工時(shí)間逐漸減少，趨近于任務(wù)的加工時(shí)間，很少出現(xiàn)任務(wù)超過(guò)受限時(shí)間才開始加工的現(xiàn)象。而CP方法解的質(zhì)量變化不顯著，運(yùn)行時(shí)間迅速加長(zhǎng)，占用空間迅速變大。
　　第二個(gè)問(wèn)題為

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