摘要

本文嘗試將不同的啟發(fā)式方法應(yīng)用于家具制造公司的實(shí)際設(shè)施布局問(wèn)題。所有模型都使用 AHP 進(jìn)行比較，其中采用了許多感興趣的參數(shù)。實(shí)驗(yàn)表明，正式的布局建模方法可以有效地用于解決行業(yè)面臨的實(shí)際問(wèn)題，從而帶來(lái)顯著的改進(jìn)。

1。 簡(jiǎn)介

家具行業(yè)正經(jīng)歷著與其他行業(yè)一樣的激烈競(jìng)爭(zhēng)，因此，人們努力尋找降低制造成本、提高質(zhì)量等方法。作為一家制造公司（以下簡(jiǎn)稱“公司”=“TC”）生產(chǎn)力改進(jìn)計(jì)劃的一部分，我們開展了一個(gè)項(xiàng)目，以優(yōu)化該公司車間生產(chǎn)線的布局設(shè)計(jì)，旨在克服當(dāng)前因布局效率低下而導(dǎo)致的問(wèn)題。我們決定應(yīng)用多種布局建模技術(shù)，基于實(shí)踐中很少使用的正式方法生成近乎最優(yōu)的布局。使用的建模技術(shù)是圖論、Bloc Plan、CRAFT、最優(yōu)序列和遺傳算法。然后使用 3 個(gè)標(biāo)準(zhǔn)（即總面積、流量 * 距離和相鄰百分比）評(píng)估和比較這些布局。總面積是指每個(gè)開發(fā)模型的生產(chǎn)線所占的面積。流量 * 距離計(jì)算流量與每 2 個(gè)設(shè)施之間的距離的乘積之和。相鄰百分比計(jì)算滿足相鄰要求的設(shè)施的百分比。

最佳布局的選擇也正式使用多標(biāo)準(zhǔn)使用 Expert Choice 軟件的決策方法 AHP（Satty，1980）。將最佳布局與現(xiàn)有布局進(jìn)行比較，以展示通過(guò)布局設(shè)計(jì)正式方法獲得的改進(jìn)。

工廠布局問(wèn)題的定義是找到物理設(shè)施的最佳布置，以實(shí)現(xiàn)高效的運(yùn)營(yíng)（Hassan 和 Hogg，1991 年）。布局會(huì)影響材料處理成本、交貨時(shí)間和產(chǎn)量。因此，它會(huì)影響工廠的整體生產(chǎn)力和效率。根據(jù) Tompkins 和 White (1984) 的說(shuō)法，設(shè)施的設(shè)計(jì)在整個(gè)有記載的歷史中一直存在，事實(shí)上，設(shè)計(jì)和建造的城鎮(zhèn)設(shè)施在古代就有描述

* 通訊作者

希臘和羅馬帝國(guó)的歷史。最早研究這個(gè)問(wèn)題的人是 Armour 和 Buffa 等人 (1)。1964 世紀(jì) 1950 年代似乎很少有相關(guān)研究。Francis 和 White (1974) 是第一個(gè)收集和更新該領(lǐng)域早期研究的人。后來(lái)的研究由兩項(xiàng)研究更新，第一項(xiàng)由 Domschke 和 Drexl (1) 進(jìn)行，另一項(xiàng)由 Francis 等人 (2) 進(jìn)行。Hassan 和 Hogg (1) 報(bào)告了一項(xiàng)關(guān)于機(jī)器布局問(wèn)題所需數(shù)據(jù)類型的廣泛研究。機(jī)器布局?jǐn)?shù)據(jù)按層次結(jié)構(gòu)考慮；取決于布局設(shè)計(jì)的詳細(xì)程度。當(dāng)所需的布局只是找到機(jī)器的相對(duì)排列時(shí)，表示機(jī)器編號(hào)及其流動(dòng)關(guān)系的數(shù)據(jù)就足夠了。但是，如果需要詳細(xì)的布局，則需要更多數(shù)據(jù)。在查找數(shù)據(jù)時(shí)可能會(huì)出現(xiàn)一些困難，尤其是在尚無(wú)數(shù)據(jù)的新制造工廠中。當(dāng)為現(xiàn)代化和自動(dòng)化設(shè)施開發(fā)布局時(shí)，所需的數(shù)據(jù)無(wú)法從歷史數(shù)據(jù)或類似設(shè)施中獲得，因?yàn)樗鼈兛赡懿淮嬖?。?shù)學(xué)建模被認(rèn)為是獲得設(shè)施布局問(wèn)題最佳解決方案的一種方法。自從 Koopmans 和 Beckmann (1985) 開發(fā)出第一個(gè)數(shù)學(xué)模型作為二次分配問(wèn)題以來(lái)，人們對(duì)該領(lǐng)域的興趣已經(jīng)大大增加。這為研究人員開辟了一個(gè)新而有趣的領(lǐng)域。在尋找設(shè)施布局問(wèn)題的解決方案時(shí)，研究人員開始開發(fā)數(shù)學(xué)模型。Houshyar 和 White (1992) 將布局問(wèn)題視為整數(shù)規(guī)劃模型，而 Rosenblatt (1986) 將布局問(wèn)題表述為動(dòng)態(tài)規(guī)劃模型。Palekar 等人 (1992) 處理不確定性，而 Shang (1993) 使用多標(biāo)準(zhǔn)方法。另一方面，Leung (1992) 提出了圖論公式。

