汽車裝配車間生產計劃與調度的同時優(yōu)化方法嚴

1、D第OI : 10. 16383 /j . aas . 2002. 06. 007自動化學報28卷 第 6期2002年 11月V ol. 28, No . 6 N ov . , 2002ACT A A U TO M A T ICA SIN IC A汽車裝配車間生產計劃與調度的同時優(yōu)化方法1)嚴洪森夏琦峰(東南大學自動化朱南京如2 0096)cn )劉霞玲( Ea l h syan seu ed u摘 要 文中提出三種新方法來解決汽車裝配車間生產計劃與調度的同時優(yōu)化問題. 首先將汽車裝配線簡化為一個 Flo w sho p問題 , 并建立其混合整數模型 , 以求得使各裝配工位的準備成本和空閑時間

2、盡可能少并盡可能滿足需求的粗生產計劃. 然后在粗生產計劃的基礎上考慮裝配線的細節(jié) ,用 Tabu搜索法與快速調度相結合的三種不同啟發(fā)式算法使生產計劃與調度同時得到優(yōu)化 , 并給出了三種算法的復雜性 . 大量算例的比較研究表明了這些算法的有效性和適用性 .裝配車間 , 生產計劃與調度 ,混合整數, Tabu搜索號T B491; F213. 1APPROACHES TO SIMULTANEOUS PRODUCTION PLANN IN G ANDSCHEDULIN G IN AUTOMOBILE ASSEMBLY WORKSHOPSYAN Hong-Sen X IA Qi-FengZHU Min-

3、RuLIU Xia-Ling( Research Inst itu te of Automa tion, Sou theast University , Nanjing2 0096)( E a l h syan seu ed u cn )AbstractThree new approaches is presented to the simultaneous production planningand scheduling problem in automobile assembly wo rkshops. First of all, an automobile assembly line

4、is simplified into a flow shop, it s mixed integer prog ramming mis f ormulated t o obtain a rough production plan by minimizing the ov erproduction, un- derproduction, set-up and leisure time. On the basis of the obtained rough production plan, three di fferent heuristic algorithms combining Tabu s

5、earch with quick schedule simulation are used t o optimize the production plans and schedules simultaneously, with more details of the assembly line being considered. The computational complexity of each algo rithm i s also given. Compariso n between many computational examples of these algorithms i

6、s carried out, the result confirms thei r ef fectiveness and adaptabili- t y.Key wordsAssembly workshops, productio n planning and scheduling , mixed integ er)“ 863” /C IM S主題項目 ( 863 5708 008和 863 5943 005)和教育部高等學校骨干教師資助計劃資助收稿日期2000 08 7收修改稿日期200 09 20自動化學報28 卷912prog ramming , Tabu search1引言在現行的生產

7、計劃、調度與優(yōu)化文獻中,往往先單獨優(yōu)化生產計劃,然后在被優(yōu)化的計劃基礎上優(yōu)化生產調度,其結果是計劃與調度不能達到整體優(yōu)化,甚至出現生產計劃導致調度不可行或性能很差的情況1 . 為此,本文將提出三種新的方法來解決汽車裝配車間的生6產計劃與調度的同時優(yōu)化問題,以使綜合性能指標最小化. 本文方法的基本思想是,先將汽車裝配線簡化為一個 Flow shop問題,并建立其混合整數模型,以求得使各裝配工位的準備成本和空閑時間盡可能少并盡可能滿足需求的粗生產計劃,然后在粗生產計劃的基礎上考慮裝配線的細節(jié).用 Tabu搜索法7, 8 與快速調度法使生產計劃與調度同時得到優(yōu)化.相結合的三種不同啟發(fā)式算2粗生產計劃

