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

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

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

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

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

（1）計算初始布置p的物流費用，記為w0。令

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

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

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

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

（7）結(jié)束。

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

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

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

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

（2）在Matlab窗口中輸入：

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

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

在Matlab窗口中輸入：

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

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

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

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

［3］賈春玉，崔劍 ．設(shè)備單行布置從至表試驗法的改進 ［J］．工業(yè)工程與管理，2008（1）：127－130．

［4］謝健 ．生產(chǎn)車間設(shè)備布置的 “從至表”優(yōu)化法 ［A］．于英川，汪壽陽 ．決策科學(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．