一種鄰域搜索算法在差異工件單機(jī)批調(diào)度問題中的應(yīng)用研究.pdf

1、生產(chǎn)調(diào)度是一類重要的組合優(yōu)化問題，在工業(yè)生產(chǎn)、制造系統(tǒng)等領(lǐng)域應(yīng)用廣泛。合理的調(diào)度方案有助于提高生產(chǎn)效率，減少生產(chǎn)成本，因此對(duì)調(diào)度問題研究有著重要的現(xiàn)實(shí)意義。批調(diào)度是調(diào)度問題的一個(gè)重要分支。不同于經(jīng)典調(diào)度問題，在批調(diào)度模型中，一臺(tái)機(jī)器可以同時(shí)處理多個(gè)工件。差異工件批調(diào)度問題(Batch ProcessingMachines with Non-identical Job Sizes，NSBM)是對(duì)傳統(tǒng)批調(diào)度問題的進(jìn)一步擴(kuò)展，即工件尺寸不同，

2、且同一批中工件的總尺寸不能超過批的容量限制。鄰域搜索算法是求解組合優(yōu)化問題的一類重要優(yōu)化方法，這類算法以進(jìn)化的方式在解空間中進(jìn)行尋優(yōu)，具有簡(jiǎn)單、適用范圍廣和魯棒性強(qiáng)等。本文將一種新的鄰域搜索算法——自由搜索算法(Free Search，F(xiàn)S)應(yīng)用于NSBM問題，主要工作如下：
　　 首先，充分利用工件序列這一啟發(fā)信息求解NSBM問題，即首先采用FS算法尋找一個(gè)較優(yōu)的工件序列，然后將該工件序列按一定的啟發(fā)式規(guī)則進(jìn)行分批。論文針對(duì)生

3、產(chǎn)調(diào)度問題的離散性，設(shè)計(jì)了向量形式的編碼方式，并結(jié)合改進(jìn)的Best-Fit啟發(fā)式分批規(guī)則，構(gòu)造了工件序列編碼的自由搜索算法。根據(jù)本文的目標(biāo)函數(shù)，對(duì)算法模型中的信息素重新定義，并設(shè)置三類不同數(shù)值的鄰域半徑，避免算法陷入局部最優(yōu)。實(shí)驗(yàn)表明，F(xiàn)S的求解效果優(yōu)于現(xiàn)有的啟發(fā)式算法和智能算法。
　　 其次，利用批序列的編碼方式求解NSBM問題，即直接構(gòu)造批，然后用鄰域搜索算法對(duì)批序列優(yōu)化。工件序列編碼的方法在求解問題時(shí)結(jié)果會(huì)受到所選用的啟發(fā)

4、式分批規(guī)則的影響，若分批規(guī)則求解效果不好，則工件序列優(yōu)化對(duì)結(jié)果的改進(jìn)也很有限，且該方法不能在完備的解空間中尋優(yōu)，不利于找到更好的解。論文提出了一種混合鄰域搜索算法(Hybrid Neighborhood Search，HNS)，根據(jù)FS算法在搜索過程中存在的停滯問題，加入差異演化算法和局部?jī)?yōu)化策略，并利用尖點(diǎn)災(zāi)變理論的精英保留機(jī)制進(jìn)一步提高搜索效率，仿真實(shí)驗(yàn)驗(yàn)證了HNS算法的有效性。
　　 最后，對(duì)全文進(jìn)行了總結(jié)，討論了進(jìn)一步的