生產(chǎn)計劃與調(diào)度.docx

核心思想：為了編制和優(yōu)化汽車裝配線的生產(chǎn)計劃與調(diào)度,控制整個裝配工位的裝配節(jié)奏,使其負(fù)荷均衡并保持與大規(guī)模生產(chǎn)線一樣的資源利用率首先將汽車裝配線簡化為一個Flow shop （流線式生產(chǎn)）問題,并建立其混合整數(shù)規(guī)劃模型,由此求得使各裝配工位的資源利用率和準(zhǔn)備成本達(dá)到整體優(yōu)化并盡可能滿足需求的粗生產(chǎn)計劃。然后考慮裝配線的細(xì)節(jié),建立求解生產(chǎn)計劃與調(diào)度整體優(yōu)化問題的數(shù)學(xué)模型,利用模擬退火( SimulatedAnnealing) 算法與快速調(diào)度仿真相結(jié)合的方法使生產(chǎn)計劃與調(diào)度達(dá)到整體優(yōu)化。 具體步驟如下：1 建立一個粗生產(chǎn)計劃首先建立一個粗生產(chǎn)計劃的混合整數(shù)規(guī)劃模型其中, N 為計劃任務(wù)所要裝配的汽車種類數(shù); M為汽車裝配線上的工位數(shù); xi 為計劃區(qū)間內(nèi)裝配第i種汽車的產(chǎn)量; di 為計劃區(qū)間內(nèi)對第i 種汽車的需求;j、j 分別為計劃區(qū)間內(nèi)第j 個裝配工位的空閑時間和可用時間; a+i 為第i 種汽車超產(chǎn)的存儲及占用流動資金的單位成本; a-i 為第i 種汽車欠產(chǎn)而違約受罰的單位成本; cj 為與資源閑置有關(guān)的成本系數(shù); tij 為第j 個裝配工位裝配第i 種汽車所需要的時間; ( c) + 為max(0 , c) ,即取正數(shù);sgn( xi) 為符號函數(shù), 當(dāng)xi 0時, sgn( xi) 取1 ,否則取0 ; bij 、tij 分別為第i 種汽車在第j 個裝配工位上的準(zhǔn)備成本和準(zhǔn)備時間但是上述模型在某些點(diǎn)處導(dǎo)數(shù)不存在，顧引進(jìn)一些變量和約束將其轉(zhuǎn)換為混合整數(shù)線性規(guī)劃模型求解。改進(jìn)為：也就是利用分枝定界發(fā)或單純型法將之前的模型線性化。具體得到粗生產(chǎn)計劃的步驟如下：2 生產(chǎn)計劃與調(diào)度集成優(yōu)化的實(shí)現(xiàn)通過單純型算法與分枝定界結(jié)合，所得到的混合整數(shù)線性規(guī)劃模型，只注意到了生產(chǎn)過程中的一些主要參變量，而忽略了裝配線的細(xì)節(jié)，由其獲得的粗生產(chǎn)計劃可作為后續(xù)生產(chǎn)計劃與調(diào)度整體優(yōu)化問題迭代求解的初始計劃,以加快問題的求解速度。另外,考慮細(xì)節(jié)的裝配線調(diào)度往往是一個非結(jié)構(gòu)化問題,很難用解析的方法求解,較為可行的辦法是使用基于可變時間流的快速調(diào)度仿真。最后,利用SA 算法搜索來解決最優(yōu)計劃與調(diào)度的選擇問題汽車裝配車間生產(chǎn)計劃與調(diào)度整體優(yōu)化的數(shù)學(xué)模型：其中,( s , i) 為N 種汽車或其中部分通過裝配線的順序(調(diào)度) s 中的第i 個位置所對應(yīng)的汽車種類; x= ( x( s ,1) , x( s ,2) , , x( s , N) ) 為生產(chǎn)計劃向量; f ( x ,s) 為汽車裝配任務(wù)全部完成的時間; r 為任務(wù)完成時間權(quán)系數(shù); q 為各裝配工位負(fù)荷均衡權(quán)系數(shù)。具體算法是通過：1,嵌入式SA算法（從初始生產(chǎn)計劃出發(fā),在計劃層用SA 算法進(jìn)行搜索尋找最好的計劃, 同時對計劃層Markov 鏈中隨機(jī)產(chǎn)生的相鄰計劃用另一個SA 算法搜索經(jīng)過快速調(diào)度仿真計算具有最好性能指標(biāo)的調(diào)度,直至生產(chǎn)計劃與調(diào)度同時達(dá)到優(yōu)化。）2.交替式SA算法（從初始生產(chǎn)計劃出發(fā)尋找一個可行計劃與調(diào)度; 給定調(diào)度,用SA 算法尋找最好的計劃; 反過來給定計劃,再用另一個SA 算法搜索最好的調(diào)度; 交替使用、兩步直至找到最好的計劃與調(diào)度。由于分別對計劃與調(diào)度進(jìn)行SA 算法搜索,在此稱這種方法為交替式SA 算法。）3.串行式SA算法（從初始生產(chǎn)計劃出發(fā)尋找一個可行的計劃; 從可行計劃開始,使用SA 算法尋找最好的計劃; 對此最好的計劃,使用另一SA 算法尋找最好的調(diào)度。由于對計劃和調(diào)度依次使用SA 算法,故稱為串行式SA 算法。）該種方法的優(yōu)劣：優(yōu)點(diǎn)：首先通過單純型法根據(jù)需求計劃獲得一個最優(yōu)值，該值是整數(shù)則定位粗生產(chǎn)計劃，否則進(jìn)行分枝定界，得到的粗生產(chǎn)計劃的最優(yōu)整數(shù)解，可以比較快的獲取粗生產(chǎn)計劃，從而為之后的大規(guī)模集成優(yōu)化做好準(zhǔn)備。（單純形法是是保證b=0，通過轉(zhuǎn)軸，使得檢驗(yàn)數(shù)r=0來求得最優(yōu)解，在靈敏度分析時，對cj的靈敏度分析用單純形法來考察，因?yàn)榇藭rcj變動導(dǎo)致檢驗(yàn)數(shù)變動）通過可變時間流的快速調(diào)度仿真來解決裝配線上的細(xì)節(jié)非結(jié)構(gòu)化問題，通過三種不同的SA算法編程仿真，根據(jù)算例得出文中所提出的啟發(fā)式算法是有機(jī)的將解析方法，模擬退后算法和快速調(diào)度仿真有機(jī)的結(jié)合在一起有效的解決的汽車裝配線生產(chǎn)計劃與調(diào)度的集成優(yōu)化問題，保證至少有一個可行的解，具有創(chuàng)新精神思路新穎。這種方法能夠加快問題的求解速度對于模擬退火算法，它是一種新的隨機(jī)搜索方法,它是近年來提出的一種適合于解決大規(guī)模組合優(yōu)化問題的通用而有效的近似算法。與以往的近似算法相比,模擬退火算法具有描述簡單、使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受到初始條件約束等優(yōu)點(diǎn) 缺點(diǎn)：在獲得粗生產(chǎn)計劃的時候，如果生產(chǎn)計劃規(guī)模大，采用分枝法會使得所分出來的枝越來越多，一個非整數(shù)解編程了2個整數(shù)解的定界，問題就會以2的指數(shù)增長，這樣就會很浪費(fèi)時間，增加計算量浪費(fèi)資源，這個時候可以直接采用單純法，如果獲得的最優(yōu)解不是整數(shù)則直接取整。在集成優(yōu)化的時候，通過兩個實(shí)例的仿真結(jié)果，用ESAA法就行求解時所需要的時間最長，但是獲得的解是性能指標(biāo)最優(yōu)的，相反SSAA求解速度快，但是性能指標(biāo)最差，ASAA處于兩者之