文摘

机械零件单元形成问题(MPCFP)是一个np难优化问题,由分组的设备和部件的一组细胞,这样每个单元可以独立运作和注液电池运动减到最少。这个问题主要是解决在文献中通过使用不同的技术从经典方法如线性规划自然metaheuristics更现代。在本文中,我们提出一个有效的并行版本的候鸟优化metaheuristic MPCFP的解决。候鸟优化人口metaheuristic基于V-Flight迁徙鸟类的形成,这是形成被证明是一种有效的节能。这种方法提高了并行程序的智能结合显著提高性能的几个metaheuristic执行的排序过程。我们执行计算实验1080基准组合而成的90个知名MPCFP实例与12个分类配置,没有线程。我们说明了有前景的结果,建议能够进入全球最佳在所有情况下,而对非平行的方法是解决时间明显减少。

1。介绍

机械零件单元形成问题(MPCFP)是基于著名的成组技术(GP) [1广泛应用于制造业。MPCFP的目标是组织一个制造厂的一组细胞包含一个有限数量的机器和零件,但减少cell-interchange部分。目的是为了降低成本,提高生产率。已知MPCFP赋权,所以总是有挑战的生产高质量的解决方案在一个有限的时间间隔。在过去的几年,一些技术已经成功地应用于这个问题,线性规划等数学方法(2)等经典metaheuristics粒子群优化(3等)和更现代的人工鱼成群(4]。

在本文中,我们提出一个新的、有效的并行版本的候鸟优化metaheuristic MPCFP的解决。候鸟优化(MBO)是一个基于metaheuristic灵感来自于v型飞行受雇于鸟类迁徙时。这种技术是非常有效的节能在飞行。这个有趣的方法是增强通过精确的集成高效的排序的并行程序尤其是鸟类和邻近的解决方案。它导致性能显著改善整个求解过程。我们执行的计算实验通过使用90个知名MPCFP实例,2众所周知的排序算法,1顺序配置5线程配置(1、4、8、16和32)导致1080基准。结果是鼓舞人心的,建议能够进入全球最佳在所有情况下,而对非平行的方法是解决时间明显减少。

这项研究的大纲如下。节2在相关工作,我们提供一些信息。部分3描述了MPCFP和模型。部分4MBO的概述。部分5描述如何使用MBO解决MPCFP平行。部分6提出并讨论了实验结果。部分7结论和未来工作提供指导。最后,附录提供了详细的结果为1080年的基准,在每一个包括90个测试实例。

2。相关工作

进行了调查问题MPCFP如下:线性规划(5),一个目标规划模型(6),一种混合遗传算法(7),布尔可满足性(8),约束编程(9),并使用一个人工鱼群算法(4]。细胞形成的进化问题的分析可以发现在10,11]。随着MPCFP是np难问题,许多研究人员认为metaheuristics应用近似方法。各种领域的研究可以发现metaheuristics,。执行搜索使用迭代过程,使解决方案从一个到另一个在搜索空间。这种类型的metaheuristic执行运动社区当前的解决方案,这意味着它有一个扰乱性的本质。metaheuristics基于轨迹,其中我们模拟退火(12- - - - - -14),禁忌搜索(15- - - - - -17),本地迭代搜索(18,19),和本地变量搜索(20.),也有另一种类型的metaheuristics基于人口。人口metaheuristics有一组个人,每一个编码一个临时解决方案。这些metaheuristics使用每个单独的健身评价函数,目的是获得最佳值的人口解决优化问题。此外,还有干扰算法,指导个人的人口或部分的可能的解决方案更好的健康。在这些人群metaheuristics,蚁群优化(21,22),粒子群优化(3,23,24),猫群(25,26),和候鸟优化(27)可以在混合flowshop调度等问题,总flowtime最小化(28),闭环布局与精确的距离在柔性制造系统(29日MPCFP[],初步结果30.]。简要回顾产品表面为优化算法可以在找到31日]。

制造业和工业领域的应用程序,使用metaheuristics并行实现已经解决,如掌握和网格计算解决位置区域问题[32),性能分析的粗粒度并行遗传算法在多核Sun Ultra SPARC T1 (33),为多级并行遗传算法不受约束的批量问题34),和一个迷因算法和并行hyperheuristic island-based 2 d模型包装问题35]。我们还可以找到研究使用并行metaheuristics的合作并行metaheuristic生产配送车辆路径问题(36)和优化共享内存之上hyperheuristics参数化metaheuristics [37),最后,我们可以找到一个实现并行性的最新进展与metaheuristics包含在下列工作(38]。

