英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

基于柔性区带结构和遗传算法求解动态设施布局问题

Mostafa Mazinani amp; Mostafa Abedzadeh amp;Navid Mohebali

摘要:找到工厂部门的职位多个时段的地板，同时最小化的总和材料处理和重新布置成本是动态设施布局问题（DFLP）的基础考虑。 在本文介绍了一种新型DFLP采用灵活的柔性区带结构。 在工厂布局中，基于柔性托架结构，部门分配到工厂楼层的平行隔间。部门可能是自由导向的，可能是不平等的区域以及混合整数规划找到最佳解决方案。 由于复杂性，只有小尺寸使用精确时，可以在逻辑时间内解决问题方法。 因此，提出了遗传算法（GA）解决这个优化问题。 测试了这种方法关于DFLP文献的一些测试问题。 结果显示了算法的有效性。

关键字:动态设施布局问题；连续布局；柔性区带结构；不等面积；遗传算法

1 引言

动态设施布局问题通过在规划范围之内考虑变更各部门之间物料流量来扩展静态设施布局问题（SFLP）。这个问题可能导致布局的重新排列。现实条件下，如果物料不流动，SFLP将适合改变了很长时间，并考虑到大部分的现在工作的地方在变，所以学习了动态设施布局问题（DFLP）将是必要的。

基本的DFLP是由于物料流量的变化部门之间的规划视野。 规划地平线分为几个周期，定义为周，月，或年。 SFLP的解决方案是单一布局; 但为了DFLP，它是每个布局的一系列布局（布局图）与特定时期有关。 因此，总成本布置图由材料处理成本,组成所有期间和重新排列成本的总和。

对于每个时期，DFLP可以被认为是SFLP并且每个SFLP被独立地解决。 虽然创建一系列布局可能具有较低的材料处理成本，重新排列的过度成本将是不经济的（例如，重型机器可能需要移动）。 所以以下应始终考虑两项成本平衡。 1）当重新排列未完成时，物料流的额外成本将会存在; 这似乎是有必要的。 2）额外的重新安排费用是由于设施移动可能导致生产线停产，需要特别工具，人力等。

因此，DFLP包括为每个选择静态布局期间再决定是否改为不同布局在下一个时期或不是。 如果重新安排费用相当低，布局配置会趋向于更频繁地更换以保持材料处理效率。高重新排列成本是相反的。

通常，在DFLP文献中，目标函数最大限度地减少了所有时段的物料搬运和重新排列的成本。 通常的区别目标函数与重排成本有关，具体取决于问题。 部门重组成本可分为两类：固定成本和可变成本。 固定成本定义为不依赖的成本有多少部门已经重新排列。 相反，可变成本是根据部门的运输距离和部门规模的增减。他们使用DFLP文献中的大部分论文固定重排成本。

设施布局问题分为NP难题。 其复杂性由于具有多个周期而增加（多个周期导致解决方案空间的增加问题）。 为了解决这个问题，合理的时间找到一个优质的解决方案，有必要选择一个强大的元启发式算法。如今，遗传算法在许多领域都被使用，因为具有搜索并行复杂空间的能力防止实现局部最优解。 在最近多年来，遗传算法已经开发出来解决了设施布局问题[8-20]。 在本文中，遗传算法用于解决动态设施布局问题灵活的柔性区带结构。 在灵活的框架结构（FBS）中，每一个问题被分配到具有不同宽度的并行托架。

本文的结构如下：第2节提供了DFLP和FBS的文献综述。 在第3节，提出了使用FBS与不等面积部门的DFLP的数学公式。 在第4节，遗传提出了DFLP算法。 在第5节，案例问题并提及参数和使用的设置对所提算法的测试进行了讨论，最后得出结论。

2 文献评论

解决DFLP的数学公式可以基于几个模型的类型，允许复杂的关系涉及布局问题的不同要素表达。 取决于问题的方式制定，即离散或连续。 罗森布拉特[21]是率先引进DFLP。 他用了两种启发式方法基于动态规划来解决DFLP。 罗森布拉特考虑到部门平等地位，采用离散布局。

