準(zhǔn)時(shí)生產(chǎn)方式下混流裝配線的調(diào)度問(wèn)題

1、準(zhǔn)時(shí)生產(chǎn)方式下混流裝配線的調(diào)度問(wèn)題第 3卷第 4期 管 理 科 學(xué) 學(xué) 報(bào) Vo】3 No4 準(zhǔn)時(shí)生產(chǎn)方式下混流裝配線的調(diào)度問(wèn)題。 苧 韓文秀 ，呈查查! (1天津大學(xué)系統(tǒng)工桓麗禿。 津300072；2吳磊 辜院天津3222) 摘要：混流裝配線的調(diào)度問(wèn)題是JIT生產(chǎn)方式中的一個(gè)重要問(wèn)題本文建立了多級(jí)混流裝配線 的調(diào)度模型，其目標(biāo)是使不同生產(chǎn)級(jí)上各零部件的消耗量盡可能保持均勻，并用遺傳算法和模 擬退火進(jìn)行求梓試驗(yàn)表明：遺傳算法和模擬退火算法的求解質(zhì)量比“目標(biāo)追隨法”有所提高 關(guān)鍵詞：準(zhǔn)時(shí)生產(chǎn) 逸流裝配踐l_遺傳算法 模擬退火算法 中圖分類號(hào)：F273 文獻(xiàn)標(biāo)識(shí)碼 ：A 文章編號(hào)：1007 980

2、7(2000)04 002306 0 引 言 的調(diào)度問(wèn) j 法求解單級(jí)混 混流裝配線是 IT生產(chǎn)方 式的具體應(yīng)用之 一，在國(guó)外許多制造企業(yè)已廣泛采用，它能在不引 起大的產(chǎn)品庫(kù)存的條件下滿足用戶的多樣化需 求所謂混流裝配線，有時(shí)也特指混合車型組裝 線，是指在一定時(shí)間內(nèi)，在一條生產(chǎn)線上生產(chǎn)出多 種不 同型號(hào) 的產(chǎn)品產(chǎn)品的品種可以隨顧客需求 的變化而變化例如，在豐田汽車廠的Coronas生 產(chǎn) 線上 ，可以生產(chǎn) 4000多種類型的汽車 ，每種車 型的發(fā)動(dòng)機(jī)、變速器、加速器、空調(diào)、車門或其它部 件不同8小時(shí)的班必須生產(chǎn) 250輛sedan，125輛 hardtop，125輛 wagon當(dāng)前，我國(guó)汽車廠

3、家基本 上仍以單一車型為主，但可以預(yù)料在不久的將來(lái) 必然會(huì) 向多種車型發(fā)展 ，開(kāi)發(fā)復(fù)雜 的混合車型組 裝線勢(shì)在必行 很多學(xué)者從不同的角度研究了混流裝配線的 調(diào)度問(wèn)題文：1對(duì)混合車型組裝線中的車輛及 工人的移動(dòng)軌跡進(jìn)行模型化，分析了混流裝配線 上車型調(diào)度問(wèn)題的幾種目標(biāo)函數(shù)，并對(duì)相應(yīng)的算 法進(jìn)行了評(píng)價(jià)文E2綜述了對(duì)混流裝配線調(diào)度 問(wèn)題的研究狀況，指出目前的啟發(fā)式算法很難滿 足要求文 3研究了在IT環(huán)境下使混流裝配線 停止時(shí)間最小的問(wèn)題，并建立了相應(yīng)的模型文 4從物流管理的角度分析了一家汽車裝配廠生 收稿 日期：1999-09一Z9；修訂 日期 ：Z0O0 09 28 作者簡(jiǎn)升：趙 偉f1971一)

