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

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

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

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