在离散布局中，通常考虑的问题是二次分配问题（QAP），其中植物地板是分为相同面积的矩形块形状，每个块分配给一个特殊设施。 如果设施有不同的地区，那么他们就占了几个块[22,23]。 一般来说，这种布局设计被用于DFLP。 关于离散布局，许多研究都有已经完成，其中一些如下：

Conway和Venkataramanan [10]使用遗传算法来解决DFLP。 Balakrishnan和Cheng [11]调查了Convey的遗传算法并进行了改进。Baykasoglu和Gindy [24]已经开发了DPLP的模拟退火算法（SA）。 使用测试问题，他们表明他们的算法执行得比较好Conway和Venkataramanan的遗传算法（GAs）[10]和Balakrishnan和Cheng [11]。 Balakrishnan等人[12]提出了一种混合遗传算法来解决DFLP。然后在交叉运算符中使用动态规划创造后代，CRAFT用于突变。麦肯多尔 [1]提出了DFLP的两种模拟退火启发式。 第一个启发式是SA的直接改编解决DFLP。 第二个SA启发式是一个修改第一个SA，加上追溯策略。

由于离散模型的特殊限制，一些作者认为连续模型是合适的。离散的型号不适合表示车间设施的确切位置，也无法形成正确的型号由于一些特殊的制约因素，如设施方向，设施之间的空白空间和输入/输出点。在连续空间，设备停留在连续工厂一种他们没有任何重叠的方式。 Montreuil和Venkatadri [25]提出DFLP具有不平等的部门和形状不同的第一个配方。在他们的模型中，部门在最终布局中的职位是已知的。另外，部门连续时期的区域增加和边界各期各部门应在下一期同一部门范围内。数学公式不需要二进制变量，因为部门对的相对位置是已知的。因此，大问题可以解决为最佳。这个线性规划模型由Montreuil和Laforge [26]放宽了部门的假设连续时期的区域增加，边界的增加，且各期各部门应在下一期同一部门范围内。如同Montreuil和Venkatadri [25]，数学公式是线性的，因为各部门的相对位置未来可能由设计人员指定，固定的重新安排费用不予考虑。

Lacksonen [27]提出了一个两阶段的启发式解决方案与不平等地区部门的DFLP。 在第一阶段，全部部门假定具有相同的大小和DFLP同等面积的部门由切割机解决启发式呈现在Lacksonen和Enscore [28]。 在第二阶段，对于每个时期，静态不平等的区域设施布局问题是由Montreuil修改了MILP[29]。 第二阶段包括约束，确保了部门和时间段，首先没有重新排列阶段，也不在第二阶段重新排列。 Dunker等人[13]扩展了Dunker等人提出的GA [14]解决与不平等地区部门的DFLP。 作者使用了混合方法，结合动态规划遗传算法。 动态规划用于评估每个基因的适应度。

董等人[30]在动态商业环境下考虑了DFLP，其中可能添加新机器进入旧机器可以从工厂移除。 他们使用拍卖算法来解决最短路径问题并提出了基于模拟退火算法的最短路径来解决优化问题。麦肯多尔 [31]使用边界搜索技术沿线现有部门边界部门解决不平等的DFLP问题。 他们用禁忌搜索（TS）启发式来改进解决方案。

在文献综述布局问题上，有研究者一直在使用一个有趣的方法在标题下灵活的框架结构来表示布局方案。这个方法，限制了连续布局的状态问题第一次被Tong [32]提出在基于柔性区带结构和遗传算法求解动态设施布局中，厂房面积为分为水平或垂直间隔，其中每个的宽度是灵活的，依赖于部门的数量位于那个柔性区带（每个区带的宽度是从获得的分配给各部门的划分结果那个海湾由植物地板的最小边）。另外，每个海湾设置的海湾和部门的数量可变（灵活）。应该提到在问题基于灵活的海湾结构，由于控制部门的“形状，使用最大宽高比的因子。后提出灵活柔性区带结构的理念，泰特和史密斯[15]使用遗传算法来解决动态设施基于弹性区带结构的布局问题。他们显示两条染色体的问题解决方案。第一条染色体是部门的排列，显示了序列每个海湾的部门。第二条染色体包含关于区带和休息的数量的信息积分。