8、設一條裝配線共有 m 個裝配工位,計劃區(qū)間內依據裝配訂單共需裝 n 種汽車且第 i 種汽車需 di輛.再將裝配線簡化為一個shop問題,且最優(yōu)計劃的目標是最大限度地滿足Flo w需求并使各裝配工位的準備成本和空閑時間盡可能少,則可建立求解最優(yōu)粗生產計劃的混合整數模型如下:nmnm> +di )+ +- xi )+bij sgn( xi ) +cjfjmin J =ai ( xi -nai ( d+( 1)ii 1j 1 i 1j 1n> tij sg n( xi ) + fj = Ujs. t.ti j xi +( 2)i 1i 1式中 n 為計劃區(qū)間內需裝配的汽車種類數; m 為

9、汽車裝配線上的裝配工位數; xi為計劃區(qū)間內裝配第 i 種汽車的產量, xi 0且為整數; sg n( xi )為符號函數,當 x i> 0時, sg n( xi )取 1,否則取 0; di為計劃區(qū)間內對第 i 種汽車的需求,是整數; fj為計劃區(qū)間內第 j 個裝配工位的空閑時間,fj 0, j= 1, 2, , m ;Uj為計劃區(qū)間內第 j 個裝配工位的可用時間,是從計劃區(qū)間內+的生產總時間中扣除設備故障維修時間等所剩的時間; ai 為超產一輛第 i 種汽車的及-占用資金的成本; ai 為欠產一輛第 i 種汽車而違約受罰的成本; bij為第 i 種汽車在第 j個裝配工位上的準備成本;

10、 cj為與第 j 個裝配工位閑置有關的成本系數; tij為第 j 個裝配工位裝配第 i 種汽車所需要的時間; tij為第 i 種汽車在第 j 個裝配工位上的準備時間; ( c)+ 為 max ( 0, c ) .式( 1)和( 2)的混合整數非線性n模型可轉化為混合整數線性模型如下:mnmi x i ) + bij yi +( ai n+ +- -cjfjmin J =xi +a( 3)i 1j 1 i 1j 1n> tij yi + fj = Ujs. t.ti j xi +( 4)i 1i 1+- xi + xixi =di( 5)( 6)B yi xi式中 xi 0且為整數; yi

11、 是布爾變量, yi ( 0, 1) ,當 xi > 0; B 是一個大的正數.+-0時為 1,否則為 0; xi 0, xi6 期嚴洪森等: 汽車裝配車間生產計劃與調度的同時優(yōu)化方法913到此, 就可用分枝定界或割平面算法求解式( 3) ( 6)的混合整數線性模型,以獲取使各裝配工位的準備成本和空閑時間盡可能少并盡可能滿足需求的粗生產計劃.3生產計劃與調度的同時優(yōu)化為加快問題求解速度,在式( 3) ( 6)的模型中忽略了裝配線的細節(jié),并由此求出粗生產計劃作為后續(xù)生產計劃與調度同時優(yōu)化問題迭代求解的初始計劃. 另一方面,考慮細節(jié)的同步裝配線調度往往是一個非結構化問題,很難用的方法來求解,

12、較為可行的辦法是使用基于可變時間流的快速調度.此處快速的含義是不要圖形顯示,僅僅通過快速計算給定調度的性能指標.至于最優(yōu)計劃與調度的迭代選擇問題則由基于 Tabu搜索的三種不同啟發(fā)式算法來解決.3. 1Tabu搜索算法為節(jié)省汽車裝配準備時間,同種汽車集中裝配,不分割成多個裝配任務,并在調度時僅占用一個排序位置.參照式( 1)和( 2) ,則求解汽車裝配車間生產計劃與調度同時優(yōu)化問題的數學模型可描述如下:nmin G( x , S) = min a+ ( S ,id ( S ,i )+ +( s ,i ( d ( S ,i -a-)+( x ( S ,i-x ( S ,i+x , Sx , Si

13、 1mnm> b ( S, i j sg n( xcjfj + rf ( x , S ) +) +( S ,ij 1 i 1j 1mm2 1qm(Ujfj ) -(Uj - fj )-( 7)j 1j 1nnt ( S, i j x ( S ,i + t ( S, i j sg n( x ( S ,i) + fj = Ujs. t.( 8)i 1i 1h ( ( S , i ) ) j( S, ix ( S ,i 0且為整數, fj ( 9)( 10)0, j = 1, 2, , m式中 ( S , i )為 n種汽車或其中部分通過裝配線的順序 (調度) S中的第 i 個位置所對應的汽車

14、種類,如果對于 k in 有 ( S , i ) = 0,則表示調度 S 中最多只包含 k - 1種汽車; b ( S, i j 為第 ( S , i )種汽車在第 j 個裝配工位上的準備成本; t ( S ,i j為第 ( S , i )種汽車在第 j 個裝配工位上的準備時間; h ( ( S , i ) )為第 ( S, i )種汽車的下線時間; j( S ,i 為第( S, i )種汽車的交付期; x= ( x ( S, 1 , x ( S , 2 , , x ( S,n ) T 為生產計劃向量;( x, S)為汽車裝配任務全部完f成的時間,由相應計劃和調度共同決定; r 為任務完成時間

15、權系數; q為各裝配工位負荷均衡權系數.Tabu 搜索是由 Glov er7, 8 提出的用于獲取組合最優(yōu)化難題近似解的一種高級啟發(fā)式方法. 在應用 Tabu搜索法求解生產計劃與調度同時優(yōu)化問題( 7) ( 10)之前,首先介紹兩個概念,即相鄰計劃和相鄰調度. 設計劃 = ( x 1 , x 2 , , xn ) T 且對某些 i 有 f>p* *jtij > 0,對j = 1, 2, , m ,則定義 p= ( x 1 , x 2 , , xi- 1 , xi+ 1, xi+ 1 , , xn ) T , p= ( x 1 , x 2 , , xi1, ,xk 1, , xn )

16、 和 p= ( x1 , x 2 , , xi- 1 , xi - 1, xi+ 1 , , xn ) 為的相鄰計劃; 否則定義 p=TT* *p( x 1 , x 2 , , xi1, , xk 1, , xn ) T 和 p= ( x 1 , x2 , , xi - 1 , xi - 1, xi+ 1 , , xn ) T 為的相p* *鄰計劃. 可見的相鄰計劃最多可能有 n2+ n 個.p* * *S* *S* *S對于調度,我們定義僅交換中的兩個元素而形成的調度為相鄰于的調度.自動化學報28 卷914不失一般性,設初始調度 S0 中共包含三種汽車,即 S0= a ,b , c ,則依定

17、義,相鄰于 S0 的調度共有三種: S1= b , a, c , S2= c,b , a , S3 = ( a , c, b) .注意相鄰調度僅交換初始調度 S0 中的兩個元素而得.如 S1 是僅交換 S0 中的 a , b兩個元素而得到的, 是相鄰于 S0 的調度; 但c, a ,b 是交換 S3 中的 a , c 兩個元素而得到的,不能直接交換 S0 中的兩個元素而得,所以c , a, b不是相鄰于 S0 的調度. 一般地,對于包含 n 種汽車的調度 ,則相鄰調度共有n ( n- 1) / 2種.目前, Tabu搜索法主要用于 Flow shop 調度、 Job sho p調度和制造單元形

18、成等方S* *面9 10,而在汽車裝配線生產計劃、調度方面的應用則非常少見. 本文要解決的是計劃與調度的同時優(yōu)化問題,所以需要提出一種新的基于 Tabu搜索的高級啟發(fā)式算法,即Tabu 搜索算法來解決. 其基本思想是以粗生產計劃作為初始解,在計劃層用Tabu搜索尋找最好的計劃,并對計劃層生成的每個相鄰計劃用另一個 Tabu搜索尋找經過快速計算具有最能指標的調度,直至使生產計劃與調度同時達到優(yōu)化. 因一個 Tabu搜索嵌套著另一 Tabu搜索,故取名為Tabu搜索算法.算法 1. 生產計劃與調度同時優(yōu)化問題( 7) ( 10)的Step1. 初始化1)式( 7) ( 9)中的各種數據和參數;Ta

19、bu搜索算法( ETS)size、 給定的計劃移動次數SM- max;算法參數, 包括生產計劃Tabu 表長度 P T-2)P M-m ax、調度 Tabu表長度 S T-size和給定的調度移動次數3) 設置 G- best= M- big, PM- ctr= 0, P T- li st= O , p- best= O, S- best= O . Step2. 搜索初始可行計劃與調度1) 設置初始生產計劃 p0= x;2) 設置當前計劃p= p0 ,并調用算法2以搜索給定計劃 p的可行調度;* * *) < G- best,則設置 p p, p- best p, S- best3) 如

20、果 SC- flag= 1且 G( p, SS* * *, G- best G( p, S* * ) ,然后轉 Step3;4) 生成 p0 的一個相鄰計劃 p,設置 p0= p.然后轉 Step2的 2). Step3.搜索最好計劃與調度1) 生成一個相鄰于 p 的所有可能計劃集,并置 G( p , S) = M- big;* * * *2) 對于該集合中的一個計劃 p,如果 p 不在li st中,則調用算法 2以搜索對于給定P T-計劃 p 的最好調度,并更新當前相鄰集中的最好計劃 p, G( p*p* *, S) G( p, S* * ) ,如G( p, S* * *) < G(

21、p* ,* * *S果1且) ; 否則丟棄 p; 如果計劃Tabu 表中 P T- li st中SC- flag=*的計劃個數少于 P T- size,將 p 加到 P T - list的頂部; 如此重復,直至做完 p 的所有相鄰計劃;p* p* , G( p* * , S* *) G( p*, S* *p* * 不在3) 作一次計劃移動,設置)且如果P T -p* *list中則將加到li st的頂部; 如果li st中的計劃個數>P T- size,則從 P T- li stP T-P T-的底部刪除一個最老的計劃;G( p* *S* * *best p*4) 如果計劃有,即如果)

22、< G- best,則更新最好解 p-, S-best S* * *best G( p* *, S* *, G-) ;PM- ct r P M- ct r+5) 更新到目前為止所作的計劃移動次數1; 如果P M- ctr>P M- max ,則停止迭代并轉 Step4,否則轉 Step3的 1).輸出結果Step4.輸出 P-bestbest和 G- best.S-6 期嚴洪森等: 汽車裝配車間生產計劃與調度的同時優(yōu)化方法915這里 M- big 為一個很大的數; SC- f lag 為對于給定計劃 p是否存在滿足約束( 8) ( 10)的p*調度的標志, SC- f lag= 1

23、表示存在, SC-0表示不存在;為在當前相鄰計劃集中的f lag=*最好計劃; p 為在緊前相鄰計劃集中的最好計劃; p- best為到目前為止找到的最好生產* *S計劃;為相應計劃的最好調度; S- best為到目前為止找到的最好生產計劃,所找到的最好調度; G( p , S)為與生產計劃 p和調度 S相對應的性能指標; G- best為到目前為止所達到的最好指標.算法 2.基于 Tabu搜索的調度優(yōu)化Step1. 初始化設置 SM- ctr= 0,調度 Tabu表 ST - list= O. Step2. 尋找初始調度1) 對給定的當前生產計劃 p,依次按最早交付期和最少批量等優(yōu)先規(guī)則,確

24、定初始調* *S* *S度 S0 ,并置= S0 ,= S0 ,SC- f lag=0;* *S2) 通過快速調度,計算相應于 p 和 S0 的性能指標 G( p, S0 ) ,并置 G( p,) =G( p, S0 ) ,如果 S0 可行(即滿足約束( 8) ( 10) ) ,置Step3. 調度搜索SC- f lag=1.* *S1) 生成一個相鄰于緊前相鄰調度集中的最好調度的所有可能調度集, 并置G( p, S*) = M-big;2) 對于該集合中的一個調度 S,如果 S 不在list中,則通過快速調度,計算調S T-度性能指標 G( p, S ) , 并更新當前相鄰集中的最好調度 S

25、 , G(*Sp , S*) G ( p, S ) ,SC- f lag= 1如果 S 可行且 G( p , S) < G( p, S* ) ; S* S , G( p, S* ) G( p, S )如果 S 和 S* 都不可行且G( p, S ) < G( p, S* ) ; 否則丟棄 S; 如此重復,直至做完 S* * 的所有相鄰調度;*S S, G( p, S* ) G( p, S* ) ,并將加到* *S3) 作一次調度移動,設置ST - list的頂部,如果 ST - list中的調度個數> S T- size,則從 S T- list的底部刪除一個最老的調度.,即

26、可行且 G( p, S* * )* *S< G ( p, S* * *S* *S4) 如果調度有)或和都不可行且G( p, S* *< G( p, S* * * * * *S S, G( p, S) G( p, S* ) ;) ,則更新最好解)5) 更新對當前計劃所作的調度移動次數 SM- ct r SM- ctr+ 1, 如果 SM- ctr>S M- max ,則停止迭代并轉 Step4; 否則轉 Step3的 1) .返回.Step4.算法 1 Step2中的 x 是由求解式( 3) ( 6)所獲得的粗生產計劃并被當作算法的初始解以加快問題的求解速度,因為粗生產計劃往往

