英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
基于柔性区带结构的动态设施布局问题并通过遗传算法求解
摘要：动态设施布局问题（DFLP）的基础考虑，在工厂内多个部门寻找职位，同时最大限度地减少材料处理和重新布置成本。在本文中，研究了一种使用柔性区带结构的新型DFLP。在工厂布局中，基于灵活的托架结构，部门分配到厂房内的并行托架。部门可以是自由导向的，并且可能具有不平等的区域以及为了找到最佳解决方案而制定的混合整数规划。由于复杂性，使用精确的方法只能在逻辑时间内解决小尺寸问题。因此，提出了遗传算法（GA）来解决这个优化问题。在DFLP文献的一些测试问题上测试了该方法。结果表明该算法的有效性。
关键字：动态设施布局问题；连续布局；灵活性结构；遗传算法
1介绍
动态设施布局问题通过考虑部门之间物料流量在规划范围内的变化来扩大静态设施布局问题（SFLP）。
这个问题可能导致布局的重新排列。在实际情况下，如果材料流量长时间不变化，并且考虑到现在大部分工作场所正在发生变化，SFLP将是适用的，所以需要研究动态设施布局问题（DFLP）。
基本的DFLP是由于部门之间在规划期间的物料流量变化。 规划范围分为几个周期，周期，月份或年份定义的时间段。SFLP的解决方案是单一布局;但是对于DFLP，它是一系列布局（布局图），每个布局与特定周期相关联。因此，布图规划的总成本包括所有期间的材料处理成本和重排成本的总和[1]。
对于每个时期，DFLP可以被认为是SFLP，并且每个SFLP被独立地求解。 虽然创建的一系列布局可能具有较低的材料处理成本，但是重新布置的过多成本将是不经济的（例如，重型机器可能需要移动）。所以以下两个成本平衡应该总是被考虑[2]：
·当重新排列未完成时，物料流的额外成本将会存在; 这似乎是有必要的。
·额外的重新安排成本是由于设施搬迁可能导致生产线停产，需要专用工具，人力等等。
因此，DFLP包括为每个周期选择一个静态布局，然后决定是否在下一个周期中更改为不同的布局。如果重新布置成本相当低，布局配置往往会更频繁地变化，以保持材料处理效率。高重组成本相反是相反的[2]。
通常，在DFLP文献中，目标函数最大限度地减少了所有时段的物料搬运和重新排列的成本。通常，目标函数之间的差异与重新排列成本有关，这取决于问题。部门重组成本可分为两类：固定成本和可变成本[2]。固定成本被定义为不依赖于多少部门重新排列的成本。相比之下，可变成本是根据部门运输的距离和部门规模的增减。在DFLP文献中的大多数论文中，他们使用固定的重排成本。
设施布局问题分为NP难题[3]。其复杂性由于具有多个周期（多个周期导致问题的解空间增加）而增加。为了在合理的时间内解决这个问题，找到一个优质的解决方案，有必要选择一个强大的元启发式算法[4-20]。如今，遗传算法在许多领域都被使用，因为能够并行搜索复杂的空间并避免实现局部最优解。近年来，已经开发了遗传算法来解决设备布局问题[8-20]。本文采用遗传算法来解决灵活的框架结构的动态设施布局问题。在灵活的框架结构（FBS）中，问题分配到并行具有不同宽度的托架。
本文的结构如下：第2节提供了DFLP和FBS的文献综述。在第3节中，提出了使用FBS与不等面积部门的DFLP的数学公式。在第4节中，提出了一种用于DFLP的遗传算法。在第5节中提到了案例问题和参数，并讨论了用于测试所提算法的设置。最后，第6节得出结论。
2文献综述
解决DFLP的数学公式可以基于几种类型的模型，这些模型允许表达布局问题中涉及的不同元素之间的复杂关系。取决于问题的形成方式，即离散的或连续的。Rosenblatt [21]率先引进DFLP。他使用基于动态规划的两种启发式方法来解决DFLP。罗森布拉特认为部门平等，采用离散布局。
在离散布局中，通常考虑的问题是二次分配问题（QAP），其中工厂底层被分成具有相同面积和形状的矩形块，并且每个块被分配给一个特殊设施。如果设施有不同的区域，那么他们就占了几个块[22,23]。通常，这种布局设计被用于DFLP。关于离散布局，已经做了很多研究，其中一些如下：
Conway和Venkataramanan [10]使用遗传算法来解决DFLP。Balakrishnan和Cheng [11]调查了Convey的遗传算法并进行了改进。Baykasoglu和Gindy [24]已经开发了一个模拟的DPLP退火算法（SA）。使用测试问题，他们表明他们的算法比Conway和Venkataramanan [10]和Balakrishnan和Cheng [11]的遗传算法（GAs）更好。Balakrishnan等人[12]提出了一种混合遗传算法来解决DFLP。然后，在交叉算子中使用动态规划来创建子代，并使用CRAFT进行突变。麦肯多尔[1]提出了两种用于DFLP的模拟退火启发式方法。第二个SA启发式是第一个SA的修改，添加了回溯策略。
由于离散模型的特殊限制，一些作者认为连续模型是合适的。离散模型不适合表示设备在工厂车间的确切位置，也不能使适当的模型对称性特异性约束，导向距离，设施之间的空白空间和输入/输出点。在连续的空间中，设备停留在连续工厂中，与他们没有任何重叠。这些问题经常形成混合整数线性规划（MILP）。在DFLP上已经做了很少的工作，具有连续的代表性[22]。Montreuil和Venkatadri [25]提出了DFLP的第一个方案，具有不平等的地区部门和不同的形状。在他们的模型中，部门在最终布局中的位置是已知的。而且，各部门的时间间隔有所增加，各期各部门的界限应在下一期间同一部门的界限内。数学计算不需要二进制变量，因为已知对部门的相对位置。因此，大问题可以解决为最佳。这种线性规划模型由Montreuil和Laforge [26]进行了改进，放宽了各部门在连续时间内增加的假设，每个时期各部门的界限应在下一个时期内同一部门的界限内。类似于Montreuil和Venkatadri [25]，数学公式是线性的，因为每个可能的未来部门的相对位置由设计者指定，固定的重新排列成本不被考虑。
Lacksonen [27]提出了一个两阶段启发式解决与不平等地区部门的DFLP。在第一阶段，所有部门假定具有相同的规模，同等面积部门的DFLP由Lacksonen和Enscore提出的切割飞机启发式解决[28]。在第二阶段，Montreuil [29]对MILP进行了修改，解决了前所未有的问题。第二阶段包括制约因素，确保第一阶段没有重新排列的部门和时间段不会在第二阶段重新排列。Dunker等人[13]扩展了Dunker等人提出的GA [14]用不平等的地区部门解决DFLP。 作者使用了混合方法，结合动态规划遗传算法。动态规划用于评估每个基因的适应度。
董等[30]在动态商业环境下考虑了DFLP，其中可能添加新机器，或者可以将旧机器从工厂移除。他们使用拍卖算法来解决最短路径问题，并提出了基于模拟退火算法的最短路径来解决优化问题。麦肯多尔[31]使用边界搜索技术，将部门沿着现有部门的边界解决不平等的DFLP。他们使用禁忌搜索（TS）启发式来改进解决方案。
关于布局问题的综合评论，一些研究人员一直在灵活的框架结构标题下使用一种有趣的方法来表示布局方案。这种方法是第一次限制连续布局问题的状态，由Tong [32]在1991年提出。在基于柔性区带结构的布局中，植物地面分为地平线垂直结构，其中每个柔性区带是灵活的，取决于位于该柔性区带的部门的数量（每个柔性区带的宽度是从部门的分区结果获得的，这些部门由工厂底部分配给该柔性区带）。此外，每个柔性区带设置的柔性区带和部门的数量是可变的（灵活的）。应该指出的是，由于控制部门的形状，基于弹性舱结构的问题，使用了最大宽高比的因素。在提出灵活的桥架结构理念的基础上，Tate和Smith [15]利用遗传算法解决了基于弹性舱结构的动态设施布局问题。他们显示了两条染色体的问题解决方案。第一条染色体是部门的排列，显示了每个柔性区带内的一系列部门。第二条染色体包含关于柔性区带和断点数量的信息。
Arapoglu等人[16]已经使用遗传算法来解决FBS考虑输入和输出点。Kulturel-Konak等人[33]使用禁忌搜索算法来解决FBS问题。Enea等[17]使用遗传算法来解决FBS的布局问题，当需求生产变化时，模糊数字用于计算物流。Konak等人[34]提出了一个MILP，它是找到最优FBS解决方案的第一个确切方法。他们通过使用约束来收紧他们的模型，这些约束包括去除对称解，增加对问题的限制，减少模型退化。那么他们完全解决了14个部门的问题。诺曼等人[18]考虑了设备布局问题，在连续规模下不确定材料处理成本的条件下，使用与生产预测相关的数学期望和标准差，并将其编码用于随机数解决使用的遗传算法。
Aiello et al[19]考虑multicriterions,研究多目标条件下的布局问题。他们解决布局问题基于柔性区带结构利用遗传算法和electre方法,并考虑材料处理成本标准,要求邻接规模,规模所需的距离,和形状比率。他们消除形状比限制使用形状比目标函数。在不同的遗传算法的步骤,它总是产生可行的布局和不需要一个特定的战略遇到形状比例约束。Kulturel-Konak等[35]认为柔性区带结构设施relayout通过TS算法问题和解决它。
Alagoz等人[20]考虑了FBS问题的通过方式，输入和输出点等假设，并采用遗传算法进行求解。2010年，Wong和Komarudin [36]使用蚂蚁系统算法（ASA）和Kulturel-Konak和Konak [37]使用蚁群优化（ACO）来解决灵活柔性区带结构的布局问题。他们通过使用虚拟部门来考虑这个空位，这个问题。
考虑到在动态设施布局领域中使用的柔性湾结构没有研究报道，并且由于基于灵活柔性区带结构的布局具有所期望的质量，本文旨在扩大对区域中柔性湾结构的研究动态设施布局。 此外，提出了一种解决遗传算法的遗传算法。
本文用于构建基于FBS的DFLP解决方案，假设如下：
- 最大长宽比用于控制部门形状。
- 部门可能会有不平等的地区。换句话说，它们的形状是正方形或矩形。
- 部门区域每个时期都是固定的，但可能会有所不同。
4.部门取向可以改变（即，部门可以是水平的或垂直的方向）
5.每个时期的布局使用厂房的连续表示。
6.部门应分配不同宽度的并行托架。如果一个部门被分配到一个柔性区带，它必须被完全填满。
7.目标函数最大限度地减少了材料处理和重新排列的成本总和。重组成本包括固定成本和可变成本。
3 DFLP的数学公式
在本节中，介绍了一种基于FBS的针对具有不等面积的DFLP的MILP公式，其生成连续布局，并且部门应仅分配具有不同宽度的并行间隔。Konak等人提出了SFLP的类似配方[34]，虽然他们的表达是静态的。首先，符号如下。
索引
t=1,2,...,T 其中T是周期数
I,j=1,2,...,N 其中N是部门的数量
K=1,2,..., 其中k是柔性区带的数量
参数
W 工厂地板沿x轴的宽度
H 工厂地板沿y轴的长度
t期间最大平行间隔数
时期t部门的区域要求
时期t部门i的宽比
=min{W,} 第t期部门i的最大允许边长
= 第i期第t期最小允许边长
在第t期从部门i到部门j的物料流量
= 期间t（上三角矩阵）部门i和j之间的材料流量
单位物料搬运的费用在t期间i和j部门之间的单位距离
在第一阶段转移部门i的重新安排固定成本t
在开始阶段转移部门i的重新排列可变成本t
变量
在时段t的间隔k的宽度（x轴方向的长度）
在t期的湾k部门的高度
第i期在t期的高度（y轴方向的长度）
(, ) 时期t部门i的质心坐标
=|-|= t期间i和j部门中心之间的水平距离
=|-|= t期间i和j部门中心之间的垂直距离
=|-|= 第i期从t-1到t的垂直运动量
在模型描述中，不失一般性，植物地板的长边沿水平轴方向，托架假设垂直运行。此外，车间西南角的坐标为（0,0）。
弹性湾结构问题的混合整数规划（MIP）公式如下：
minZ=( ) ( ) (1)
取决于：
(2)
(3)
(4)
(5)
(6)
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[25430]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
