混合式裝配線(xiàn)平衡問(wèn)題.

1、1A new heuristic method for mixed model assembly line balancing problem 一種針對(duì)混合式裝配線(xiàn)平衡問(wèn)題的新啟發(fā)式演算法2Introductionu因應(yīng)市場(chǎng)競(jìng)爭(zhēng)，客製化商品增加 以汽車(chē)工業(yè)為例：顧客可以用基本的模型再加上自己的喜好來(lái)選擇自己喜歡的車(chē)子，如：要不要安全氣囊，要不要DVD等。=混合式裝配線(xiàn)平衡問(wèn)題混合式裝配線(xiàn)平衡問(wèn)題3IntroductionuTOYOTA應(yīng)用JIT系統(tǒng)的成功=生產(chǎn)順序中資源的使用率有最小的變異u此篇paper中問(wèn)題的目標(biāo)在於最小化順序中零件消耗率的變化。Kubisk(1993)稱(chēng)此為生產(chǎn)率變化問(wèn)題

2、(product rate variation problem)4The mixed model assembly line formulationu假設(shè)在一條裝配線(xiàn)上有N種模型(model or units)可以生產(chǎn)，模型中有C種零件可供選擇使用。以下是本篇出現(xiàn)的符號(hào)意義ndi：代表model i 的需求量，ncj,i：代表一個(gè)model i 所需要零件j的數(shù)目 (technical matrix)nD：代表總需求量nTj：代表所有的順序(sequence)中所需的part j總數(shù)目nrj：期望零件消耗率nxi,k：為決策變數(shù)，代表model i在一個(gè)特定的順序中前k 個(gè)位置的累積排列次數(shù),

3、.,1Ni,.,1and,.,1CjNiNiidD15The mixed model assembly line formulationu依照以上的定義可得 (1)u為了平滑的生產(chǎn)零件，於是期望零件消耗率為 (2)u因?yàn)橛辛慵墓┙o與消耗，所以試著平衡順序中消耗的零件，在前k個(gè)位置的零件j消耗數(shù)目為krj (3)u在個(gè)特定順序中位置k的實(shí)際累積消耗零件j的數(shù)目為 (4)NiijijcdT1,DTrjjNiijkicx1,model i 下所需的零件j的數(shù)目model i在一個(gè)特定的順序中前k個(gè)位置的累積排列次數(shù)6The mixed model assembly line formulation

4、u目標(biāo)式可以用 與krj的差來(lái)表示如下 (5) Fj為凸函數(shù)，當(dāng)Fj(0)=0為最小值，目標(biāo)式可表示如下 (6)Niijkicx1,)(Minimize1,D1k1NijijkiCjjkrcxF D1k121,)(minSDQCjNijijkikrcxSum of the quadratic differences7The mixed model assembly line formulationu基於上式，可以將混合式裝配線(xiàn)平衡問(wèn)題表示如下 (7a) (7b) (7c) (7d) (7e) xi,k為整數(shù),.,1,.,1 0 ,.,1,.,1 0 ,.,1,.,1 1 ,.,1 s.t)(S

5、DQmin ,1,1,.,1,D1k121,DkNidxDkNixxDkNixxDkkxkrcxikikikikikiNikiCjNijijki 8The mixed model assembly line formulation goal chasing methoduModen(1983)將此方法實(shí)施在Toyota來(lái)解決平衡裝配線(xiàn)混合模型問(wèn)題並將此法稱(chēng)為目標(biāo)追蹤法(goal chasing method)u因?yàn)闉椴煌哪繕?biāo)函式，所以將目標(biāo)追尋法作些微的變化且不影響必須的點(diǎn)，步驟如下nStep 1.令nStep 2.選擇個(gè)model l可以最小化成本，此時(shí)xl,k-1 D就結(jié)束運(yùn)算，反之回到

6、Step 2u目標(biāo)演算法可以解決多零件、大量需求等大規(guī)模的問(wèn)題而且只花很少的時(shí)間就可以得到結(jié)果。此法主要的缺點(diǎn)在於在如果有些model的選擇比較特殊會(huì)被留到後期才會(huì)生產(chǎn)這樣產(chǎn)出的變異會(huì)很大。*1, when 1lixkiotherwise 1, kix,.,1Nl10Existing improvement SymmetryuBautista,Conpanys,and Corominas(1996)提出三種方法可以改善混合式裝配線(xiàn)平衡問(wèn)題的方法。nSymmetry：因?yàn)槟繕?biāo)追蹤法是對(duì)稱(chēng)的即可以應(yīng)用在順序中的開(kāi)始或結(jié)尾的結(jié)果不會(huì)有影響。所以從起始點(diǎn)與最終點(diǎn)增加一個(gè)一個(gè)的unit來(lái)建立一個(gè)順序，第