27、比隨機選擇的初始解更接近式( 7) ( 10)的真實解. 盡管如此,由于式( 3) ( 6)忽略了裝配線調度等方面的細節(jié),由此獲得的粗生產計劃對式( 7) ( 10)來講往往還是不可行. 此外,從粗生產計劃演變成可行計劃的有效方法無疑是減少裝配線的負荷,所以算法 1 Step2中的相鄰計劃可只定義為 p= ( x1 , x 2 , , xi- 1 , xi - 1, xi+ 1 , , xn ) T ,以加快獲得初始可行解的速度.如果汽車裝配線具有隨機特性(如設備故障、裝配時間發(fā)生變化等) ,可通過算法 1的蒙特卡羅運行來求解其同時優(yōu)化問題.具體做法是: 1)在每次蒙特卡羅運行之前,先按照各隨

28、量的分布函數計算各自的樣本值并用這些樣本值代替式( 7) ( 9)中的相應值,然后調用算法 1; 2)在第一次蒙特卡羅運行時,算法 1 Step2中的 x 為粗生產計劃,但第二次及以后的蒙特卡羅運行時, x 則為前次蒙特卡羅運行后所獲得的最好生產計劃以加快其求解速度, 因為盡管當前蒙特卡羅運行的樣本值很可能同前次蒙特卡羅運行的不一樣,但前次最好生 產計劃往往還是比粗生產計劃更接近本次最優(yōu)解; 3)所有蒙特卡羅運行結束后,需計算除最自動化學報28 卷916好調度以外的所有結果平均值,并用圓整后的最好計劃平均值及隨機參數平均值作為輸入 再一次調用算法 2以獲取相應的最好調度,最后將其和圓整的最好計

