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

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

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

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