4、男河南人博士生 流裝配線的調(diào)度問(wèn)題文 6證明了混流車型組 裝線調(diào)度問(wèn)題的最優(yōu)解具有循環(huán)排序的形式，更 進(jìn)一步，在每個(gè)循環(huán)中生產(chǎn)的每種車型數(shù)是每種 車型的需求數(shù)在整個(gè)車型需求總數(shù)中所占比例的 倍數(shù)，并指出，尋找有效的混流裝配線調(diào)度算法是 提高該系統(tǒng)性能的關(guān)鍵要素之一本文著重研究 多級(jí)混流裝配線的調(diào)度問(wèn)題 1 問(wèn)題描述 混流裝配線的調(diào)度問(wèn)題主要解決裝配線以及 整個(gè)生產(chǎn)系統(tǒng)的生產(chǎn)負(fù)荷均衡問(wèn)題 ，以避免系統(tǒng) 產(chǎn)生瓶頸典型的汽車裝配線包括控制板裝配 ，頭 燈裝配，車輪裝配，車窗裝配，車座裝配，機(jī)械結(jié)構(gòu) 裝配等工序由于不同車型對(duì)不同零部件的需求 不同，因此對(duì)各種零部件的消耗就不同，各工位根 據(jù)車型的不同在

5、需要的時(shí)刻生產(chǎn)或組裝不同的零 部件 圖1為JIT生產(chǎn)環(huán)境下混流組裝線的直觀描 述如圖 1所示生產(chǎn)線上正在組裝兩輛 B型車， 一 輛 C型車 ，一輛A型車正要進(jìn)入組裝線子裝配 單元根據(jù)進(jìn)入組裝線車型的不同，向前一工序取 出適當(dāng)?shù)牧悴考捎诓煌悴考男枨箅S車型 的不同而不同，因此很難保證所有的單元生產(chǎn)平 Jfb 3 1 午 F 維普資訊 /.cqvip4 24 管 理 科 學(xué) 學(xué) 報(bào) 2000年 12月 順化并保持低的在制品庫(kù)存在 兒T生產(chǎn)環(huán)境下， 這種情況會(huì)進(jìn)一步惡化，因?yàn)槊康拦ば蜿U幾乎段 有在制品庫(kù)存，只有在下道工序需要時(shí)，才進(jìn)行生 產(chǎn)因此 ，總裝線 的調(diào)度對(duì)整個(gè)生產(chǎn)系統(tǒng)的負(fù)荷均 O 衡和

6、JIT目標(biāo)的實(shí)施具有重要的影響 用以下例子來(lái)進(jìn)一步對(duì)問(wèn)題進(jìn)行直觀的描 述假定有四種車型A，B，c，D要進(jìn)行裝配，對(duì)這 四種 車型的需求量如表 1所示 園圈 圓 圓 圈 千 裝 于裝 圖 l JIT環(huán)境下的總裝線 表 l 四種車型的需求斂 恩裝線 車 型 需 求 每個(gè)生產(chǎn)循環(huán)中生產(chǎn)的各種車型數(shù) A 2000 2 B 3000 3 C 4000 4 ，) 2000 2 總 計(jì) ll000 II 由于對(duì)四種車型的需求比是2比3比4比2 按照生產(chǎn)比例數(shù)法來(lái)確定數(shù)量節(jié)拍，則一個(gè)生產(chǎn) 循環(huán)可以定義為生產(chǎn)兩輛A型車，三輛B型車，四 輛 C型車 ，兩輛 D型車在一個(gè)生產(chǎn)循環(huán) 中，一個(gè) 可 能 但 不 一 定

7、為 晟 好 的 車 型 組 裝 順 序 為 ： AABB B_CCCCD-D對(duì)各級(jí)子裝配需求的 不同，導(dǎo)致不同的調(diào)度結(jié)果(即排序)對(duì)生產(chǎn)有不 同的影響表2為本例中各車型對(duì)子裝配的需求 衰 2 各車型需求的子裝配 每個(gè)生產(chǎn)循環(huán)中生產(chǎn) ：F 裝 配 車 型 的每種車型的數(shù)量 X 2 3 A 2 l0 0 5 日 3 l 4 C 4 l l 7 O D 2 0 4 l 每個(gè)生產(chǎn)循環(huán)中需要的子裝配數(shù) 30 7g 24 為了簡(jiǎn)化問(wèn)題的表達(dá)，假定此時(shí)只有兩種車 型 A(每生產(chǎn)循環(huán) 2輛)和c(每生產(chǎn)循環(huán)4輛)需 維普資訊 /.cqvip 第 1期 趙 偉等：準(zhǔn)時(shí)生產(chǎn)方式下混流裝配線的調(diào)度問(wèn)題 25一 要裝