綠色和哈基姆(1985) 使用 GA 來(lái)查找零件系列以及單元之間的布局。在他的公式中，他將單元的排列限制為線性單排或線性雙排。開發(fā)的算法更傾向于單元系統(tǒng)布局或生產(chǎn)車間布局，而不是單元布局或機(jī)器布局。沒有考慮單元內(nèi)機(jī)器的實(shí)際布局。Banerjee 和 Zhou (1995) 為單環(huán)使用遺傳算法進(jìn)行布局。所開發(fā)的算法適用于單元系統(tǒng)布局，因此不考慮單元內(nèi)機(jī)器的布局。Fu 和 Kaku (1997) 提出了一種針對(duì)車間制造系統(tǒng)的工廠布局問(wèn)題公式，其目標(biāo)是最小化平均在制品。他們?cè)谝幌盗屑僭O(shè)下將工廠建模為開放排隊(duì)網(wǎng)絡(luò)。該問(wèn)題簡(jiǎn)化為排隊(duì)分配問(wèn)題 (QAP)。使用模擬來(lái)最小化平均物料搬運(yùn)成本并最小化平均在制品。

2. 建模方法

根據(jù)模型的性質(zhì)、假設(shè)和目標(biāo)，對(duì)模型進(jìn)行分類。第一種通用的系統(tǒng)布局規(guī)劃方法由 Muthor (1) 開發(fā)，它仍然是一個(gè)有用的方案，尤其是在得到其他方法的支持和計(jì)算機(jī)的協(xié)助的情況下。構(gòu)建方法（例如 Hassan 和 Hogg (1955)）從頭開始構(gòu)建布局，而改進(jìn)方法（例如 Bozer、Meller 和 Erlebacher (1991)）則嘗試修改現(xiàn)有布局以獲得更好的結(jié)果。Heragu (1994) 詳細(xì)記錄了布局的優(yōu)化方法和啟發(fā)式方法。德阿爾瓦倫加和 Gomes (2000) 討論了元啟發(fā)式方法來(lái)克服最優(yōu)模型的 NP 難題。

本研究中使用的各種建模技術(shù)包括圖論、CRAFT、最優(yōu)序列、BLOCPLAN 和遺傳算法。下面解釋了每種算法建模所需的參數(shù)。

圖論

圖論（Foulds and Robinson，1976 年；Giffin 等，1984 年；Kim and Kim，1985 年；Leung，1992 年）應(yīng)用了一種邊權(quán)重最大平面圖，其中頂點(diǎn)（V）表示設(shè)施，邊（E）表示鄰接，Kn 表示 n 個(gè)頂點(diǎn)的完全圖。給定加權(quán)圖 G，設(shè)施布局問(wèn)題是找到最大加權(quán)生成子圖G 中的 G' 是平面的。

本文采用兩種不同的方法來(lái)模擬案例研究。第一種方法是三角面體Foulds 和 Robinson (1976) 的方法。該方法涉及使用初始 K4 進(jìn)行簡(jiǎn)單插入，然后根據(jù)收益標(biāo)準(zhǔn)逐個(gè)插入頂點(diǎn)。使用的第二種方法是輪式擴(kuò)展算法（Green 和哈基姆，1985）。這里，初始 K4 是通過(guò)選擇具有最高 w8 的邊，然后根據(jù)收益標(biāo)準(zhǔn)應(yīng)用 2 個(gè)連續(xù)頂點(diǎn)插入而獲得的。然后，算法繼續(xù)進(jìn)行插入過(guò)程，稱為輪擴(kuò)展過(guò)程。n 個(gè)頂點(diǎn)上的輪定義為(n-1)頂點(diǎn)（稱為輪輞），使得每個(gè)頂點(diǎn)都與一個(gè)額外的頂點(diǎn)（稱為輪轂）相鄰。讓 W 成為具有輪轂 x 的輪子。選擇 2 個(gè)頂點(diǎn) k 和 l，它們是此循環(huán)的輪輞。然后將未使用的頂點(diǎn)集中的一個(gè)頂點(diǎn)插入當(dāng)前部分中的此輪子子圖這樣 y 是新車輪 W′ 的輪轂，車輪 W′ 包含 k、l 和 x 作為輪輞，并且 W 中的所有輪輞現(xiàn)在都與頂點(diǎn) x 或頂點(diǎn) y 相鄰。通過(guò)按上述方式依次插入每個(gè)未使用的頂點(diǎn)，即可獲得最終的最大平面子圖。