29、劃平均值及其它結果的平均值一起作為具有隨機特性的汽車裝配線生產計劃與調度同時優(yōu)化問題的解.算法 1的計算復雜性是 o ( 0. 5n2 ( n2 - 1)SM- m ax ( P M- max )次.如果 n 比較大,用算法 1求解式( 7) ( 10)會需要太多的時間以致無法在可接受的時間內獲得最優(yōu)解. 為此提出另一種求解式( 7) ( 10)的算法,即交替 Tabu搜索法.3. 2 交替 Tabu搜索算法交替 Tabu搜索算法的基本思想: 1)從初始生產計劃開始尋找一個可行計劃與調度; 2) 給定調度,用 Tabu搜索尋找最好的計劃; 3)反過來給定計劃,又用另一 Tabu搜索尋找最好的調

30、度; 4)交替使用 2) , 3)兩步直至找到最好的計劃與調度.由于分別對計劃與調度交替使用兩個 Tabu搜索,故稱為交替 Tabu搜索算法.算法 3. 生產計劃與調度同時優(yōu)化問題的交替Tabu搜索算法( ATS)初始化Step1.同算法 1的 Step1.Step2. 搜索初始可行計劃與調度同算法 1的 Step2.Step3. 搜索最好計劃與調度1) 同算法 1的 Step3 的 1);2) 同算法 1 Step3的 2) , 除了以這里的“通過快速調度值 G( p, S* * * )”替換那里的“調用算法 2以搜索對于給定計劃3) 調用算法 2以搜索對于給定 p 的最好調度 S;* *