Arapoglu等人[16]已经使用遗传算法考虑输入和输出点来解决FBS。Kulturel-Konak等人[33]使用禁忌搜索算法解决FBS问题。 Enea等[17]使用遗传算法来解决FBS在需求时的布局问题生产是可变的。因此，按顺序使用模糊数计算物料流量。 Konak等人[34]MILP是找到最优的第一个确切方法FBS解决方案。他们通过使用收紧了他们的模型约束，其包括去除对称解，增加问题的下限和减少模型退化。然后他们解决问题达14部门正确。诺曼等人[18]考虑了设施在布局问题的判断条件下不存在连续规模的材料处理成本使用数学期望和标准偏差相关用于预测生产和解决遗传遗传基于随机数的编码算法。

Aiello等人 [19]，考虑多准则，研究多目标条件下的布局问题。 他们解决了基于弹性舱结构的布局问题遗传算法和电荷法，考虑材料处理成本标准，所需邻接尺度，所需距离刻度和形状比。 他们消除了使用形状比目标函数的形状比限制。 在遗传算法的不同步骤中，它总是生成可行的布局，不需要具体的策略在遇到形状比的约束。 Kulturel-Konaket al。 [35]考虑了设备重新发布问题的灵活的区带结构，并通过TS算法进行了解决。

Alagoz等人 [20]考虑了假设通过方式，输入输出点为FBS问题，并使用遗传算法来解决它。 在2010年，Wong和Komarudin [36]使用ant系统算法（ASA）和Kulturel-Konak和Konak [37]使用了蚁群优化（ACO）解决布局问题灵活的海湾结构。 他们使用虚拟部门来解决这个问题。

考虑到没有关于灵活舱的研究报告结构被用于动态设施布局领域因为基于灵活的布局所需的柔性区带结构，本文旨在扩展研究动态设施布局区域灵活的柔性区带结构。此外，提出了一种解决遗传算法的遗传算法。

本文用于构建基于DFLP的解决方案在FBS下，假设如下：

1.最大长宽比用于控制部门形状。

2.部门可能会有不平等的地区。 换一种说法，它们的形状是正方形或矩形。

3.部门区域每个时期都是固定的，但可能有所不同，从一个时期到另一个时期。

4.部门取向可以改变（即，部门可以是水平的或垂直的）。

5.每个时期的布局都使用厂房的连续表示。

6.部门应分配不同的并行托架宽度 如果一个部门被分配到一个海湾，它必须是完全填满。

7.目标函数最小化了成本的总和材料处理和重新排列。 重组成本包括固定成本和可变成本。

3 DFLP的数学公式

在本节中，基于FBS的MILP公式提出了具有不等面积的DFLP，其产生a连续布局和部门只能分配具有不同宽度的平行隔间。 类似的表述SFLP由Konak等人 [34]虽然他们配方是静态的。 首先，符号如下。

索引

其中T是周期数

其中N是部门的数量

其中k是海湾的数量

参数

W 厂房宽度

H 厂房的长度

在t期间的海湾最大并行数

时期t部门面积要求

t期的部门长度的最大允许面

t期的部门长度的最小允许面

时期t部门i到部门j物料流量

物料流量在i和j之间的部门之间周期t（上三角矩阵）

时期t在部门i和j间每单位移动的成本材料之间的单位距离

开始时期t内i部门重组的固定成本

t时期内部门i重组的可变成本

变量

在时期t内k的宽度（长度在x轴方向）

在时期t内k的高度（长度在y轴方向）

在时期t内部门i的高度（长度在y轴方向）

时期t内部门i的质心坐标

在时期t部门i和j在中心之间的水平距离

在时期t部门i和j在中心之间的垂直距离

部门i从时期t-1到t水平量运动

部门i从时期t-1到t垂直量运动

如果部门i在时期t被分配到湾k取1，反之，取0。

如果湾k在时期t被占用取1，反之，取0。

如果i在第t期在同一个海湾的部门j以上取1，反之，取0。

如果部门i在t期开始重新排列取1，反之，取0。

在模型描述中，不失一般性，植物地板的长边沿水平轴线方向，并且假定托架垂直运行。 此外，车间西南角的坐标为（0,0）。

混合整数规划（MIP）公式为弹性湾结构问题如下：

<stron

剩余内容已隐藏，支付完成后下载完整资料</stron

资料编号：[25457]，资料为PDF文档或Word文档，PDF文档可免费转换为Word