使用 CRAFT

CRAFT（計(jì)算機(jī)化相對(duì)設(shè)施分配技術(shù)）使用成對(duì)交換來(lái)制定布局（Buffa 等人，1964 年；Hicks 和 Lowan，1976 年）。在生成改進(jìn)的布局之前，CRAFT 不會(huì)檢查所有可能的成對(duì)交換。輸入數(shù)據(jù)包括建筑物和設(shè)施的尺寸、設(shè)施對(duì)之間的物料流量或行程頻率以及單位距離每單位負(fù)載的成本。流量（f）和距離（d）的乘積提供了在兩個(gè)設(shè)施之間運(yùn)輸物料的成本。然后根據(jù)交換前后的物料處理成本貢獻(xiàn)來(lái)計(jì)算成本降低。

最優(yōu)序列

解決方法從任意順序布局開始，并嘗試通過(guò)按順序切換 2 個(gè)部門來(lái)改進(jìn)布局（Heragu，1997）。在每個(gè)步驟中，該方法計(jì)算所有可能切換 2 個(gè)部門的流量*距離變化，并選擇最有效的一對(duì)。切換 2 個(gè)部門并重復(fù)該方法。當(dāng)沒有切換導(dǎo)致成本降低時(shí)，該過(guò)程停止。使用最佳序列生成布局所需的輸入主要是建筑物和設(shè)施的尺寸、設(shè)施對(duì)之間的物料流量或行程頻率以及每單位距離每單位負(fù)載的成本。

使用 BLOCPLAN

BLOCPLAN 是一個(gè)交互式程序，用于開發(fā)和改進(jìn)單層和多層布局（綠色和 哈基姆，1985 年）。這是一個(gè)簡(jiǎn)單的程序，由于其基于幾個(gè)嵌入選項(xiàng)的靈活性，可以生成良好的初始布局。它使用定量和定性數(shù)據(jù)來(lái)

生成若干個(gè)塊布局及其適應(yīng)度度量。用戶可以根據(jù)具體情況選擇相應(yīng)的解決方案。

遺傳算法

通過(guò)遺傳算法 (GA) 制定設(shè)施布局問(wèn)題的方法有很多。Banerjee、Zhou 和 Montreuil(1997) 將 GA 應(yīng)用于單元布局。切片樹結(jié)構(gòu)最初由 Otten (1) 提出，作為一種表示一類布局的方法。后來(lái)，許多作者都使用了這種方法，包括 Tam 和 Chan (1982)，他們用它來(lái)解決具有幾何約束的不等面積布局問(wèn)題。本文中使用的 GA 算法是由 Shayan 和 Chittilappilli (1995) 基于切片樹結(jié)構(gòu) (STC) 開發(fā)的。它將樹結(jié)構(gòu)候選布局編碼為二維染色體的特殊結(jié)構(gòu)，該結(jié)構(gòu)顯示了切片樹中每個(gè)設(shè)施的相對(duì)位置。在 GA 操作中，可以使用特殊方案來(lái)操縱染色體 (Tam and Li, 2004)。Shayan 和 Chittilappilli (2) 還引入了一種新的“克隆”操作哈基姆（1999）。通過(guò) GA 選擇的解決方案隨后轉(zhuǎn)換為切片布局。它從一個(gè)包含所有設(shè)施的初始?jí)K開始。隨著布局構(gòu)建算法的進(jìn)展，新的分區(qū)被創(chuàng)建，設(shè)施被分配到新生成的塊之間，直到每個(gè)塊中只有一個(gè)設(shè)施。同時(shí)還計(jì)算每個(gè)設(shè)施的坐標(biāo)。設(shè)施質(zhì)心之間的直線距離用于評(píng)估相應(yīng)染色體的適應(yīng)度。當(dāng) GA 終止時(shí)，繪圖程序接管使用存儲(chǔ)的坐標(biāo)值打印布局。目標(biāo)函數(shù)有一個(gè)懲罰項(xiàng)以避免狹窄的切片。

