傳統(tǒng)優(yōu)化方法求解Job-shop調(diào)度問題的特征分析及改進策略研究.pdf

1、Job-shop調(diào)度問題是一個NP難的組合優(yōu)化問題，探索可行、高效的調(diào)度算法一直是求解該問題的研究重點。當前，大多數(shù)的研究都是利用啟發(fā)式算法對調(diào)度問題進行求解。雖然傳統(tǒng)的優(yōu)化方法能夠有效的求解一般的約束問題，但是它們在Job-shop調(diào)度問題中的求解研究還很少。復(fù)合形法和罰函數(shù)法能夠有效的對約束問題進行求解。拓撲排序算法能夠合理的進行任務(wù)進度的調(diào)度安排。本文的研究以調(diào)度的總完工時間最短為優(yōu)化目標，分析復(fù)合形法，罰函數(shù)法及基于拓撲排序的算

2、法求解Job-shop調(diào)度問題中的流程和特征，并編程實現(xiàn)調(diào)度算法，開發(fā)Job-shop調(diào)度系統(tǒng)。
　　 首先，本文對復(fù)合形法求解一般約束問題的過程和Job-shop調(diào)度問題的模型進行分析，提出利用復(fù)合形法求解Job-shop調(diào)度問題的改進策略，進而構(gòu)造問題的求解流程，研究復(fù)合形法的求解特征。
　　 其次，本文利用罰函數(shù)法將約束問題轉(zhuǎn)化為無約束問題進行求解的思想，將Job-shop調(diào)度問題的約束條件以懲罰項來表示，結(jié)合求解

3、無約束優(yōu)化問題的變量輪換法，從初始解出發(fā)對問題的變量進行一維搜索，以達到求得較優(yōu)解的目的。同時，文中制定了利用罰函數(shù)法求解Job-shop調(diào)度問題的流程，并對罰函數(shù)法的求解特征進行分析。
　　 再次，本文通過結(jié)合圖論中拓撲排序思想和Job-shop調(diào)度問題中的設(shè)備分配規(guī)則，提出基于拓撲排序的算法來求解車間調(diào)度問題。每個調(diào)度問題的可行解中的工序按照開始時間的先后順序排序可以得到問題有向無環(huán)圖中的一個拓撲序列。根據(jù)這個關(guān)系展開了從工