基于完全局部搜索的無等待車間作業(yè)調(diào)度方法.pdf

1、無等待車間作業(yè)調(diào)度問題廣泛存在于金屬冶煉、食品加工、化工生產(chǎn)等制造系統(tǒng)中。不同于傳統(tǒng)的車間作業(yè)調(diào)度，該問題具有無等待約束條件，即一個作業(yè)一旦開始加工就必須連續(xù)進(jìn)行，不允許中斷。無等待車間作業(yè)調(diào)度通常被分解為兩個子問題：時間表生成和任務(wù)排列。
　　本文考慮最大完工時間最小的無等待車間作業(yè)調(diào)度優(yōu)化問題，針對現(xiàn)有的時間表方法無法解決有向環(huán)的活動調(diào)度、目前最優(yōu)任務(wù)排列算法計(jì)算時間過長等問題，提出一種有效的元啟發(fā)式算法。定義一種描述活動調(diào)度

2、任務(wù)約束的受限關(guān)系圖，并分析基于受限關(guān)系圖的三種無延遲時間表方法的特點(diǎn)：集成兩種基本時間表策略，設(shè)計(jì)一個具有部分延遲的時間表方法；基于帶記憶的完全局部搜索算法CLM和帶有限記憶的完全局部搜索算法CLLM，提出任務(wù)排列的帶記憶變鄰域完全局部搜索算法CLMVN；設(shè)計(jì)保存比當(dāng)前解更優(yōu)鄰域值的隊(duì)列，擴(kuò)大搜索范圍，提高算法性能；構(gòu)建避免重復(fù)搜索的記憶策略；定義多個鄰域結(jié)構(gòu)，建立變鄰域搜索機(jī)制；實(shí)現(xiàn)算法的多樣性和集約性動態(tài)平衡。
　　將所提出