設(shè)施直線型自動布置的算法之二

常雙領(lǐng)（北京物資學(xué)院 信息學(xué)院，北京 101149）

0 引 言

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

1 算法描述

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

例1：4個產(chǎn)品，8個設(shè)施的零件工藝線路圖如圖1所示，產(chǎn)品A，B，C，D的當(dāng)量物流量分別是2，3，1，1。

圖1 產(chǎn)品工藝路線圖

算法1：（由產(chǎn)品工藝路線圖生成從至表）

（1）把m個產(chǎn)品n個設(shè)施的產(chǎn)品工藝圖轉(zhuǎn)化為一個m行n列的工藝路線矩陣a；

（2）構(gòu)造n個零件的當(dāng)量物流量為向量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），結(jié)束，否則（4）；

（6）結(jié)束。

算法1的實現(xiàn)：通過[c]=fromto（a,b）函數(shù)實現(xiàn)。

函數(shù)輸入?yún)?shù)說明：a為工藝路線矩陣，即a的第i行，為第i個產(chǎn)品的工藝路線，b為零件的當(dāng)量物流量向量，即b（i）表示第i個零件的當(dāng)量物流量。

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

構(gòu)造產(chǎn)品的當(dāng)量物流量的向量為b=（2,3,1,）1。

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

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

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

（1）給出初始從至表矩陣c（c為n×n矩陣），c對應(yīng)的布置記為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個從至表矩陣，每一個從至表矩陣對應(yīng)一種布置，在n-1種布置中找到物流費用最小的一種布置，最小的物流費用記w，如果w＜w0，則把物流費用最小的布置做為新的布置p，對應(yīng)的矩陣做為新的從至表矩陣c，并且令w0=w；否則布置和從至表矩陣均保持不變。

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

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

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

（7）結(jié)束。

算法2的實現(xiàn)：通過[p,m,w]=mincost（c,x）函數(shù)實現(xiàn)：

函數(shù)輸入?yún)?shù)說明：c為初始從至表矩陣（c為一個n×n的矩陣），x為懲罰倍數(shù)（當(dāng)x=1是不進行回退懲罰，當(dāng)x＞1是進行回退懲罰）。

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

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

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

2 數(shù)值實驗與結(jié)果分析

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

表1 從至表

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

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

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

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

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

3 結(jié)束語

這種方法實現(xiàn)了從產(chǎn)品工藝路線圖開始，設(shè)施進行直線型布置的自動化，數(shù)值實驗的結(jié)果表明這種算法是十分有效的。

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

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

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

[4]謝健.生產(chǎn)車間設(shè)備布置的“從至表”優(yōu)化法[C]//決策科學(xué)的力量方法與應(yīng)用.北京：卓越出版社，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]張畢西，劉永清.多對象生產(chǎn)單元設(shè)備雙行布置優(yōu)化分析[J].華南理工大學(xué)學(xué)報（自然科學(xué)板），1999,5(27):45-51.