31、*計算相應 p 和 S的目標p的最好調度”;* * *4) 同算法5) 同算法6) 同算法1的1的1的Step3 的 3);Step3 的 4);Step3 的 5).輸出結果同算法 1的Step4.Step4.算法 3的計算復雜性是 o( ( n2+ n+ 0. 5n ( n - 1) SM-max ) PM- max )次.如果 n 足夠大,則算法 1的復雜性是 o( n ) ,而算法 3是 o( n2 ) .所以算法 3比算法 1快得多,但后者往往比前者獲得更好解. 如果 n 非常大,即使算法 3也無法在可接受的時間內獲得最優(yōu)或次優(yōu)提出串行 Tabu搜索法來求解式( 7) ( 10) .

32、解. 為此,3. 3 串行 Tabu搜索算法無疑 調度所做的個可行計劃;求解過程的一種有效方法是減少算法的計算復雜性,也就是減少為獲取最好總次數.為此,串行 Tabu搜索算法的基本思想是 1)從初始計劃開始尋找一2)從可行計劃開始,使用 Tabu搜索尋找最好的計劃; 3)對于最好的計劃,使用另一 Tabu搜索尋找最好的調度. 由于對計劃和調度依次使用 Tabu搜索,故稱為串行Tabu搜索算法.算法 4. 生產計劃與調度同時優(yōu)化問題的串行 Tabu搜索算法( S TS)Step1. 初始化同算法 1的 Step1.Step2. 搜索可行計劃同算法 1的 Step2,除了以這里的“調用算法 5以確

