文摘

船块建筑空间是一个重要的瓶颈资源在造船的过程中,生产调度优化是提高造船效率的关键技术。关于船块建筑空间调度问题,混合启发式算法。首先,Bottom-Left-Fill (BLF)过程。接下来,一个初始解和角落通过指导排序过程。最初的解决方案的基础上,模拟退火算法(SA)是用来改善解决方案通过提供一种可能性接受糟糕的邻居为了逃离局部最优的解决方案。最后,进行了仿真实验验证了算法的有效性。

1。介绍

空间船的关键资源块施工过程。如何最小化最大完工时间的空间资源和优先约束下的项目是一个复杂的调度问题。至于这个问题,涉及到两个相关的问题:资源约束项目调度问题(RCPSP)和装箱问题。

RCPSP可以被描述为一个问题应该安排技术和其他约束条件的限制下,以满足项目的目标(1]。一般来说,我们的目标是获得最大完工时间最短的项目下的可用资源和优先约束。的方法可以分为两类:具体方法和启发式方法。哈特曼(2]提出RCPSP属于np难问题,因为它总是用于扩展机器调度问题(3,4]。所以问题规模的增大,计算复杂度会迅速增加。许多研究人员使用的算法来解决RCPSP [5,6];然而,他们中的大多数提议,精确算法在现实中并不可行。凯利(提出的优先级规则7]表明RCPSP可以通过启发式算法来解决。刘和王8]试图减少项目考启发式算法,取得了良好的效果。Bhaskar et al。9)利用并行方法和优先级规则解决RCPSP模糊活动时间。李等人。10)提出了一个船块建筑空间调度问题和描述这个问题从理论上作了阐述。Koh et al。11)解决了造船公司调度问题的启发式算法。

本包装问题是投入更多的盒子本为了最低高度有限。这个问题可以分为两类,二维和三维问题。前,研究人员往往通过启发式方法来解决装箱问题。他们是左下侧(提单)算法(12),Bottom-Left-Fill (BLF)算法(13]。此外,别洛夫et al。14)考虑采用一维问题求解二维问题。陈等人。15]试图解决二维问题的启发式随机社区结构。对于三维问题,最受欢迎的3 bf [16],提出的Silvano圆形石堡2000年,找出如何选择最合适的数据集的问题。Alvarez-Valdes et al。17]掌握/路径链接算法用于解决多个容器大小本包装问题。廖和许18发现新的下界来提高三维的效率问题。

本文组织如下。介绍后,部分2提出了一种数学模型。部分3给这个问题的混合启发式算法。节4我们进行仿真实验,验证了算法的有效性。部分5提出了通用的结论。

2。船块建筑空间调度问题

船块建筑空间调度问题可以描述为一个项目,包括活动;流程活动所需的地方。活动可以被定义为,在那里和代表的长度和宽度哪个活动的需求。活动的持续时间是。和活动的开始和结束时间吗。在项目过程中,的地方可以被定义为哪一个。

在项目过程中,每个活动都是优先约束下,我们建议活动的前辈吗。所以不能开始如果其前身之一吗还没有完成。我们假设整个项目的开始时间是0。为方便建模,我们还将介绍两个虚拟节点:0和活动。他们不需要时间和空间。0是所有的活动项目的前身;与此同时,是所有活动的继任者。所以项目的时间。此外,我们认为一个活动表示为一个立方体。所有的活动都可以在水平旋转90度,和和0,表明活动分别是旋转的,而不是。这个问题下面所示的模型:

在模型中,公式(1)是客观的问题,(2)提出了优先约束,(3)意味着两个数据集不能重叠。公式(4)- (7)表示,每个多维数据集应该在可用的地方完成。多维数据集可以水平旋转和0和1表示如果旋转立方体,公式(8)所示。

3所示。混合启发式算法

3.1。初始解的方法

在本文中,我们应用BLF获得初始解。BLF, Chazelle提出的131983年),属于启发式算法。在该算法中,将多维数据集的方法是由角(19]。

3.1.1。角落里

在BLF,重要的是找到角落的地方活动。首先,我们将尝试最低和最左边的点(最低点);如果这个位置可以匹配的活动,那么它的位置和更新的角落;否则,试下一点,直到找到一个角落。可以表示成的角落,在那里表明角落的位置代表点的可用空间- - - - - -- - - - - -维度。参见图1;和表示的长度和宽度,代表项目的持续时间。

3.1.2。Bottom-Left-Fill算法

在这篇文章中,我们代表活动的多维数据集的长度,宽度,高度是有限的。对于这些立方体,长度和宽度表示他们需要的长度和宽度,高度代表了他们所需要的时间。与此同时,我们认为不受限制的高度是时间表。已对所有活动时,总高度等于项目的持续时间。在这个过程中,我们发现活动可以放置在每一个时间点,然后考虑这些活动的顺序。我们把底面积较大的活动;如果相同,选择高度越高;如果仍然相等,选择较长的长度。我们描述了算法如下。(1)我们(平台船块嵌入地方建筑空间)在三维坐标系,把bottom-left-rear点原点(0,0,0),并把长度、宽度、高度,,分别轴。和代表的长度和宽度。(2)设置5组:,,,,。是一组活动已预定但尚未完成。是一组活动已经安排和完成。是一组活动,可以预定但尚未安排。是一组角,而是一组输入顺序的所有活动。(3)移动活动可以安排来然后将这些活动:首先,交换的活动,这样的长度和宽度可以满足任何活动吗;然后排序活动安置政策上面所提到的,应安排在第一个活动后排序。检测到的角落直到第一个合格的角落发现了- - - - - -- - - - - -规则,这意味着更小在角落里更好。然后,考虑到小。最后,选择较小。把bottom-left-rear活动所选的角落,将新元素和新合格的角落;同时删除角落使用这一次。按顺序记录的活动和他们的角落。(4)如果一个活动已经完成,把它从来然后移动它的最近的继任者来。类活动规则中提到(3)。重复(3)和(4),直到所有的活动都完成了。(5)选择越高项目的各个角落的持续时间。

