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

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

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