33、定相應于 p的調度”替換那里的“調用算法 2以搜索給定計劃 p 的可行調度”和以這里的S 替換那里的 S* * .6 期嚴洪森等: 汽車裝配車間生產計劃與調度的同時優(yōu)化方法917搜索最好計劃Step3.同算法 1的 Step3,除了以這里的“調用算法 5以確定相應于 p的調度”替換那里的“調用算法 2以搜索對于給定計劃 p 的最好調度” ,以這里的 S 替換那里的 S* * 和以這里的 “轉 Step4”替換那里的“停止迭代并轉 Step4” .Step4. 搜索最好調度1) 設置 p=p- best,并調用算法 2以搜索相應于 p 的最好調度;G( p, S* * *best S* *bes

34、t2) 如果調度有,即) < G- best,則更新最好解 S-, G-G( p, S* *) .輸出結果Step5.同算法 1的Step4.這里 S 是由算法 5確定的一個調度.算法 5. 相應于給定計劃的調度確定算法Step1. 確定調度1) 對于給定計劃 p,依次按照最早交付期、最少批量等優(yōu)先規(guī)則,確定調度S;2) 通過快速調度,計算相應于 p和 S 的 G( p, S ) ;3) 如果 S 不可行,則置 SC- flag= 0,否則置 SC- f lag= 1;返回.Step2.算法 4的計算復雜性是 o( (n2+max )次.如果 n 足n ) P M- max+0. 5n(

35、 n - 1) S M-夠大,算法 4的復雜性同算法 3一樣都是 o( n2 ) .但是,使用算法 4從初始可行計劃開始搜索到最好計劃與調度要比使用算法 3少做 1+ 0. 5n ( n- 1) SM- max ( PM- max - 1)次因此,算法 4要比算法 3快,但后者往往比前者獲得更好解.在生產計劃與調度的同時優(yōu)化中,計劃的職能是確定每種汽車的裝配批量,調度的職能是確定每種汽車按什么樣的順序上線裝配.4舉例求解汽車裝配線生產計劃與調度同時優(yōu)化問題的Tabu搜索算法 ( E TS) ,交替Tabu 搜索算法( ATS)和串行 Tabu搜索算法( STS) ,以及求解式( 3) ( 6)