3.2。优化解决方案方法

提出Steinbrunn et al。20.),模拟退火(SA)是一个metaheuristic算法提供了一个可能接受糟糕的邻居逃离局部最优的解决方案。直到1983年,柯克帕特里克et al。21)改变了这个想法,SA算法成功应用到旅行商问题。

陈等人。22)开发一种混合算法,可以从禁忌搜索思想都和样本模拟退火解决分布式调度问题。Bouleimen和Lecocq)23)实现SA RCPSP MRCPSP。Yannibelli和Amandi24)结合SA和其他算法来解决多目标项目调度问题。在SA算法中,我们描述了社区的修改订单的两个活动可安排在同一时间。代表温度下降速率,表示的初始值附近,代表了邻居生成温度下降后,表示当前时间,表示最短的时间到现在。我们的船块建设空间调度问题,SA可以描述如下。(1)初始化:初始和最终温度和,分别。该算法迭代从最初的解决方案。初始评价函数的值的评价函数值,而最初的最优解是。(2) 表示当前的温度和表示当前社区的长度。最初,。(3) 。(4)选择一个新的解决方案从社区的。(5)计算增量。(6)如果,接受作为一种新的解决方案,,;如果,然后,。其他接受作为一种新的解决方案与一个概率。(7) ,如果,转到步骤(4);其他步骤(8)。(8) ,,并比较和。如果,转到步骤(3);其他是满足终止条件和输出电流和;结束程序。

4所示。仿真实验

我们使用一系列的活动来验证算法。这些活动的参数如表所示1和活动的网络图呈现在图2。在实验中,有两个地方,,分别代表长度,宽度,和时间。位置1的长度和宽度是3,3,3和2是2。

4.1。代的初始解

我们得到初步解决方案如下。(1)起初,。可以安排在这个时间。根据上面的规则,我们调整为。活动3将在完成1,所以我们把它的bottom-left-rear点在原点的地方1。所以三个新的角落,,生产。更新,,,,,,,,。参见图3。(2)接下来,活动5将安排在位置2。我们把bottom-left-rear活动5点在原点的地方2。新角,,生产。根据规则,我们删除。更新,,。,,,,,,。参见图4。(3)检测到的角落和选择活动2。活动2计划后,三个新的角落,只有生产是合格的一个角落里。考虑到空间的一部分已经被活动2,我们应该重新测试之前的角落,当我们更新的可用空间。应该修改成。然后,,,,,,。参见图5。(4)4 0时刻,活动将在秩序。检测并把它放在。测试后,只可以是一个新的角落。同样,前面的角落的可用空间还应该测试和应该改变成。,,,,,,。参见图6。(5)0时,空间仍然可用,但是它是不够的任何剩余的活动。所以下次点此时,活动5完成。,,。订购后,是变成了。为了安排活动15,我们检测到。如果有任何角落的价值小于3时,我们应该改变成3和修改这个角落的可用空间。例如,应该改变成在活动前15。与此同时,这个角落的空间应该改变活动后15放。我们把活动15。,,,,。参见图7。(6)根据这一思路,我们得到一个初步的解决方案,,,,,,,,,,,,,,,,在这意味着活动应该开始时间吗,需要的空间可以表示为。根据初步的解决方案,整个项目的持续时间是25。位置1和位置2的状态图所示8。

4.2。优化初始解

在SA,活动的顺序对项目的持续时间有很大的影响。所以通过搜索附近和增加动态邻域的大小,我们设法使用SA和改善初始解。

我们改善的步骤如下。(1) ,。(2) ,。(3)如果,转到步骤(4);其他的输出电流和;完成这项计划。(4) 。(5)如果,,然后转到步骤(4);去下一个步骤。(6)选择从社区的。在我们的示例中,我们交换活动活动6和7的顺序。然后,我们得到另一个解决方案,,,,,,,,,,,,,,,。,。。如果,转到步骤(7);(8),去一步。当前是1,所以去步骤(7)。(7)比较和,如果,,;其他的(5)去一步。在这个例子中,,所以,。(8)生成一个数字随机,如果,,,,然后转到步骤(5)。

此改进后,在最优解减少从25 - 24。这是证明了方法的有效性。

5。结论

在这篇文章中,我们结合BLF和SA解决船块建筑空间调度问题。在安排活动的过程,我们用角落指导排序过程。然后,初步解决方案的排序可以改变SA。然而,如何提高搜索效率将是未来的研究,特别是当块的数量是非常大的。

利益冲突

作者宣称他们没有金融和个人关系与他人或组织不当会影响他们的工作,他们也宣称没有利益冲突有关的出版。

确认

这部分工作是支持由国家自然科学基金委批准号61202345,nsf在批准号ZR2012FM006, SDPW批准号IMZQWH010016。作者感谢2评论者和处理编辑器的细致阅读论文的和建设性的评论大大改善。