8、配 ，車型 C需要 17個(gè)子裝配操作 X ，而車型 不需要子裝配操作 x 假定組裝線上車型的調(diào) 度結(jié)果為ccccA A，則在生產(chǎn)循環(huán)的開(kāi)始階 段需要進(jìn)行174=48個(gè)子裝配x 操作；然后， 在接下來(lái)的生產(chǎn)中，由于沒(méi)有對(duì)它的需求，進(jìn)行子 裝配操作 的工人將處于“休息”狀態(tài)，這嚴(yán)重違 反了JIT生產(chǎn)方式中“生產(chǎn)平順化”的 目標(biāo)因此， 合理安排總裝線上車型的調(diào)度順序是保證 J1T目 標(biāo)實(shí)現(xiàn)的重要手段當(dāng)然，除了尋找好的調(diào)度方案 外，也有其它解決方法例如在需要的時(shí)候分配盡 量多的工人；或者在空閑的時(shí)候進(jìn)行生產(chǎn)，保持一 定的庫(kù)存 ，在需要的時(shí)候再?gòu)膸?kù)存中取出；可以看 出，這兩種方法都不十分令人滿意因此，在

9、總裝 線的調(diào)度問(wèn)題中，需要找到一種調(diào)度方案，盡可能 使所有的子裝配和部件生產(chǎn)的變化率最小，以保 障生產(chǎn)平順化的實(shí)施 J，從而最終達(dá)到準(zhǔn)時(shí)生產(chǎn) 的目標(biāo) 2 數(shù)學(xué)模型 混流裝配過(guò)程由一系列不同生產(chǎn)級(jí)上的子裝 配過(guò)程組成假定有三個(gè)生產(chǎn)級(jí) ，一個(gè)特定的生產(chǎn) 級(jí)用h表示，其中h=1，2，?，L最高的生產(chǎn)級(jí)是 第 1級(jí)第 h生產(chǎn)級(jí)上的不同子裝配工序(或產(chǎn) 品)數(shù)用 表示 對(duì)于多級(jí)裝配類型的產(chǎn)品結(jié)構(gòu)可用一有向圖 G(V，E)表示， 表示節(jié)點(diǎn)(或項(xiàng)目)的集合，即裝 配或生產(chǎn)工序集 ；有向弧集合 E表示裝配工序之 間聯(lián)系 的集合，弧 ( ， ， )表示裝配項(xiàng) 目 需要裝配項(xiàng)目n 假定每生產(chǎn)級(jí)上的節(jié)點(diǎn)按照 1，2

10、，?的拓?fù)漤樞蚓幪?hào) ，如圖2所示 ，定義如 下概念 ： 圍 2 子裝 配結(jié)構(gòu)拓?fù)?圖 定義l 裝配項(xiàng)目之間的關(guān)聯(lián)系數(shù)為裝配項(xiàng) 目 “需要裝配項(xiàng) 目 + 的數(shù)量，表示為Rl在 圖 2中，R? = 1，Rl2l= 3-1lR !一 2，R1 一 4， R = 2等 定義 2 與第 h生產(chǎn)級(jí)上裝配項(xiàng)目i直接相 連的后序裝配項(xiàng)目的集合為 h生產(chǎn)級(jí)上 i節(jié)點(diǎn)的 緊鄰后序集合，表示為 ( ，h)，h> 1在圖 2中， A(1，3)= 1j，A(2，3)一 1)， (1，2)一 1j， (4，3)= 3)等 定義3 與第 h生產(chǎn)級(jí)上裝配項(xiàng) 目i直接相 連的前序裝配項(xiàng)目的集合為 h生產(chǎn)級(jí)上 的緊鄰 前序

