设备布局优化是现场改善活动的一个基础性问题，它的合理与否直接影响着现场的生产能力、工作效率和生产成本。Tompkins和White指出因设备布局不合理所产生的运行费用占制造系统整体运行费用的20％一50％，而优良的设备布局可使这一费用减少10％一30％；优良的设备布局还能加快物料处理的效率，减少在制品的停留时间，减少工件缓冲区的容量，缩小制造系统所占用的空间，减少制造系统建设的费用。因此，进行生产现场的设备布局改善对制造企业提高生产效率和经济效益具有十分重要的现实意义。

设备布局问题的描述

制造企业TPM中的设备布局通常可以分为“逻辑布局”和“物理布局”两种：逻辑布局是指各制造系统的任务分配，包括资源规划和负荷平衡等；物理布局则是指为制造设备分配相应的位置。本文所指的布局主要是指现场设备的物理布局。设备布局就是要将工作地内的各个设备合理安排，在满足各设备面积和位置限制条件下，使它们组合成一定的空间形式，从而有效地为企业的生产运作服务，以获得更好的经济效果。常见的布局形式有单行布局、多行布局、U型布局和环形布局等，其中的约束条件包括：设备不可重叠、设备不可超出工作地范围、设备之间必须满足最小间距要求等等。

设备布局问题的模型

事实上，不论是单行布局、u型布局还是环形布局，都可以看作是多行布局的一种。

工作地设备布局的俯视图，图中Mi表示设备i，(xi，yi)表示设备i中心点的坐标。设备布局问题就是求解各个设备的坐标(xi，yi)，并使其满足一定的目标函数要求。这一模型所做的假设如下：

①工作地和设备忽略其细节形状，均假设为矩形，且设备的各条边分别与工作地各条边平行；

②设备的尺寸已知且固定不变；

③相邻两行的最小行间距己知，同一行相邻内设备的最小间距已知；

④同一行内的设备，其中心点的纵坐标相同。

自Koopmans和Beckman提出二次分配模型开始，学者们建立了许多模型来尝试解决设备布局问题，其中常见的模型主要有“二次分配模型”和“图论模型”两种。

(1)二次分配问题模型

二次分配问题(QAP)模型是1957年由Koopmans和Beckman提出的，它的思想是将工作地分成m个等面积的区域，然后将n(n=m)台设备分别分配到这些区域中去，使得总搬运成本最低。并且规定每台设备最多只能占一个区域，每个区域最多只能放置一台设备。

QAP模型的优点在于模型结构简单，容易理解和使用。然而也正是由于它的简单，使它同时具有以下的缺陷：

①只适用于设备面积相等的布局问题，且设备的放置地点是已知、固定的；

②由于目标函数为自变量的二次多项式，问题的复杂程度随着位置的数量而呈指数增长。

③由于忽略了设备的几何形状，往往导致计算得到的布局方案无法实现。

(2)图论模型

用图论模型解决设备布局问题需要经过三个步骤：

①根据设备间的关系画出关联图；

②建立关联图的对偶图；

③将对偶图转化为块布置图。

设备布局优化算法

由于设备布局问题属于NP完备问题，在多项式时间内无法求其最优解，因而在求解这类问题时通常采用启发式算法。

所谓启发式算法是指：一组指导算法搜索方向的、建议性质的规则集，通常按照这个规则集计算机可在解空间中寻找到一个较好解，但并不能保证每次都能找到较好解，更不能保证找到最优解。

简单说，启发算法就是能够提高搜索效率，从计算结果上看有较好的性能但无法做出相应的理论证明的一种算法。启发算法有很多种，其中应用最广泛的就是遗传算法。

遗传算法(GA)起源于对生物系统所进行的计算机模拟研究，它是由美国Michigan大学的Holland教授及其学生受到生物模拟技术的启发，而创造出的一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术。其运算流程如图2．2所示：

(1)初始化：确定遗传算法的各种参数。如种群数量M，最大进化代数T，代数计数器t=0，交叉概率Pc，变异概率P。，生成初始种群P(o)。

(2)编码：根据不同问题，采用不同的编码方法，将问题的解映射为一组数据串，实现个体表现型向基因型的转化。

(3)计算个体适应度：适应度值代表个体的优劣程度，先确定适应度函数，然后计算群体中每个个体的适应度值，为选择操作做好准备。

(4)生成新群体：对当前群体P(t)进行选择、交叉、变异等操作，生成新一代群体P(t+1)。

①选择算子：遗传算法使用选择算子来实现个体的优胜劣汰——根据每个个体的适应度值大小进行选择，适应度较高的个体被遗传到下一代的概率较大，以此促使群体中个体的适应度值不断逼近最优解。

②交叉算子：遗传算法中，用交叉算子对相互配对的两个染色体，按照某种方式交换其部分基因，从而形成两个新的个体。交叉算子决定了遗传算法的全局搜索能力。

③变异算子：以较小的概率对个体基因编码上某个或某些基因值进行改变，从而生成新个体。变异算子决定了遗传算法的局部搜索能力。

(5)判断是否达到进化要求：从遗传代数、最优解精度两方面判断是否停止遗传运算，如“是”则停止运算，转入解码；如“否”则转到步骤(3)继续运算。

(6)解码：结束遗传运算后，采用与编码相反的运算，将个体的基因型转化为表现型，得到最终结果。

遗传算法通过上述流程可以有效地解决许多NP复杂问题，因而在各个领域得到了广泛的应用。其主要特点如下：

(1)由于遗传算法处理的是解集的编码而非解集本身，因而其方法具有广泛适应性。

(2)遗传算法采用并行搜索的方法，即同时对多个点进行搜索，因此具有较好的全局搜索能力。

(3)遗传算法只使用适应度函数值来评价个体，不需要其它辅助信息。

(4)遗传算法具有内在启发式随即搜索特性，它不是采用确定规则，而是采用概率规则来指导搜索方向。

(5)不容易陷入局部最优，能以较大的概率收敛到全局最优解。

(6)遗传算法具有可扩展性，易于同其它方法混用。