不同的研究并行排序算法解决大规模并行分类合并连接在主存多核数据库系统(39),一个高效的并行归并排序固定和可变长度的密钥40),随机并行排序算法的实验研究[41许多核心架构),排序算法基于自适应双调的排序(42),连续快速排序的性能比较和并行快速排序算法(43),所获得的利润的时间快速排序算法的并行化用于数值排序(44),一个高效的大规模并行快速排序(45),最后,快速排序的快速并行实现及其性能评估在10000年太阳企业(46]。

在本文中,我们选择了metaheuristic MBO,因为它有一个友好的设计,由两个链表的每个群的鸟和一个节点作为一个领导者的鸟。此外,MBO被应用到各种优化问题有前景的结果(47- - - - - -49]。我们专注于一个有效的并行排序MBO解决MPCFP时,我们的知识尚未报道。已经选择排序算法的并行化MBO因为4 8个步骤的MBO metaheuristic使用排序算法,因此我们认为,应用并行排序这些步骤可以实现MBO算法执行时间的减少。

3所示。机械零件细胞形成的问题

机械零件单元形成问题(MPCFP)是np难优化问题;的主要目标是形成的机器和零件组,注液电池运输部分的数量最小化。因此,初始矩阵(见矩阵表1)必须被转换成一个矩阵,一块对角结构(细胞很容易可见;看到矩阵表2)。这个示例使用以下参数:对应于一个MPCFP 5机器,7部分,= 3 2细胞。获得的最优值是0,和最后的关联矩阵由矩阵的结果吗和(见表3和4)。

一个严格的数学公式MPCFP由Boctor给出的2]。问题是由以下数学模型:(我)参数、指数和集:(一) ,二进制机械零件关联矩阵, (b) 机器的数量,(c) 的部分,(d) 细胞的数量,(e) 机器的指数(),(f) ,该指数的部分(),(g) ,该指数的细胞(),(h) ,每个细胞机器的最大数量。(2)变量和域:(一) ,加工单元矩阵, (b) ,一部分细胞矩阵, (3)目标函数: (iv)受制于以下约束:

4所示。候鸟优化

候鸟自然人口metaheuristic优化(MBO)是一种基于v型飞行的候鸟50,51),被证明是一个有效的形成在节能52]。在v形(图所示1),翼端间距等参数(WTS),机翼的最大宽度()、v形角()和深度和翼展()是重要的,形成一个有效的v形53,54]。算法的概念之间的相似性参数的MBO实际迁移的鸟类在Duman V-flight形成了et al。27]。这个表中描述的概念相似5。

MBO始于许多初步解决方案V-flight形成相应的鸟类。这些解决方案生成随机选择和解决方案领导者鸟;然后剩下的鸟类交替分布的羊群。在下一步中,旅游,提高领导者的解决方案是通过生成和评估其执行邻居。对于每一个解决方案在羊群(领导除外),尽量改善通过评估其邻居和未使用的最好的邻居在前面的解决方案。推动领导解决,之后的一个解决方案的领导者地位。最后,当迭代结束后,返回羊群的最佳解决方案。算法1描绘了MBO的经典程序算法。

5。解决MPCFP使用MBO和并行排序

解决问题的第一步与MBO metaheuristic MPCFP是一个适当的集成。在这个意义上,我们概念化每只鸟的羊群(包括群的领袖)作为一个可能的解决问题的办法MPCFP(见图2)。鸟儿将由一个矩阵和矩阵。这些矩阵迭代修改而失效的问题。此外,他们将被用于计算MPCFP适应性问题。

5.1。生成初始解决方案

生成初始解,考虑下面的输入:机器= 4,= 5,部分细胞= 2,= 2,一个矩阵(见表6)。

考虑到数据表6,第一步生成一个初始解如下。

步骤1。生成随机分配矩阵与一些随机的方法。这个矩阵(见表7)满足约束,只存在于一台机器在一个细胞小于或等于2在整个细胞。

步骤2。与手动生成矩阵的方法从矩阵。为此,建立连接的矩阵和矩阵的解决方案。在细铅字的机器对应单元1号,2号粗体,机器对应于细胞(见表8)。

手动确定矩阵的方法涉及添加值1的位置,的临时数组的矩阵,将这个值金额根据相应的细胞。我们为每个值执行操作的位置,矩阵的(见表9)。