11、集合，表示為 B(i， )，h<L 1在圖 2中， B(1，1)= 1，2)，B(2，1)一 3，4)， (2，3)= 4， 5)等 第 3生產(chǎn)級(jí) - 產(chǎn)埡 以上定義均對(duì)某種車型而言，不同車型則相 應(yīng)的數(shù)值有所不同 假定b 代表每組裝一輛車型 在第1生產(chǎn)級(jí) 上需要子裝配J的數(shù)量，J=1，2，?n 則b 一 二L >：b R ， 一 1，2，? ，表示每組裝一輛車 j-l 型i在第 2生產(chǎn)級(jí)上需要子裝配 ， 的數(shù)量由于 J1T為拉式生產(chǎn)系統(tǒng)，每一級(jí)上每一個(gè) 子裝配的 消耗數(shù)量由第一級(jí)上的生產(chǎn)調(diào)度決定只要最后 裝配線上的調(diào)度結(jié)果確定，利用產(chǎn)品裝配拓?fù)潢P(guān) 系圖，很容易確定各生產(chǎn)級(jí)上子裝配

12、的消耗量 本文采用豐田公司提出的調(diào)度 目標(biāo)函數(shù)，即 在組裝所有車輛的過(guò)程中，所確定的組裝順序應(yīng) 使各零部件的使用速率均勻化，建立模型如下 維普資訊 /.cqvip 26 管 理 科 學(xué) 學(xué) 報(bào) 2000年 12月 min(kaj 一 一fl1,ia) 1 =1 h一】 J一 】 (1) 目標(biāo)函數(shù)式(1)表示調(diào)度結(jié)果應(yīng)使不同生產(chǎn) 級(jí)上每 一個(gè)零 部件 的實(shí) 際使 用速 率 (6 + )和理想使用速率( )之間的差別最小 化 其中，各符號(hào)含義如下： i- 車型數(shù)的標(biāo)號(hào) 一 需要裝配的車型數(shù) _ _ _ 某生產(chǎn)級(jí)上子裝配的標(biāo)號(hào) 第 生產(chǎn)級(jí)上的不同子裝配工序(或 產(chǎn)品)數(shù) 車型調(diào)度結(jié)果(即排序位置)的

13、標(biāo)號(hào) ，J一一在一個(gè)生產(chǎn)循環(huán)中需要組裝的各種車 型的總和 L一 生產(chǎn)級(jí)數(shù)，某 一個(gè)特定的生 產(chǎn)級(jí)用 h 表示 ，h一 1，2?，L 在一個(gè)生產(chǎn)循環(huán)中車型 的數(shù)量 b 生產(chǎn)每輛 i車型需要第 h生產(chǎn)級(jí)上子 裝配 的數(shù)量 db 一 _三 ，表示第h生產(chǎn)級(jí)上零部件J的 理想使用速率 f 如果車型 i在調(diào)度中的k位置 【0 否則 = 在組裝線調(diào)度中前k一1輛車總共 消耗h生產(chǎn)線上零部件J的數(shù)量和 8 = 0? + b ，并且 & k一 0 如果不同型號(hào)的產(chǎn)品消耗零部件的種類大致 相同，由于調(diào)度的目標(biāo)是使所有生產(chǎn)級(jí)上零部件 的消耗量保持均勻，則原問(wèn)題可簡(jiǎn)化為單級(jí)混流 調(diào)度問(wèn)題此時(shí)，問(wèn)題可描述為

14、D n min( 一 一 一，) (2) l ，一I 式中各符號(hào)含義如下： m 裝配線上需要的零部件種類總數(shù) 6 一 生產(chǎn)每輛 i車型需要零部件 的數(shù)量 )：d,b ， = - 一零部件J的理想使用速率 在組裝線調(diào)度中前k一1臺(tái)車消耗 零部件 ，的數(shù)量和 pb= 0H 十 z 并且 = 0 其它符號(hào)含義同上 3 算法描述 上述問(wèn)題為組臺(tái)優(yōu)化問(wèn)題，在多項(xiàng)式時(shí)間內(nèi) 不可能得到最優(yōu)懈因此，在實(shí)踐中人們采用各種 啟發(fā)式方法豐田汽車公司是首先采用混流生產(chǎn) 方式的企業(yè)，并對(duì)這種生產(chǎn)方式進(jìn) 行了大量的研 究他們研究出一種啟發(fā)式算法“目標(biāo)追隨法 (goal chasing algorithm，簡(jiǎn)稱 GCA算法

15、)”，在實(shí) 踐中已廣泛采用這種算法實(shí)際上是一種貪婪算 法，算法的每一步均從當(dāng)前可選擇策略中選取使 目標(biāo)函數(shù)值增加最少的策略即在確定第n+1臺(tái) 車輛的車型時(shí)，如有多種車型可供選擇，則從中選 擇一種車型，使第 +1臺(tái)車輛組裝時(shí)各零部件的 使用速率最為均勻每步只考慮當(dāng)前的狀態(tài)，而不 考慮全局狀態(tài)，因此這樣得到的結(jié)果常常為局部 最優(yōu)懈本文使用文5中的數(shù)據(jù)，用遺傳算法和 模擬退火算法與該算法進(jìn)行了對(duì)比實(shí)驗(yàn)試驗(yàn)數(shù) 據(jù)如下表 表3 各車型的翱料單和需求的子裝配數(shù) 每個(gè) 生產(chǎn)循環(huán)生產(chǎn)的 子 裝 配 車 型 各種車型數(shù) X 2 Y3 E 8 q l 0 A 5 0 17 g 0 4 0 0 18 0 O B 2

