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

0 引 言

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

1 算法描述

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

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

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

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

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

（2）構(gòu)造n個(gè)零件的當(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的實(shí)現(xiàn)：通過(guò)[c]=fromto（a,b）函數(shù)實(shí)現(xiàn)。

函數(shù)輸入?yún)?shù)說(shuō)明：a為工藝路線矩陣，即a的第i行，為第i個(gè)產(chǎn)品的工藝路線，b為零件的當(dāng)量物流量向量，即b（i）表示第i個(gè)零件的當(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：（對(duì)初始從至表矩陣進(jìn)行行列變換，得到一個(gè)優(yōu)化的布置）

（1）給出初始從至表矩陣c（c為n×n矩陣），c對(duì)應(yīng)的布置記為p=（1,2, …,n）稱為初始布置，計(jì)算初始布置的物流費(fèi)用w0。令w（1）=w0＋1；w（2）=w0；k=1。

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

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

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

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

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

（7）結(jié)束。

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

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

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

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

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

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

例2：（見文獻(xiàn)[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所示，物流費(fèi)用為119。

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

如果在例2中對(duì)回退進(jìn)行2倍懲罰時(shí)：

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

3 結(jié)束語(yǔ)

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

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

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

[3]賈春玉，崔劍.設(shè)備單行布置從至表試驗(yàn)法的改進(jìn)[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]張畢西，劉永清.多對(duì)象生產(chǎn)單元設(shè)備雙行布置優(yōu)化分析[J].華南理工大學(xué)學(xué)報(bào)（自然科學(xué)板），1999,5(27):45-51.