设施直线型自动布置的一个优化算法

常双领 （北京物资学院信息学院，北京101149）

企业对物流成本进行有效的控制，需要对生产设施进行优化布置。一方面要求尽可能地减少移动次数，缩短移动距离；另一方面要尽可能地避免回退现象。优良的设施布置可以使物流费用至少减少10%～30%［1］。设施布置常见的形式有直线型、L型、U型、O型等，其中直线型是最简单也是最常见的形式。直线型最优布置问题是一个具有重要应用价值但至今仍然未解决的理论问题［2］，因为m个产品n个设施的不同布置方案共有n！，完全列举这些布置显然不可取。对这类问题的求解通常采用 “从至表”试验法，这种试验法一般都需要用经验来进行调整和改进。有的学者对这种方法做了一些改进［3］；有的学者也提出了一些新的 “从至表”优化模式和新的准则［2］；有的学者在 “从至表”基础上提出了十字形分析法等［4］；有的学者也用遗传算法进行了一些自动布置的方法研究［5］。但一般都没有考虑回退惩罚下的布置方法。下面，笔者给出了直线型自动布置的一个算法，这种算法包括了回退惩罚下如何进行布置的情况❶❶北京物资学院科研创新基地资助项目。。算法是基于Matlab语言描述的，程序是通过Matlab函数给出的，生成的从至表是以矩阵的形式表示的，也称为从至表矩阵。

1 n个设施自动布置的算法描述及实现

n个设施自动布置的算法描述如下：

（1）计算初始布置p的物流费用，记为w0。令

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

（3）在布置p中将设施1分别与设施2，3，…，n交换，得到n－1个不同的布置，在这n－1个布置中寻找物流费用最小的布置，最小的物流费用记为w，如果w＜w0，将物流费用最小的布置作为新的布置p，令w0＝w。否则布置和物流费用均保持不变。

（4）在布置p中将设施2分别与设施3，4，…，n交换，得到n－2个不同的布置，在这n－2个布置中寻找物流费用最小的布置，最小的物流费用记为w，如果w＜w0，将物流费用最小的布置作为新的布置p，令w0＝w。否则布置和物流费用均保持不变。依次下去…。

（5）最后在布置p中将设施n－1与设施n交换，得到一个新的布置，并计算该布置的物流费用，记为w，如果w＜w0，则把该布置作为新的布置p，令w0＝w，否则布置和物流费用均保持不变。从而得到第一阶段的一个优化布置方案。

（7）结束。

算法通过［p，M，w］＝costmi n（p0，C，x）函数实现，其中，p0为初始布置；C为p0对应的从至表矩阵 （C为n×n的矩阵）；x为惩罚倍数 （当x＝1时不进行回退惩罚，当x＞1时进行回退惩罚）。输入p0，c，x，输出布置p以及对应从至表矩阵M 和物流费用w。

2 数值试验与结果分析

例1 4个产品，10个设施的物流从至表如表1所示。

表1 10个设施的物流从至表

（2）在Matlab窗口中输入：

则在Matlab窗口中输出的结果为：

如果在例1中对回退进行2倍惩罚时：

在Matlab窗口中输入：

则在Matlab窗口中输出的结果为：

数值试验结果表明，该算法由从至表开始，实现了设施进行直线型布置的自动化，同时考虑了回退惩罚下如何进行布置的问题，并大大减少了物流费用。

［1］蔡临宁 ．物流系统规划——建模及实例分析 ［M］．北京：机械工业出版社，2003：60－124．

［2］王俊峰，李兹强 ．设备组单行布置问题的 “从至表”法优化模式与新准则探索 ［J］．合肥工业大学学报 （自然科学版），2005，28（9）：1163－1166．

［3］贾春玉，崔剑 ．设备单行布置从至表试验法的改进 ［J］．工业工程与管理，2008（1）：127－130．

［4］谢健 ．生产车间设备布置的 “从至表”优化法 ［A］．于英川，汪寿阳 ．决策科学的力量方法与应用 ［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．