16、 l2 13 0 l1 0 O 0 1 17 17 C 3 2 4 0 19 0 l2 6 4 9 3 D 3 O 1j 0 19 0 l5 9 9 0 6 E 3 O 0 5 7 8 10 4 0 0 O 每個(gè)生產(chǎn)循環(huán)需求的子裝配數(shù) 3O l68 60 1 57 44 l11 j7 13l 6l 6l “目標(biāo)追隨法”得到的結(jié)果為CACAE D A E DAC EAD，目標(biāo)函數(shù)值為 3293 維普資訊 /.cqvip 第4期 趙 偉等：準(zhǔn)時(shí)生產(chǎn)方式下混流裝配線的調(diào)度問(wèn)題 一 27 31 遺傳算法 本研究中染色體采用字符編碼，如用“A”代 表“A”型車選擇算子采用比例選擇交叉算子采 用部分映射雜

17、交，即在兩個(gè)父代向量上隨機(jī)選取 一 段，利用兩個(gè)父代向量在所選段內(nèi)相應(yīng)位的對(duì) 應(yīng)來(lái)定義一系列交換，這些交換可在每個(gè)父代向 量上分別執(zhí)行如： 父代 l AA B C D EE C DA BA CA E D 父代 2 B E D A c AE D BC A D A E C A 其中對(duì)應(yīng)對(duì)是 ：E：E，C：D，D：B，經(jīng)部分映射雜 交后生成如下兩個(gè)有效的排列 ： 父代 1 A A D C C EE D BA B A C A E D 父代 2 B E B A D A E C DC A D A E C A 采用任意交換一個(gè)染色體上兩個(gè)位來(lái)實(shí)現(xiàn)變 異算子 實(shí)驗(yàn)參數(shù)：交叉概率 07變異概率 002，種 群太

18、小 2o，最大代數(shù) 1500，用遺傳算法得到的車 型排序結(jié)果為 C A D-B E ADEACA BEDAC，相應(yīng)的 目標(biāo) 函數(shù)值為 3073與 GCA 算法相比改進(jìn) 7 32 模擬退火算法 換策略一種是二鄰域變換策略，即隨機(jī)地交換兩 種車型的位置；第二種是逆序策略，即任意選擇兩 個(gè)位置，把兩個(gè)位置之間的車型按原來(lái)順序的逆 序重新排列 實(shí)驗(yàn)參數(shù)：初始溫度 T = lO，溫度下降率 一 099，終止溫度 T = 001，馬爾可夫鏈長(zhǎng) L 一 20在二鄰域變換策略下，得到的排序結(jié)果為 CADEBA D E A C BEAD-AC，目標(biāo) 函 數(shù)值為2 8598，與GCA算法相比改進(jìn) l5；在逆 序