7、一次循環(huán)決定第一個(gè)位置，第二次循環(huán)決定最後一個(gè)位置。而且bad units不會(huì)累積在順序中的後面並且此改善方法計(jì)算上的負(fù)荷不會(huì)太大。此法的缺點(diǎn)在於poor units似乎會(huì)被放在順序的中央，所以此法雖然改善了問(wèn)題卻也生產(chǎn)出另一個(gè)問(wèn)題。11Existing improvement Horizon(2-step)nHorizon(step-2)：為了降低”short-sightedness”，所以每次循環(huán)不只考慮一個(gè)位置。於是測(cè)試兩個(gè)一次考慮兩個(gè)位置的模型，計(jì)算此兩個(gè)模型所增加的成本和比較所有的成本組合。改變目標(biāo)演算法的step 2。此法的缺點(diǎn)在於計(jì)算的複雜度增加，當(dāng)增加大量的選擇數(shù)時(shí)運(yùn)算時(shí)間會(huì)增

8、加許多。在極端的狀況下，當(dāng)考慮所有順序的第一個(gè)位置時(shí)，此法會(huì)列舉所有可能順序來(lái)找出最佳解。 12Existing improvement Rate-preservingnRate-preserving：使用目標(biāo)追蹤法在一些循環(huán)計(jì)算後會(huì)累積poor units而剩下來(lái)的units結(jié)構(gòu)與原本的結(jié)構(gòu)相比會(huì)變成有更多的poor units。Rate-preserving法試著讓結(jié)構(gòu)與原本的結(jié)構(gòu)相同。Bautista認(rèn)為此法搭配step-2會(huì)減少5%的成本且選擇unit上使得剩下來(lái)的組成結(jié)構(gòu)與一開(kāi)始的組成結(jié)構(gòu)差距變小。此法計(jì)算負(fù)荷比horizon小，比Symmetry大。u以上三種方法可以同時(shí)使用以求得

9、較佳的結(jié)果13Variance methodu目標(biāo)追蹤法基本的問(wèn)題在於good units在早期的循環(huán)消耗太快而bad units會(huì)被留到較晚的循環(huán)來(lái)處理。然而並沒(méi)有個(gè)量化的指標(biāo)來(lái)衡量模型的適合度，所以存在以下兩個(gè)問(wèn)題n1.什麼是good units和什麼是bad units？n2.要如何避免此現(xiàn)象？藉由回答上面兩個(gè)問(wèn)題的過(guò)程，發(fā)展出Variance。在一個(gè)特定的模型中將零件結(jié)構(gòu)接近期望消耗率的units稱(chēng)作good units。使用model variance vi來(lái)衡量 (9) Cjijjicrv12,)(14Variance methodu當(dāng)模型有較小的vi代表是good units。對(duì)

10、一個(gè)特定的composition of the units也定義total composition variance如下 (10) 如果composition有小的composition variance則可能有較多的good units。Niiivdt115Variance methodu目標(biāo)追蹤法試著找出unit在最低成本下的適合位置且不考慮未來(lái)順序。我們結(jié)合composition variance當(dāng)做剩下composition的機(jī)會(huì)成本當(dāng)作總成本?，F(xiàn)有的成本與機(jī)會(huì)成本是相衝突的，所以要在兩者之間做trade-off。Variance法是改變目標(biāo)追蹤法的step 2而來(lái)n選擇 可以最小化平

11、方成本 (12)此時(shí)Zi,j= w為機(jī)會(huì)成本的折扣因子lkldx1, NiCjijjlikiiCjNijijlikiNlcrzxdwkrczxl112,1,112,1,.,1*)()( )(min arg)( otherwise 01 when 1i,.,1Nl16Variance methodu這個(gè)啟發(fā)式演算法解決現(xiàn)有目標(biāo)追蹤法的問(wèn)題，而且此啟發(fā)式演算法可以與現(xiàn)存的改進(jìn)方法一起使用，並且計(jì)算上不會(huì)造成負(fù)荷。17Numerical examples and experimentsu令N=5，C=4，每個(gè)模型i的technical matrix(cj,i)和demand(di)如下，意思是model i所需的part j數(shù)量18Numerical examples and experimentsuTable 2代表不同啟發(fā)式演算法的結(jié)果 Variance與2-step/variance 的產(chǎn)出結(jié)果優(yōu)於其他的 演算法。如果我們改變需求 為90 80 25 15 70，總需求 變?yōu)?80，則結(jié)果與計(jì)算時(shí) 間如下頁(yè)19Numerical examples and experimentsu由上表可知variance與原本的目標(biāo)追尋法相比的結(jié)果較好且所增加的時(shí)間不多20結(jié)論與感想u在這篇paper中提出了許多改進(jìn)