例1。(我) 是与细胞相关联的值1;我们将这个值添加到行。(2) 是与细胞相关联的值2;我们增加这个值的行。(3) 是与细胞相关联的值2;我们增加这个值的行。(iv) 是与细胞相关联的值1;我们增加这个值的行。

步骤3。从表的结果9,我们构建一个矩阵的部分解决方案(见表10)。

步骤4。找到可能的解决方案。

我们必须选择的值的位置,属于临时矩阵每一行的最大价值。随后,我们更换更大的值分配值1,我们指定其他值的行值0(见表11)。的画,整个行人数相等,我们保持不变如果头寸的价值是1。如果相同的数量大于1,每个数大于1,我们分配值为1。

我们考虑行值等于1,在这种情况下对应行用于修饰或说明机器3和4。从这个角度,我们生成所有可能的组合矩阵和随机选择一个(见表12)。

5.2。产生邻近的解决方案

生成一个邻近的解决方案,我们认为以下输入:机器= 4,= 5,部分细胞= 2,= 2,矩阵,矩阵,矩阵(见表13)。

步骤1。随机选择一个位置,在矩阵的值为1,我们与机器相关的行。这是一样的选择一台机器和使用它的行。在这种情况下,我们选择了随机矩阵的位置值为1,对应于机器2(见下表14)。

步骤2。机器2上,我们随机选择一个细胞有一个0。在这种情况下,我们选择的位置矩阵;我们完成一个替代的价值0到1,最后实现替代值为0。你可以看到这个操作在表的结果15。约束不一致的情况下,你必须重复步骤1的过程。

步骤3。我们进行建设的矩阵使用手工方法解释部分5.1。

5.3。流程图的候鸟优化

本节描述算法MBO的阶段,因为它集成了MPCFP问题的应用和阶段平行排列的算法。为了更好的理解,已经包括一个流程图(见图3),分为4个主要阶段:初始化算法,参观过程中,领导人更换,算法结束。

5.3.1。算法初始化

参数初始化(阶段1图3)。在这个阶段,MBO metaheuristic所需的所有值的初始化;所需的所有值的问题MPCFP这类型的排序算法在metaheuristic中实现。

在metaheuristic值,有(我)鸟类的数量(),(2)邻居的数量(),(3)旅游的数量(),(iv)许多共享的解决方案(),(v)的迭代次数()。

和之间的互补metaheuristic参数,我们可以包括(我)领导人交换模式中,有两种类型的领导人的变化;交换的领袖继承人和交流最好的领袖;(2)那种类型应用于最初的鸟类群,那里是一个订购与随机的鸟类群和另一个鸟类要求根据他们的健康。

在MPCFP所需的参数问题,(我)关联矩阵(),(2)机器的数量(),(3)数量的部分(),(iv)细胞的数量(),(v)最大数量的机器在一个细胞()。

最后,对于排序应用于MBO的类型,我们有以下参数:(我)类型的排序算法:快速排序和归并排序。(2)排序方法:正常或线程。(3)如果需要的线程数量。生成初始解决方案(第二阶段在图3)。在这个阶段,我们根据部分中描述的方法生成初始解5.1。这些解决方案必须满足的三个约束条件模型MPCFP。

创建初始群(第三阶段在图3)。从最初的解决方案,我们创建一个数组的鸟类,并最终创建有序排列的概念v形鸟。,我们指定数组中的第一个位置(第一个解决方案)的领导人,我们执行一个交替分布的鸟类之间的羊群的鸟类。我们必须考虑到鸟儿总是按健身从低到高排序,较低的鸟健身最好的解决问题的办法(MPCFP是一个最小化问题)。此外,我们必须考虑,这是一个阶段,我们将并行快速排序和归并排序。

5.3.2。旅游的过程

内部有两个子阶段:这个阶段的发展领袖鸟和其他鸟类的演化。领袖鸟的进化阶段有一个阶段(生成邻国解决方案领导者)和其他鸟类的进化阶段两个阶段(生成其他鸟类和邻近的解决方案共享邻国领导人所使用的解决方案,不与其他鸟类)。

生成邻国解决方案领导者(阶段4在图3)。这个阶段包括生成邻国解决方案根据部分中概述的步骤5.2。随后,这些邻国解决方案通过一个并行排序算法排序;看到算法MBO(线(5)算法1)。

其他鸟类产生邻近的解决方案(第五阶段在图3)。在这个阶段,我们创建邻国解决群的鸟儿;那么这些鸟类的排序算法的并行排序;看到线(7)和(8)算法MBO(算法1)。