19、變 換 策 略 下， 得 到 的 排 序 結(jié) 果 為： C A D E BADEACCAB DAE，目標(biāo) 函 數(shù)值為 3 1 62，與GCA算法相比改進(jìn) 4 為進(jìn)一步研究各算法求解混流生產(chǎn)線調(diào)度問(wèn) 題的能力，還以隨機(jī)產(chǎn)生的問(wèn)題對(duì)各算法進(jìn)行了 測(cè)試這里隨機(jī)產(chǎn)生 8類問(wèn)題，每類問(wèn)題為以下條 件的組合：車型數(shù)為5或 lO個(gè)，子裝配數(shù)為 lo或 20，部件數(shù)為12o上均勻分布的隨機(jī)數(shù)，零部 件共享比例為 O一20 或 040之間均勻分布的 隨機(jī)數(shù)每類各產(chǎn)生 20個(gè)問(wèn)題，共有 160個(gè)問(wèn)題 各算法試驗(yàn)參數(shù)仍如前所述 以豐田GCA算法為基準(zhǔn)，模擬退火實(shí)驗(yàn)結(jié)果 對(duì) 于模擬退火算法本文宴驗(yàn)了兩種鄰域變 如表

20、4所示，遺傳算法試驗(yàn)結(jié)果如表 5所示 表 4 實(shí)驗(yàn)結(jié)果(模擬退火算法) 相對(duì) GCA求解質(zhì)量的改善程度 憂于 GCA的比例 劣于 GCA的比例 車型數(shù) 5 10 10 5 l0 20 849 542 70 4j 0 l5 10 4O嗝 106 957 60 80純 l5 l0 20 650 607 65 65 20 0 2O 40 333 8 31 8O 70 0 2O 表 5 實(shí)驗(yàn)結(jié)果 (遺傳算 法) 相對(duì)GCA求解質(zhì)量的改善程度 優(yōu)于GCA的比例 劣于GCA的比例 車 型數(shù) 5 10 10 5 10 2o 295 055 60 50 7 l0純 10 40 348 07g 6O 60 2O

21、 l5 20 2筇 l_46 50 8O l5 0 20 40 24 09 50 90 lj嗝 0 試驗(yàn)結(jié)果表 明：模 擬退火算法、遺傳算法均 不同程度的提高了混流生產(chǎn)線調(diào)度問(wèn)題的求解質(zhì) 量 4 結(jié)束語(yǔ) 本文研究 了準(zhǔn)時(shí)生產(chǎn)方式下混流生產(chǎn)線的調(diào) 維普資訊 /.cqvip 28 管 理 科 學(xué) 學(xué) 報(bào) 2000年 I2月 度問(wèn)題，建立了盡可能使各零部件消耗量保持均 勻的多級(jí)混流裝配線調(diào)度模型，并以GCA算法為 基準(zhǔn)，比較研究了遺傳算法、模擬退火算法的求解 參 考 文 獻(xiàn) ：1 ：2 ：3 43 51 63 73 Es 9 質(zhì)量實(shí)驗(yàn)表明，遺傳算法和模擬退火算法得到的 結(jié)果比“目標(biāo)追隨法”有一定程度

22、的提高 趙曉波，周兆英混臺(tái)車型組裝線的投人順序問(wèn)題_J中國(guó)機(jī)械工程，l 998，9(3)：2831 Kubiak WMinimizing variation of production rates in Justintime systems：a surveyJEuropean Journal of O ra_ tional Research，l99366(3)：259-27l Xiaobo z，Ohno KAlgorithms for sequencing mixed models on an assembly line in a JIT production systemJ Computer

23、s and Industry Engineering，1997，32(1)47-56 Agnetis APacifici AetcScheduling of flexible flow lines in an automobile assembly plantJEuropean Journal of OperationalResearch，l 99797(2)：348 362 Leu Y，Matheson L ARess L PSequencing mixed model assembly lines with genetic algorithms：J Computers and Industry Engineering，1996，30(4)e 10271036 Mihenburg G JA theoretical basis for scheduling mixed model production linesJMgmt Sci ，1989;(35)：l 92207 沈希瑾等改變世界的生產(chǎn)方式J北京：中國(guó)經(jīng)濟(jì)出版杜，1996 唐立新等新的Lagrangian松弛法求解 cI sP問(wèn)題J系統(tǒng)工程學(xué)報(bào)，1999，14(1)：914 鄭明春等ERP中的能力平衡策略與輔助決策研究J管理科學(xué)學(xué)報(bào)，1999，2(1)：92