設施直線型自動布置的算法之二

常雙領（北京物資學院 信息學院，北京 101149）

0 引 言

企業要對物流成本進行有效的控制，需要對生產設施進行優化布置。一方面要求盡可能的減少移動次數，縮短移動距離。另一方面要盡可能地避免回退現象，回退現象的發生與設施布置有密切關系。優良的設施布置可以使物流費用至少減少10%～30%[1]。設施布置常見的形式有直線型，L型、U型、O型，其中直線型是最簡單也是最常見的形式。設施直線型最優布置問題是一個具有重要應用價值但至今仍然未解決的理論問題[2]，因為m個產品n個設施的不同布置方案共有n!，完全列舉這些布置顯然不可取。對這類問題的求解通常采用“從至表”試驗法，這種試驗法一般都需要用經驗來進行調整和改進。有的學者也對這種“從至表”試驗方法做了一些改進[3]，但實際效果并不理想，可操作性也不強。有的學者也提出了一些新的“從至表”優化模式和新的準則[2]，有的學者提出了在“從至表”基礎上提出了十字形分析法等[4]。有的學者給出用遺傳算法進行一些自動布置的方法[5]。有的學者根據設施之間的緊密程度進行排序，以確定在車間布置中的優先位置并賦予不同的權重[6]，一般學者都沒有考慮回退懲罰下的優化布置方法。本文對這種直線型布置問題做了研究，給出了一種自動布置算法。首先，從零件工藝路線圖開始自動生成初始從至表。其次，通過對從至表進行變形計算，得到一個優化的布置方案以及對應的從至表和物流費用。文中的算法是基于Matlab語言描述的，程序是通過Matlab函數給出的，生成的從至表是以矩陣的形式表示的，也稱為從至表矩陣。

1 算法描述

以例1為研究背景，給出m個產品n個設施自動布置的算法

例1：4個產品，8個設施的零件工藝線路圖如圖1所示，產品A，B，C，D的當量物流量分別是2，3，1，1。

圖1 產品工藝路線圖

算法1：（由產品工藝路線圖生成從至表）

（1）把m個產品n個設施的產品工藝圖轉化為一個m行n列的工藝路線矩陣a；

（2）構造n個零件的當量物流量為向量b；

（3）初始化從至表c=zeros（n）；

（4）for i=1∶m，for j=1∶n；

（5）if a（i,j＋1）＞0，u=a（i,j），v=a（i,j＋1），c（u,v）=c（u,v）＋b（i），結束，否則（4）；

（6）結束。

算法1的實現：通過[c]=fromto（a,b）函數實現。

函數輸入參數說明：a為工藝路線矩陣，即a的第i行，為第i個產品的工藝路線，b為零件的當量物流量向量，即b（i）表示第i個零件的當量物流量。

函數功能：輸入a,b返回物流從至表矩陣c。

構造產品的當量物流量的向量為b=（2,3,1,）1。

（2）在Matlab窗口中輸入[c]=formto（a,b），則在Matlab窗口中輸出的結果為：

設施以1-2-3-4-5-6-7-8方式排列的從至表如矩陣c所示。

算法2：（對初始從至表矩陣進行行列變換，得到一個優化的布置）

（1）給出初始從至表矩陣c（c為n×n矩陣），c對應的布置記為p=（1,2, …,n）稱為初始布置，計算初始布置的物流費用w0。令w（1）=w0＋1；w（2）=w0；k=1。

（2）while w（k＋1）＜w（k）。

（3）將從至表矩陣中的第一行（列）分別與第二，第三，…，第n行（列）交換，得到n-1個從至表矩陣，每一個從至表矩陣對應一種布置，在n-1種布置中找到物流費用最小的一種布置，最小的物流費用記w，如果w＜w0，則把物流費用最小的布置做為新的布置p，對應的矩陣做為新的從至表矩陣c，并且令w0=w；否則布置和從至表矩陣均保持不變。

（4）將從至表矩陣中的第二行（列）分別與第三，第四，…，第n行（列）交換，得到n-2個從至表矩陣，每一個從至表矩陣對應一種布置，在n-2種布置中找到物流費用最小的一種布置，最小的物流費用記w，如果w＜w0，則把物流費用最小的布置做為新的布置p，對應的矩陣做為新的從至表矩陣c，并且令w0=w；否則布置和從至表矩陣均保持不變。這樣依次下去。

（5）最后將從至表矩陣c中的第n-1行（列）與第n行（列）交換，計算物流費用，記為w，如果w＜w0，則把物流費用最小的布置做為新的布置p，令w0=w，對應的矩陣做為新的從至表矩陣c；否則布置和從至表矩陣均保持不變。從而得到第一階段的一個優化布置方案。

（6）令k=k＋1；w（k＋1）=w0。返回（2）。

（7）結束。

算法2的實現：通過[p,m,w]=mincost（c,x）函數實現：

函數輸入參數說明：c為初始從至表矩陣（c為一個n×n的矩陣），x為懲罰倍數（當x=1是不進行回退懲罰，當x＞1是進行回退懲罰）。

函數功能：輸入c,x，輸出設施的布置以及對應從至表矩陣和物流費用，分別返回給p,m,w。

如例1：在Matlab窗口中輸入：[p,m,w]=mincost（c,1），則在Matlab窗口中輸出的結果為：

即設施的布置為1-7-3-2-5-4-6-8，從至表如矩陣m所示，物流費用為53。

2 數值實驗與結果分析

例2：（見文獻[3]中的例2）原始從至表如表1。

表1 從至表

（2）在Matlab窗口中輸入：[p,m,w]=mincost（c,1），則在Matlab窗口中輸出的結果為：

即設施的布置為5-9-2-1-3-4-7-10-6-8，從至表如矩陣m所示，物流費用為119。

結果分析：初始布置1-2-3-4-5-6-7-8-9-10的物流費用為207，經過優化布置后的物流費用為119。而文獻[3]優化的物流費用為133。

如果在例2中對回退進行2倍懲罰時：

在Matlab窗口中輸入：[p,m,w]=mincost（c,2），則在Matlab窗口中輸出的結果為：

3 結束語

這種方法實現了從產品工藝路線圖開始，設施進行直線型布置的自動化，數值實驗的結果表明這種算法是十分有效的。

[1]蔡臨寧.物流系統規劃——建模及實例分析[M].北京：機械工業出版社，2003:60-124.

[2]王俊峰，李茲強.設備組單行布置問題的“從至表”法優化模式與新準則探索[J].合肥工業大學學報（自然科學版），2005,28(9):1163-1166.

[3]賈春玉，崔劍.設備單行布置從至表試驗法的改進[J].工業工程與管理，2008(1):127-130.

[4]謝健.生產車間設備布置的“從至表”優化法[C]//決策科學的力量方法與應用.北京：卓越出版社，2001:1-80.

[5]S.G.Ponnambalam,V.Rankumar.A Genetic Algorithm for the Design of a Single-Row Layout in Automated Manufacturing Systems[J].The international Journal of Advanced Manufacturing Technology，2001(18):512-519.

[6]張畢西，劉永清.多對象生產單元設備雙行布置優化分析[J].華南理工大學學報（自然科學板），1999,5(27):45-51.