分享邻国领导人所使用的解决方案,不与其他鸟类(阶段6在图3)。共享领导的其他邻国解决方案与其他鸟类的v形的;这样做是交替地从左到右或从右到左。分享邻近的解决方案后,我们进行了排序使用的并行排序算法中所有相邻的解决方案,每只鸟群(不包括领导)。

领导人更换(阶段7图3)。在这个阶段,我们进行了更换领导人;我们选择最近的接班人;也就是说,选择鸟类接近领导人之一。继任者将取而代之,领导人将年底的羊群。我们必须考虑到,如果我们选择继任者属于羊群的左部,领导会通过左边部分的结束。同样的过程也适用于群的正确的部分(参见算法2)。

算法终止(阶段在图83)。在这一步中,获得领导的健康;此外,一种将响应矩阵显式;也就是说,我们建立一个关联矩阵根据给出的顺序矩阵的解决方案和。订单根据指数小于大多数的机器和零件(见算法3)。

5.3.3。排序算法

对于MBO,我们使用两个排序算法,归并排序和快速排序,我们执行顺序和并行使用线程。

归并排序。它是1945年由约翰·冯·诺依曼开发的。这是一个搜索算法的复杂性(见表16)。算法4演示了一个一般的伪代码归并排序。

快速排序。这是查尔斯·理查德·霍尔在1959年形成的。这是一个搜索算法的复杂性(见表16)。算法5说明了一般的快速排序的伪代码。

6。计算实验

6.1。配置标准

MPCFP性能评估实验使用从Boctor 90个测试实例的实验中,由10问题考虑5的值与考虑4和10个实例的值与。测试数据是可用的(55]。90实例执行31倍使用12种不同配置的顺序和并行排序(见表18)。我们还必须考虑到排序算法(顺序和并行)应用于以下阶段(见图3MBO的):(我)第三阶段创建初始群。(2)第四阶段生成邻国解决方案领导者。(3)第五阶段产生邻近的其他鸟类的解决方案。(iv)阶段6分享邻国领导人所使用的解决方案,不与其他鸟类。

优化算法使用并行排序编码在Java版本1.8.0_40 Mars.1 Java开发人员使用Eclipse IDE版本发布(4.5.1)。为运行并行排序的MBO,我们使用Java (TM) SE运行时环境(构建1.8.0_40-b27)。MBO被描述在表的参数值17。最后,运行实例的硬件特性MacBook Pro电脑(视网膜,13英寸,2013年末)与英特尔酷睿i5处理器速度= 2,4 GHz;处理器的数量= 1;核心的总数= 2;L2高速缓存/核心= 256 KB;L3缓存= 3 MB), 4 GB RAM 1600 MHz DDR3,虹膜和显卡英特尔1536 MB运行OS X埃尔卡皮坦版本10.11.2网(15)。

6.2。结果

表19和20.代表附录中提供的结果的摘要一个(55]。这些汇总表描述90年的平均结果实例。第1列(线程)对应的标识符分配给线程的数量用于搜索算法。第2列(执行time-BET)显示获得的最好的执行时间,以毫秒为单位。第三列(执行time-AVG)描述的平均时间在毫秒执行MBO的最好时间。列4(执行time-ST)代表的标准差执行通过MBO的最佳时间。列5 (cycle-BC)显示了循环的最优值。列6 (cycle-AVG)描述的平均周期。列7 (cycle-ST)代表标准差。列8(时间cycle-BTC)显示的最佳周期时间最优值被发现,以毫秒为单位。 Column 9 (time cycle-AVG) describes the average cycle in milliseconds. Column 10 (time cycle-ST) represents the standard deviation in milliseconds. Finally, we must consider all tests that have achieved the global optimum.

执行时间分析。执行时间是metaheuristic时的总时间在搜索空间中寻找最好的解决方案。从这个意义上讲,根据表中描述的是什么19和20.归并排序算法,我们可以考虑使用8线程最低平均时间(152.7333 ms)运行90个实例(见专栏2:执行time-BET表19和20.)。此外,当我们比较次的顺序运行metaheuristic(没有线程和使用归并排序算法),关于metaheuristic与线程运行的最佳时间(8线程),我们可以看到,使用8线程是一个改善的执行时间metaheuristic。这种行为也可以出现在表19和20.(见专栏3:执行time-AVG表19和20.)。