36、的分枝定界算法+ +V C已用5. 0編成軟件.借助于這些算法軟件,我們研究了汽車裝配線生產計劃與調度的同時優(yōu)化問題. 在下面的例子中,所有這四種算法軟件都在內存 128M 的 Pentium 450 PC 機上 Win 98環(huán)境中運行,并只考慮兩種汽車裝配線: 一種汽車裝配工位無緩沖區(qū),另一種有緩沖區(qū).每種裝配線同南京某汽車總裝廠的裝配線一樣都有 33個工位,并且有緩沖區(qū)裝配線的每個工位的虛擬緩沖區(qū)都有 3個存放位置(一個存放位置只能放一輛汽車).例 1. 考慮有準備有緩沖區(qū)隨機情況. 假定某班需要裝配 5種汽車,其產量分別為 4, 5, 14, 20, 5輛.計劃區(qū)間為一班( 480分)

37、.式( 7) ( 9)中的其它參數已經給定,其中裝配時間 tij是一個服從正態(tài)分布的隨量,方差為其均值的平方乘以 0. 002 5. 每個工位前后兩個故障之間的間隔和設備維修時間都服從指數分布. 第 j ( j= 1, 2, , 33)個工位的故障率 j為 1 /480,其維修率 j為 1 /2.算法參數 P T- size= 80, ST - size= 10, P M- max= 100, SM- max= 3.在 PC機上運行分枝定界算法軟件 3. 0秒后,我們獲得粗生產計劃為 x= ( 5, 6, 35, 20, 5) T ,其中第 i 個分量為第 i 種汽車的計劃產量.然后,以 x

38、為初始解,在 PC機上分別使用 E TS,自動化學報28 卷918A TS和STS軟件各做了 6次蒙特卡羅運行,獲得其結果的平均值如表 1所示.表中使用ET S軟件獲得的最好計劃是( 4, 7, 16, 19, 7) ,其中第 i 個分量為第 i 種汽車的計劃產量; 使用 ETS軟件獲得的最好調度為 4, 1, 5, 3, 2 ,其中第 i 個元素為調度中第 i 個位置的汽車類型.時間為每種算法的 6次蒙特卡羅運行的平均時間,且不包括讀參數和計算樣本值的時間 ( 23. 38秒 ) . ETS和 ATS的時間分別比 S TS長 22. 20倍和 1. 47倍. 但 ETS和A TS的最能指標且

39、分別比STS少14. 56% 和 13. 46% .表1 有準備有緩沖區(qū)隨機情況的蒙特卡羅運行結果平均值算法時間 (分)pbesS besG besET S ATS S TS( 4, 7,( 5, 8,( 5, 3,6, 9, 7)4, 9, 7)8, 2 , 7) 4, 5, 5, 5, 3, 2, 2, 4, 3, 2, 4, 345825477097067685 629 03 69例 2. 考慮無準備隨機情況,其它條件同例1.( 4, 5, 36, 20, 5) T.在 PC機運行分枝定界算法軟件 4. 0秒后,我們獲得粗生產計劃 x=以 x 為初始解,在 PC機上有無緩沖區(qū)兩種汽車裝配

