生產計劃與調度.docx

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