帶阻塞約束的車間作業(yè)改進(jìn)和聲搜索算法.pdf

1、帶阻塞約束的車間作業(yè)調(diào)度是指兩臺機(jī)器間沒有緩沖區(qū)，一個任務(wù)在一臺機(jī)器上加工完后，不能立刻離開當(dāng)前機(jī)器，須等到它所需的下一臺機(jī)器變?yōu)榭捎貌拍茈x開。阻塞約束的車間作業(yè)調(diào)度是NP難問題。該問題廣泛存在于網(wǎng)絡(luò)數(shù)據(jù)包的存儲轉(zhuǎn)發(fā)、醫(yī)院醫(yī)療器械與手術(shù)安排、列車調(diào)度、鋼鐵生產(chǎn)等系統(tǒng)。
　　本文考慮最大完工時間最小的阻塞約束車間作業(yè)調(diào)度優(yōu)化。分析阻塞車間作業(yè)問題的特點(diǎn)，提出求解該問題的和聲搜索算法框架。構(gòu)造基于問題實(shí)例所有操作的和聲編碼方法；建立新

2、和聲生成規(guī)則探索新解；為避免阻塞約束車間作業(yè)調(diào)度優(yōu)化過程中產(chǎn)生不可行解，提出不可行解可行化的轉(zhuǎn)化方法。提出動態(tài)調(diào)整和聲記憶庫保留概率、動態(tài)調(diào)整音調(diào)擾動概率和動態(tài)調(diào)整和聲記憶庫尺寸等參數(shù)的動態(tài)調(diào)整策略，保證算法的多樣化與集約化動態(tài)平衡。為增強(qiáng)算法搜索能力，在每代和聲搜索中嵌入基于插入的簡單局部搜索算法，提高算法性能。
　　將所提出算法與求解該問題目前最好的啟發(fā)式算法在63個Benchmark實(shí)例上進(jìn)行比較，實(shí)驗結(jié)果表明所提出算法在性