設(shè)施直線型自動(dòng)布置的一個(gè)優(yōu)化算法

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

企業(yè)對(duì)物流成本進(jìn)行有效的控制，需要對(duì)生產(chǎn)設(shè)施進(jìn)行優(yōu)化布置。一方面要求盡可能地減少移動(dòng)次數(shù)，縮短移動(dòng)距離；另一方面要盡可能地避免回退現(xiàn)象。優(yōu)良的設(shè)施布置可以使物流費(fèi)用至少減少10%～30%［1］。設(shè)施布置常見的形式有直線型、L型、U型、O型等，其中直線型是最簡(jiǎn)單也是最常見的形式。直線型最優(yōu)布置問題是一個(gè)具有重要應(yīng)用價(jià)值但至今仍然未解決的理論問題［2］，因?yàn)閙個(gè)產(chǎn)品n個(gè)設(shè)施的不同布置方案共有n！，完全列舉這些布置顯然不可取。對(duì)這類問題的求解通常采用 “從至表”試驗(yàn)法，這種試驗(yàn)法一般都需要用經(jīng)驗(yàn)來(lái)進(jìn)行調(diào)整和改進(jìn)。有的學(xué)者對(duì)這種方法做了一些改進(jìn)［3］；有的學(xué)者也提出了一些新的 “從至表”優(yōu)化模式和新的準(zhǔn)則［2］；有的學(xué)者在 “從至表”基礎(chǔ)上提出了十字形分析法等［4］；有的學(xué)者也用遺傳算法進(jìn)行了一些自動(dòng)布置的方法研究［5］。但一般都沒有考慮回退懲罰下的布置方法。下面，筆者給出了直線型自動(dòng)布置的一個(gè)算法，這種算法包括了回退懲罰下如何進(jìn)行布置的情況??北京物資學(xué)院科研創(chuàng)新基地資助項(xiàng)目。。算法是基于Matlab語(yǔ)言描述的，程序是通過Matlab函數(shù)給出的，生成的從至表是以矩陣的形式表示的，也稱為從至表矩陣。

1 n個(gè)設(shè)施自動(dòng)布置的算法描述及實(shí)現(xiàn)

n個(gè)設(shè)施自動(dòng)布置的算法描述如下：

（1）計(jì)算初始布置p的物流費(fèi)用，記為w0。令

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

（3）在布置p中將設(shè)施1分別與設(shè)施2，3，…，n交換，得到n－1個(gè)不同的布置，在這n－1個(gè)布置中尋找物流費(fèi)用最小的布置，最小的物流費(fèi)用記為w，如果w＜w0，將物流費(fèi)用最小的布置作為新的布置p，令w0＝w。否則布置和物流費(fèi)用均保持不變。

（4）在布置p中將設(shè)施2分別與設(shè)施3，4，…，n交換，得到n－2個(gè)不同的布置，在這n－2個(gè)布置中尋找物流費(fèi)用最小的布置，最小的物流費(fèi)用記為w，如果w＜w0，將物流費(fèi)用最小的布置作為新的布置p，令w0＝w。否則布置和物流費(fèi)用均保持不變。依次下去…。

（5）最后在布置p中將設(shè)施n－1與設(shè)施n交換，得到一個(gè)新的布置，并計(jì)算該布置的物流費(fèi)用，記為w，如果w＜w0，則把該布置作為新的布置p，令w0＝w，否則布置和物流費(fèi)用均保持不變。從而得到第一階段的一個(gè)優(yōu)化布置方案。

（7）結(jié)束。

算法通過［p，M，w］＝costmi n（p0，C，x）函數(shù)實(shí)現(xiàn)，其中，p0為初始布置；C為p0對(duì)應(yīng)的從至表矩陣 （C為n×n的矩陣）；x為懲罰倍數(shù) （當(dāng)x＝1時(shí)不進(jìn)行回退懲罰，當(dāng)x＞1時(shí)進(jìn)行回退懲罰）。輸入p0，c，x，輸出布置p以及對(duì)應(yīng)從至表矩陣M 和物流費(fèi)用w。

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

例1 4個(gè)產(chǎn)品，10個(gè)設(shè)施的物流從至表如表1所示。

表1 10個(gè)設(shè)施的物流從至表

（2）在Matlab窗口中輸入：

則在Matlab窗口中輸出的結(jié)果為：

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

在Matlab窗口中輸入：

則在Matlab窗口中輸出的結(jié)果為：

數(shù)值試驗(yàn)結(jié)果表明，該算法由從至表開始，實(shí)現(xiàn)了設(shè)施進(jìn)行直線型布置的自動(dòng)化，同時(shí)考慮了回退懲罰下如何進(jìn)行布置的問題，并大大減少了物流費(fèi)用。

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

［2］王俊峰，李茲強(qiáng) ．設(shè)備組單行布置問題的 “從至表”法優(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)化法 ［A］．于英川，汪壽陽(yáng) ．決策科學(xué)的力量方法與應(yīng)用 ［C］．北京：卓越出版社，2001．

［5］Ponnambalam S G，Rankumar V．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．