40、線分別使用 ET S, ATS和 S TS軟件各做了 6次蒙特卡羅運行后,獲得了各自結果平均值. 其中時間為 0. 24 35. 24分.ET S和 ATS的時間平均比STS長9. 06倍和 1. 13倍. 但E TS和 ATS的最能指標且平均比 STS少 7. 41% 和 6. 21% .有緩沖區(qū)汽車裝配線的最區(qū)汽車裝配線少 5. 29% .例 3. 考慮無準備確定情況,假定某班需要裝配 10種汽車.能指標平均比無緩沖在 PC機上運行分枝定界算法軟件 11. 2秒后,獲得了粗生產計劃. 以該粗生產計劃為初始解,在 PC機上得了各自結果. 其中有無緩沖區(qū)兩種汽車裝配線分別運行 ETS, AT

41、S和 STS軟件后,獲時間為 0. 52 991. 10分.ETS和 AT S的時間平均比S TS長89. 60倍和 64. 96% .但 ETS和 AT S的最能指標且平均比 S TS少 3. 79% 和 1. 73% .有緩沖區(qū)汽車裝配線的最能指標平均比無緩沖區(qū)汽車裝配線少 3. 17% .例 4. 考慮無準備確定情況,假定某班需要裝配 30種汽車.在 PC機上運行分枝定界算法軟件 102. 2秒后,獲得了粗生產計劃.以該粗生產計劃為初始解,在 PC機上有無緩沖區(qū)兩種汽車裝配線分別運行 ATS和 STS軟件后,獲得了時間為 5. 32各自結果 ( E TS無結果,因無法在可接受的時間內獲得

42、最好解 ) . 其中482. 85分. AT S的時間平均比 S TS長 2. 64倍. 但 ATS的最能指標且平均比 STS少 4. 33% . 有緩沖區(qū)汽車裝配線的最能指標平均比無緩沖區(qū)汽車裝配線少 8. 52% .5結論本文研究了汽車裝配車間生產計劃與調度的同時優(yōu)化問題,著重討論了粗生產計劃的 生成方法、生產計劃與調度同時優(yōu)化問題的三種高級啟發(fā)式求解方法( ET S, ATS和 STS) , 并給出了它們的計算復雜性.開發(fā)了相應軟件. 借助這些軟件,用大量算例進行了比較研究, 結果表明:1)與傳統方法相比,本文方法的優(yōu)點是將 方法、 Tabu搜索和快速調度 有機地結合在一起,有效地解決了

43、汽車裝配車間生產計劃與調度的同時優(yōu)化問題個可行解;至少有一6 期嚴洪森等: 汽車裝配車間生產計劃與調度的同時優(yōu)化方法9192) ETS的問題求解速度最慢,但獲得的性能指標往往最好; STS的問題求解速度和獲得的性能指標正好與 ET S相反; 而 ATS則介于 E TS和 S TS之間;3) ET S適合求解小問題, AT S適合求解中規(guī)模問題, S TS適合求解大規(guī)模問題; 如果1 2求出可行計劃與調度作為問題的解;問題非常大,則建議使用算法 4的Step4) 具有隨機特性的汽車裝配線生產計劃與調度的同時優(yōu)化問題可用 E TS, ATS和 STS的蒙特卡羅運行求解;5) 如果可行,應采用具有虛

44、擬緩沖區(qū)的汽車裝配線,因為有虛擬緩沖區(qū)的性能指標往往比無緩沖區(qū)好.此外,本文的 ETS, ATS和 STS也可用于求解其目標函數和約束不同于式( 7) ( 10)的模型,以及其它行業(yè)(如家電等)裝配線的生產計劃與調度的同時優(yōu)化問題.這些算法已在汽車裝配車間生產計劃與調度的集成優(yōu)化系統中加以實現,并應用于南京某汽車總裝廠,產生了顯著效益.參 考 文 獻or job shop plann ng and sch edul ng Managemen t Science,992, 38( 8) 20Las serre J B An n eg ra ed22Yan H S An n erac on / pred c on approach o h erarch cal produc on plann ng and con rol w h delay n erac onequa ons Computer In teg rated Manufacturin g Systems ,997, 10( 4) 309 3203Yan H S, J ang Z J An n e