3. 通過(guò)案例研究進(jìn)行實(shí)驗(yàn)

為了測(cè)試前面描述的方法的性能，它們都被應(yīng)用于家具制造的真實(shí)案例場(chǎng)景。該公司生產(chǎn) 9 種不同風(fēng)格的椅子、2 座和3 座分別。所有款式的生產(chǎn)都遵循相同的操作，但涉及不同的原材料。5 個(gè)部件，即座墊、靠背墊、扶手、座椅和靠背，在分散的區(qū)域（部門）內(nèi)以不同尺寸的批次進(jìn)行生產(chǎn)。零件的移動(dòng)會(huì)產(chǎn)生諸如在制品、零件缺失、短缺、擁堵和錯(cuò)誤放置等問(wèn)題。

每件產(chǎn)品都要經(jīng)過(guò) 11 道工序，從設(shè)施 1 - 切割區(qū)開始，到設(shè)施 11 - 螺栓固定區(qū)結(jié)束。每個(gè)最終組裝件都可以分解為同名的子組裝件。這些子組裝件在螺栓固定區(qū)匯合-向上最終裝配設(shè)施。每個(gè)子組件都獨(dú)立開始其操作，并且都經(jīng)過(guò)一組固定的操作，該操作以裝配圖的形式顯示在圖 1 中。當(dāng)前布局的設(shè)施不是按照操作順序放置的。

因此，材料沒有連續(xù)流動(dòng)，導(dǎo)致工作正在進(jìn)行中。設(shè)施之間的相互作用可以通過(guò)主觀和客觀措施來(lái)確定。流程圖所需的主要輸入是需求、生產(chǎn)的材料數(shù)量以及每臺(tái)機(jī)器之間流動(dòng)的材料量。材料流量是根據(jù)每 10 個(gè)月的材料流量計(jì)算的 * 計(jì)量單位，如圖 2 所示。圖 3 顯示了案例研究中使用的每個(gè)部門的面積。圖 4 顯示了案例研究的當(dāng)前布局。

圖 1 案例研究的裝配圖

圖 2 案例研究的材料流程。

圖3 部門對(duì)應(yīng)編號(hào)

圖 4 家具公司目前的布局以及案例研究建模中使用的每個(gè)部門的尺寸

4. 建模方法的應(yīng)用

這里將第 2 節(jié)中討論的各種建模方法應(yīng)用于案例研究，以生成可供比較的替代布局。

4.1 使用圖論

表 1 顯示了使用兩種不同的圖論方法（即 Foulds 和 Robinsons 方法以及 Wheels and Rims 方法）的結(jié)果比較。表 2 清楚地表明，F(xiàn)oulds 和 Robinsons 方法是兩種結(jié)果中較好的一種。Foulds 和 Robinsons 方法的結(jié)果在圖中進(jìn)行了詳細(xì)說(shuō)明5-7。

表 1：顯示所使用的兩種不同圖論方法的比較的表格。

圖 5 采用 Foulds 和 Robinson 方法的案例研究結(jié)果的鄰接圖。

圖6 利用圖論（Foulds 和 Robinsons 方法）改進(jìn)后的布局

1-切割，2- 縫紉，3- 填充印花布，4- 特寫，5- 填充墊子插入物，6- 泡沫切割，泡沫切割，7- 框架組裝，8- 粘貼，9 年春季向上，10-室內(nèi)裝飾，11- 用螺栓固定。

圖7 使用圖論（Foulds 和 Robinsons 方法）對(duì)案例研究的流程*距離評(píng)估圖表

4.2 使用 CRAFT

輸入 CRAFT 的輸入數(shù)據(jù)，并首先計(jì)算當(dāng)前布局的初始成本?？梢允褂贸蓪?duì)比較來(lái)降低此成本，如圖 1、8,9 所示。

圖 8 使用 CRAFT 計(jì)算當(dāng)前布局的初始成本

圖 9 CRAFT 的逐步交換

CRAFT 得到的結(jié)果如表 2 所示?；谝陨嫌?jì)算，可以繪制出新的改進(jìn)布局，如圖 10 所示

表 2：結(jié)果表

圖 10 CRAFT 生成的改進(jìn)布局

4.3 最優(yōu)序列算法

輸入數(shù)據(jù)與 CRAFT 相同，只是它遵循不同的成對(duì)比較。表 3 顯示了改進(jìn)布局的結(jié)果。圖 11 顯示了使用最佳序列的改進(jìn)布局。

表 3 使用 CRAFT 的結(jié)果表