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

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

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