汽車裝配車間生產(chǎn)計劃與調(diào)度的同時優(yōu)化方法嚴(yán)

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

2、盡可能少并盡可能滿足需求的粗生產(chǎn)計劃. 然后在粗生產(chǎn)計劃的基礎(chǔ)上考慮裝配線的細(xì)節(jié) ,用 Tabu搜索法與快速調(diào)度相結(jié)合的三種不同啟發(fā)式算法使生產(chǎn)計劃與調(diào)度同時得到優(yōu)化 , 并給出了三種算法的復(fù)雜性 . 大量算例的比較研究表明了這些算法的有效性和適用性 .裝配車間 , 生產(chǎn)計劃與調(diào)度 ,混合整數(shù), 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)和教育部高等學(xué)校骨干教師資助計劃資助收稿日期2000 08 7收修改稿日期200 09 20自動化學(xué)報28 卷912prog ramming , Tabu search1引言在現(xiàn)行的生產(chǎn)

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

8、設(shè)一條裝配線共有 m 個裝配工位,計劃區(qū)間內(nèi)依據(jù)裝配訂單共需裝 n 種汽車且第 i 種汽車需 di輛.再將裝配線簡化為一個shop問題,且最優(yōu)計劃的目標(biāo)是最大限度地滿足Flo w需求并使各裝配工位的準(zhǔn)備成本和空閑時間盡可能少,則可建立求解最優(yōu)粗生產(chǎn)計劃的混合整數(shù)模型如下: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ū)間內(nèi)需裝配的汽車種類數(shù); m 為

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

10、 cj為與第 j 個裝配工位閑置有關(guān)的成本系數(shù); tij為第 j 個裝配工位裝配第 i 種汽車所需要的時間; tij為第 i 種汽車在第 j 個裝配工位上的準(zhǔn)備時間; ( c)+ 為 max ( 0, c ) .式( 1)和( 2)的混合整數(shù)非線性n模型可轉(zhuǎn)化為混合整數(shù)線性模型如下: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且為整數(shù); yi

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

12、較為可行的辦法是使用基于可變時間流的快速調(diào)度.此處快速的含義是不要圖形顯示,僅僅通過快速計算給定調(diào)度的性能指標(biāo).至于最優(yōu)計劃與調(diào)度的迭代選擇問題則由基于 Tabu搜索的三種不同啟發(fā)式算法來解決.3. 1Tabu搜索算法為節(jié)省汽車裝配準(zhǔn)備時間,同種汽車集中裝配,不分割成多個裝配任務(wù),并在調(diào)度時僅占用一個排序位置.參照式( 1)和( 2) ,則求解汽車裝配車間生產(chǎn)計劃與調(diào)度同時優(yōu)化問題的數(shù)學(xué)模型可描述如下: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且為整數(shù), fj ( 9)( 10)0, j = 1, 2, , m式中 ( S , i )為 n種汽車或其中部分通過裝配線的順序 (調(diào)度) S中的第 i 個位置所對應(yīng)的汽車

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

15、權(quán)系數(shù); q為各裝配工位負(fù)荷均衡權(quán)系數(shù).Tabu 搜索是由 Glov er7, 8 提出的用于獲取組合最優(yōu)化難題近似解的一種高級啟發(fā)式方法. 在應(yīng)用 Tabu搜索法求解生產(chǎn)計劃與調(diào)度同時優(yōu)化問題( 7) ( 10)之前,首先介紹兩個概念,即相鄰計劃和相鄰調(diào)度. 設(shè)計劃 = ( 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對于調(diào)度,我們定義僅交換中的兩個元素而形成的調(diào)度為相鄰于的調(diào)度.自動化學(xué)報28 卷914不失一般性,設(shè)初始調(diào)度 S0 中共包含三種汽車,即 S0= a ,b , c ,則依定

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

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

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

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

21、p* ,* * *S果1且) ; 否則丟棄 p; 如果計劃Tabu 表中 P T- li st中SC- flag=*的計劃個數(shù)少于 P T- size,將 p 加到 P T - list的頂部; 如此重復(fù),直至做完 p 的所有相鄰計劃;p* p* , G( p* * , S* *) G( p*, S* *p* * 不在3) 作一次計劃移動,設(shè)置)且如果P T -p* *list中則將加到li st的頂部; 如果li st中的計劃個數(shù)>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) 更新到目前為止所作的計劃移動次數(shù)1; 如果P M- ctr>P M- max ,則停止迭代并轉(zhuǎn) Step4,否則轉(zhuǎn) Step3的 1).輸出結(jié)果Step4.輸出 P-bestbest和 G- best.S-6 期嚴(yán)洪森等: 汽車裝配車間生產(chǎn)計劃與調(diào)度的同時優(yōu)化方法915這里 M- big 為一個很大的數(shù); SC- f lag 為對于給定計劃 p是否存在滿足約束( 8) ( 10)的p*調(diào)度的標(biāo)志, SC- f lag= 1

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

24、定初始調(diào)* *S* *S度 S0 ,并置= S0 ,= S0 ,SC- f lag=0;* *S2) 通過快速調(diào)度,計算相應(yīng)于 p 和 S0 的性能指標(biāo) G( p, S0 ) ,并置 G( p,) =G( p, S0 ) ,如果 S0 可行(即滿足約束( 8) ( 10) ) ,置Step3. 調(diào)度搜索SC- f lag=1.* *S1) 生成一個相鄰于緊前相鄰調(diào)度集中的最好調(diào)度的所有可能調(diào)度集, 并置G( p, S*) = M-big;2) 對于該集合中的一個調(diào)度 S,如果 S 不在list中,則通過快速調(diào)度,計算調(diào)S T-度性能指標(biāo) G( p, S ) , 并更新當(dāng)前相鄰集中的最好調(diào)度 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; 如此重復(fù),直至做完 S* * 的所有相鄰調(diào)度;*S S, G( p, S* ) G( p, S* ) ,并將加到* *S3) 作一次調(diào)度移動,設(shè)置ST - list的頂部,如果 ST - list中的調(diào)度個數(shù)> S T- size,則從 S T- list的底部刪除一個最老的調(diào)度.,即

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

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

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

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

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

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

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

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

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

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

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

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

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

39、分別比STS少14. 56% 和 13. 46% .表1 有準(zhǔn)備有緩沖區(qū)隨機情況的蒙特卡羅運行結(jié)果平均值算法時間 (分)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. 考慮無準(zhǔn)備隨機情況,其它條件同例1.( 4, 5, 36, 20, 5) T.在 PC機運行分枝定界算法軟件 4. 0秒后,我們獲得粗生產(chǎn)計劃 x=以 x 為初始解,在 PC機上有無緩沖區(qū)兩種汽車裝配

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

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

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

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

44、擬緩沖區(qū)的汽車裝配線,因為有虛擬緩沖區(qū)的性能指標(biāo)往往比無緩沖區(qū)好.此外,本文的 ETS, ATS和 STS也可用于求解其目標(biāo)函數(shù)和約束不同于式( 7) ( 10)的模型,以及其它行業(yè)(如家電等)裝配線的生產(chǎn)計劃與調(diào)度的同時優(yōu)化問題.這些算法已在汽車裝配車間生產(chǎn)計劃與調(diào)度的集成優(yōu)化系統(tǒng)中加以實現(xiàn),并應(yīng)用于南京某汽車總裝廠,產(chǎn)生了顯著效益.參 考 文 獻(xiàn)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