周期分析。循环完成后替换群的领袖(阶段在图73)。目前2591次迭代的参数(),我们可以达到38周期。因此,羊群在算法的领导人改变其价值38次。基本上,周期,取得最佳值在执行完成之前,为我们提供了信息,减少迭代时间分配在metaheuristic输入参数。考虑周期的值(见专栏6:cycle-AVG表19和20.),我们可以近似的平均价值在9日的周期找到全局最优,同时使用归并排序和快速排序,线程和线程。同时,这涉及到减少迭代的值限制。但是我们也必须考虑随机因素有metaheuristic(见第二阶段在图3第四阶段,如图3,第五阶段在图3),这种随机性允许寻找全局最优的可能性较少的周期(见专栏5:cycle-BC表19和20.)。因此,这是一个建议的改变,但这还不够,总能找到全局最优。快速排序算法使用线程有不规则的时间甚至比快速排序顺序使用。

时间周期分析。相对于最优的平均周期时间被发现,我们注意到,根据测试,归并排序算法与8线程已经最少的时间(见专栏9:时间cycle-AVG用于表19和20.。它应该被认为是有趣的结果,因为它取得了更好的*使用并行排序和顺序排序,主要是通过使用归并排序和4,8,16个线程和快速排序与16个线程(见专栏8:时间cycle-BTC表19和20.)。

7所示。结论

在本文中,我们使用一个候鸟优化算法的并行排序解决机械零件细胞的形成问题。计算实验使用传统的硬件资源已经在90年进行的测试实例,2众所周知的排序算法,1顺序配置,和5个线程配置(1、4、8、16和32),给1080基准。主要结果中,我们强调解决MPCFP MBO的新校准参数。新的配置由以下参数值:鸟类的数量(),邻居的数量(),旅游的数量(),许多共享的解决方案()和迭代次数()。我们观察到下降周期从38到9,这意味着领袖群达到周期9号有一个非常高的概率找到全局最优;因此,我们可以减少迭代的数量限制来。这个数量的观察周期应用于所有基准。

此外,重要的是要注意,快速排序使单机变量次MBO的执行(见列9:时间cycle-AVG表20.)。有情况下快速排序算法没有线程中运行;甚至比线程运行时更有利。否则,归并排序算法,我们发现有前景的结果。我们可以考虑,归并排序算法在执行时间上减少使用8线程显示了一个使用顺序排序算法相比。

指导未来的研究中,我们可以应用不同的方法生成初始解决方案以及产生邻近的解决方案。我们还可以与其他排序算法实现MBO进行比较。

附录

答:基准测试的细节

. 1。Boctor的问题

表21描述测试的90个实例的配置。表的描述给出以下属性:第1列(ID)对应的标识符分配给每个实例。第2列的标识符(Boctor的问题)代表10 Boctor的问题。第三列(细胞)细胞的数量。列4 (每单元)对应于机器的最大数量。列5(选择)描述了给定的最佳全球问题。

由信用证。实验结果

表22,23,24,25,26,27,28,29日,30.,31日,32,33高对比度时代通过使用不同的排序算法。这两个表有相同的标题,如下所述:第1列(ID)对应的标识符分配给每个实例。列2(选择)描述了最优值为给定的问题。列3 (optimum-MBO)描绘了最佳值达到通过候鸟优化。列4 (optimum-AVG)的平均值31执行被描述。列5 (optimum-SD)代表标准差。列6 (optimum-RPD %)代表最著名最优值之间的差别和最好的最优值达到了MBO的百分比。列7(执行time-BET)显示获得的最好的执行时间,以毫秒为单位。列8(执行time-AVG)描述的平均时间在毫秒执行MBO的最好时间。列9(执行time-ST)代表的标准差执行通过MBO的最佳时间。 Column 10 (cycle-BC) shows the cycle in which the optimal value was found. Column 11 (cycle-AVG) describes the average cycle. Column 12 (cycle-ST) represents the standard deviation. Column 13 (time cycle-BTC) shows the best cycle time in which the optimal value was found in milliseconds. Column 14 (time cycle-AVG) describes the average cycle in milliseconds. Column 15 (time cycle-ST) represents the standard deviation in milliseconds. Finally, it describes the average time for each column.

相互竞争的利益

作者宣称他们没有利益冲突有关的出版。

确认

鲍里斯Almonacid支持研究生授予2015年天主教大学德瓦尔帕莱索(INF-PUCV 2015)。里卡多·索托支持格兰特CONICYT / FONDECYT / INICIACION / 11130459。Broderick克劳福德支持格兰特CONICYT / FONDECYT /普通/ 1140897。费尔南多帕雷德斯支持格兰特CONICYT FONDECYT / 1130455。