Spatial scheduling for large assembly blocks in shipbuilding
Abstract: This paper addresses the spatial scheduling problem (SPP) for large assembly blocks, which arises in a shipyard assembly shop. The spatial scheduling problem is to schedule a set of jobs, of which each requires its physical space in a restricted space. This problem is complicated because both the scheduling of assemblies with different due dates and earliest starting times and the spatial allocation of blocks with different sizes and loads must be considered simultaneously. This problem under consideration aims to the minimization of both the makespan and the load balance and includes various real-world constraints, which includes the possible directional rotation of blocks, the existence of symmetric blocks, and the assignment of some blocks to designated workplaces or work teams. The problem is formulated as a mixed integer programming (MIP) model and solved by a commercially available solver. A two-stage heuristic algorithm has been developed to use dispatching priority rules and a diagonal fill space allocation method, which is a modification of bottom-left-fill space allocation method. The comparison and computational results shows the proposed MIP model accommodates various constraints and the proposed heuristic algorithm solves the spatial scheduling problems effectively and efficiently.
Keywords: Large assembly block; Spatial scheduling; Load balancing; Makespan; Shipbuilding
1. Introduction
Shipbuilding is a complex production process characterized by heavy and large parts, various equipment, skilled professionals, prolonged lead time, and heterogeneous resource requirements. The shipbuilding process is divided into sub processes in the shipyard, including ship design, cutting and bending operations, block assembly, outfitting, painting, pre-erection and erection. The assembly blocks are called the minor assembly block, the sub assembly block, and the large assembly block according to their size and progresses in the course of assembly processes. This paper focuses on the spatial scheduling problem of large assembly blocks in assembly shops. Fig. 1 shows a snapshot of large assembly blocks in a shipyard assembly shop.
Recently, the researchers and practitioners at academia and shipbuilding industries recently got together at “Smart Production Technology Forum in Shipbuilding and Ocean Plant Industries” to recognize that there are various spatial scheduling problems in every aspect of shipbuilding due to the limited space, facilities, equipment, labor and time. The SPPs occur in various working areas such as cutting and blast shops, assembly shops, outfitting shops, pre-erection yard, and dry docks. The SPP at different areas has different requirements and constraints to characterize the unique SPPs. In addition, the depletion of energy resources on land put more emphasis on the ocean development. The shipbuilding industries face the transition of focus from the traditional shipbuilding to ocean plant manufacturing. Therefore, the diversity of assembly blocks, materials, facilities and operations in ship yards increases rapidly.
There are some solution providers such as Siemenstrade; and Dassult Systemstrade; to provide integrated software including product life management, enterprise resource planning system, simulation and etc. They indicated the needs of efficient algorithms to solve medium- to large-sized SPP problems in 20 min, so that the shop can quickly re-optimize the production plan upon the frequent and unexpected changes in shop floors with the ongoing operations on exiting blocks intact.
There are many different applications which require efficient scheduling algorithms with various constraints and characteristics (Kim and Moon, 2003, Kim et al., 2013, Nguyen and Yun, 2014 and Yan et al., 2014). However, the spatial scheduling problem which considers spatial layout and dynamic job scheduling has not been studied extensively. Until now, spatial scheduling has to be carried out by human schedulers only with their experiences and historical data. Even when human experts have much experience in spatial scheduling, it takes a long time and intensive effort to produce a satisfactory schedule, due to the complexity of considering blocksrsquo; geometric shapes, loads, required facilities, etc. In practice, spatial scheduling for more than a six-month period is beyond the human schedulersrsquo; capacity. Moreover, the space in the working areas tends to be the most critical resource in shipbuilding. Therefore, the effective management of spatial resources through automation of the spatial scheduling process is a critical issue in the improvement of productivity in shipbuilding plants.
A shipyard assembly shop is consisted of pinned workplaces, equipment, and overhang cranes. Due to the heavy weight of large assembly block, overhang cranes are used to access any areas over other objects without any hindrance in the assembly shop. The height of cranes can limit the height of blocks that can be assembled in the shop. The shop can be considered as a two-dimensional space. The blocks are placed on precisely pinned workplaces.
Once the block is allocated to a certain area in a workplace, it is desirable not to move the block again to different locations due to the size and weight of the large assembly blocks. Therefore, it is important to allocate the workspace to each block carefully, so that the workspace in an assembly shop can b
关于造船业大装配块的空间调度问题
摘要：本文满足了大型装配块的空间调度问题（SPP），它出现在船厂总装车间。空间调度问题是安排一组作业，其中每一个需要在有限的空间中的物理空间。这个问题是复杂的，因为不同的截止日期组件两者的调度和最早的开始时间和不同大小和载荷块的空间分配必须同时考虑。在考虑这个问题的目的是完工时间和负载平衡两者的最小化，并包括各种真实世界的限制，它包括的块的可能的定向旋转对称块的存在，并且一些块以指定的工作场所或工作的分配团队。该问题被配制成混合整数规划（MIP）模型和用市售求解器解决。两阶段的启发式算法已经发展到使用调度优先权规则和一个对角线填充空间分配的方法，它是左下填充空间分配方法的变形例。比较和计算结果表明了该MIP模型考虑了各种限制和提出的启发式算法有效地解决了空间调度问题。
关键词：大集会块;空间调度;负载均衡;完工时间;造船
1.简介
造船是一个复杂的生产工艺特点是重型和大型部件，各种设备，技术精湛的专业人员，延长交货时间和异构资源的需求。造船过程分为子过程中船厂，包括船舶设计，切割和折弯操作，块组件，舾装，涂装，前勃起及勃起。该组件块被根据它们的尺寸被称为次要组装块，子组件块和大组装块，并在装配过程的过程的进展。本文侧重于在装配车间大型装配块的空间调度问题。图。 1显示了大型装配块的造船厂总装车间的快照。
最近，在学术界和造船等行业的研究人员和从业人员最近在“在造船和海洋植物工业智能制造技术论坛”相约一起去认识到，有造船的每一个方面，由于空间有限，各种空间调度问题，设施，设备，劳力和时间。该SPP的发生在各个工作领域，如切割和爆炸的商店，装配车间，舾装店，架设前的院子里，和干船坞。在不同的地区，最高人民检察院有不同的要求和约束来表征独特的SPP。此外，土地能源资源的枯竭更加重视海洋的开发。造船行业面临的焦点从传统的造船海洋植物生产的过渡。因此，组装块，材料，设备和操作都必须在船厂的多样性迅速增加。
有一些解决方案供应商，如西门子trade;和Dassult系统trade;提供集成的软件，其中包括产品生命周期管理，企业资源计划系统，模拟等他们表示高效算法的需求，中期解决在20大型SPP问题分钟，使店铺能够迅速在店中地板上退出块完好的持续经营的频繁和意想不到的变化重新优化生产计划。
有需要的各种限制和特性有效的调度算法许多不同的应用（Kim和月亮，2003年，Kim等人，2013年，阮和云，2014年和严等人，2014年）。然而，它考虑空间布局和动态作业调度的空间调度问题还没有得到广泛的研究。到现在为止，空间调度必须由人的调度只与他们的经验和历史数据进行。即使当人类专家在空间调度多的经验，这需要很长的时间和紧张的努力，以产生令人满意的时间表，由于的考虑块#39;的几何形状，载荷所需的设施，等等。在实践中，空间调度更多的复杂性超过六个月超出了人类调度的能力。此外，在工作区域的空间往往是在造船的最重要的资源。因此，空间资源的通过空间调度过程的自动化的有效管理是生产率的造船植物的提高的关键问题。
船厂总装车间是由固定的工作场所，设备和悬起重机。由于大型装配块的重量重，悬起重机用于访问过其他对象的任何领域，而不在总装车间的任何障碍。起重机的高度可以限制可在店内组装块的高度。店铺可视为一个二维空间。该块被放置在固定精确的工作场所。
一旦块被分配到在一个工作场所的特定区域中，希望不要再次移动块到由于大组装块的尺寸和重量不同的位置。因此，分配的工作空间，重要的是每一个仔细方框，这样，在装配车间工作区可以以最有效的方式被利用。另外，由于每个块具有在船舶设计阶段被预先确定它的到期日，块组件的迟到可导致下面的操作严重延迟。因此，在用于大组装块的空间调度问题，装配的调度处理用于块和块的特定位置的工作场所的分配必须同时加以考虑。正如术语所暗示的，空间调度追求最佳的空间布局和动态时间表，也可以同时满足传统的调度约束。此外，也有不少这是对的车间严重关切，而这些复杂的SPP约束或要求。约束条件或要求本研究认为进行了说明：（1）块可以在任一方向，水平或垂直放。 （2）由于船舶绕中心线对称，存在对称块。需要这些对称块旁边被投入到彼此在相同的工作场所。 （3）要求某些块职场上的某些特殊区域放，因为该地区的工作团队有特殊设备或技能，实现一定的质量级别或完成必要的任务。 （4）通常，生产计划可以不按计划执行，因此，在生产计划频繁修改是必需的，以应付在店内的变化。在这些修改中，要求以产生一个新修改的生产计划，其中不移除或移动至预先存在的块在工作场所，完成正在进行的操作。 （5）如果有可能在任何时间，负载平衡过的工作团队，即，工作场所是为了保持所有任务分配工作团队公平统一理想的。
李某，李某和Choi（1996）研究了像考虑资源能力和截止日期，而且对象的动态空间布局不仅具有传统调度约束的空间调度。他们用由洛萨诺-Perez的（1983）开发的二维排列算法来确定在造船块的空间布局。苏梅，公园，财，和如（1999）开发了一个块组件调度系统的造船企业。他们提出了一种两阶段的方法，其包括调度相和空间布局相。苏梅，严，张和（2008）提出的最大接触面积的政策选择块更好地分配扩大了他们的珍贵艺术品（Koh等，1999）。赵涌，公园，公园和金（2001）提出了造船块喷漆工艺的空间调度系统，包括块调度，四排列算法和数据块分配算法。 Park等人。 （2002）扩展Cho等。 （2001）利用爆破和绘画两个连续的操作策略模拟。善，权，和刘某（2008年）提出的块组件的空间规划左下填充启发式算法，并建议通过差分进化算法安排块布局算法。刘，蔡，和嫣（2011）提出了一个仿真模型，这使多个优先规则来进行比较。郑江，陈（2012）提出了空间调度的数学规划模型，并使用了几种启发式空间调度策略（网格搜索和遗传算法）。张和陈（2012）提出了另一种数学规划模型，并提出了集聚算法。
这项研究提出了一种新的混合整数规划（MIP）制定考虑块旋转，对称的块，预先存在的模块，负载均衡和某些块的分配，以预先确定的工作空间。所提出的MIP模型由市售的软件实现，LINGOreg;和各种尺寸的问题进行了测试。计算结果表明，该MIP模型是极为困难的解决作为问题的大小增长。为了有效地解决这个问题，一个两阶段的启发式算法已被提出。
第2节描述空间调度问题，这是在该研究中使用的假设。第3节提出了一个混合整数规划。在第4节，一个两阶段的启发式算法已被提出，包括嵌段调度优先权规则和一个对角线填充空间分配启发式方法，它是从底部左填充空间分配方法改性。计算结果在第5节提供的结论在第6节给出。
2.问题描述
船舶设计决定如何对船舶分成许多小块。金属片切割，爆破，弯曲和焊接打造小块。这些小块被组装到更大的组装块。在这个过程中造船，所有块具有被从以前的操作阶段，并且由于这是下一个操作步骤所需日期决定了他们的最早开工时间。在每一个步骤中，块具有自己的各种尺寸和处理要求的形状。在组装，不需要块可以与他人身体重叠或悬垂的工作场所的边界。
空间调度问题可以被定义为一个问题，以确定一个给定的块的最优调度和工作场所的通过同时指定块#39;的工作场所的布局。正如顾名思义，空间调度追求动态优化空间布局时间表，也能满足传统的调度约束。动态空间布局的时间表可以是包括空间分配问题，时间分配问题，资源分配的问题。
空间调度的示例在图中给出。 2.有要被分配和安排在矩形工作场所4块。每块在不同的图案阴影。图。图2示出在给定的工作场所四个大块的6天的空间调度。块1和2是预先存在的或在第1天分配的块3和4的最早开始时间是天2和4，分别为。块1,2和3的处理时间是4,2和4天，分别。
空间时间表必须同时满足时间和空间的限制。有在空间调度许多目标，包括完工时间的最小化，最小迟到，空间和非空间资源的最大利用，等在本研究的目的是最大限度地减少完工时间和在工作空间平衡的工作量。
有在造船空间调度问题的许多制约因素，这取决于建造的船型，店铺的经营战略，组织限制等一些基本的约束给出如下： （1）所有块必须在工作场所给被分配用于装配流程，不得超越职场的边界; （2）任何块不能与其他块重叠; （3）所有的块有其自己的最早开始时间和截止日期; （4）对称块需要被放置侧由端在相同的工作区。图。图3示出块需要如何对称被分配; （5）一些块需要被放置在指定的工作区; （6）可以有规划期内前现有的块; （7）需要尽可能待平衡为工作场所的工作负荷。
除了上述的限制，以下假设。
（1）嵌段和工作场所的形状是矩形的。
（2）一旦块被放置在一个工作场所，它不能移动或者直到过程完成从它的位置移除。
（3）块可以在0°和90°角（参见图4）转动。
（4）的对称块具有相同的大小，以相同的角度旋转，并应放在侧由端在同一工作场所。
（5）非空间资源（如人员或设备）是足够的。
3.混合整数规划模型
一个MIP模型是制定并在本节给出。目标函数为最小化完工时间和偏差的每工作场所平均工作量的总和，考虑到块旋转，对称的块，预先存在的块，负载平衡和某些块的分配，以预先确定的工作区。
与长度LENW和宽度WIDW工作区被认为是二维的矩形空间。由于用于块中的矩形已经假定，一个块可以通过确定（X，Y）放置在工作区的坐标，其中0⩽点macr;x⩽LENW和0⩽yacute;⩽WIDW。因此，块上的工作场所的动态布局类似于二维装箱问题。除了块分配，需要在空间调度的问题，同时要考虑的最优调度。 Z轴被引入来描述时间维度。然后，空间调度问题成为一个三维装箱问题的各种目标和约束。
空间调度问题的判定变量是一个三维空间，其大小是LENW，WIDW和T中的x，y和z轴，其中T表示计划范围之内的所有的块（X，Y，Z）坐标。这个空间被示于图5。
在图6，两个块的空间调度到工作场所中示出，例如，参数P1和P2表示为块1和2的处理时间，分别。作为Z轴所示，块2块1完成后计划。
4.两阶段启发式算法
对于在第3节所述的MIP模型的计算实验已经使用市售的解算器，LINGOreg;进行。获得全局最优解是非常耗时的，考虑的变量和约束的数目。船舶是由超过8百大块，并采用MIP模型问题的规模超越了当今的计算能力。两阶段启发式算法已使用调度优先级规则和对角线补法提出。
4.1。第一阶段：负载均衡和测序
在空间调度问题，过去的研究认为，不同的优先权规则。 Lee等人。 （1996）使用的优先权规则块最小松弛时间。 Cho等。 （2001）和公园等。 （2002）所使用的最早到期日。 Shin等。 （2008）认为块的开始日期，结束日期和几何特征（长度，宽度和面积）三种调度优先权规则。刘腾（1999年）相比，9种不同的分派优先级规则，包括先来先服务，最短处理时间，至少松弛，最早的到期日，临界比例，大多数等待时间乘以吨位，最小的面积残留，和随机择业。 Zheng等。 （2012年）所使用的最长处理时间和最早开始时间一个调度规则。
两个优先规则在该研究中使用的所有的块分割成用于负载平衡基团和测序他们考虑到期日和最早开始时间。两个优先规则简化以负载平衡和序列块入其在所示的算法。 7.在这个阶段，算法的第一步是将组的基础上的紧迫性优先的块。的紧迫性优先通过减去最早开始时间和从到期日期为每个块的处理时间来计算。越小的紧迫性的优先级，越急块需要预定的床。然后，所有的块被分成组的水平的紧迫性优先的合理数量的适当数量。令g组的这酌情数。有基于块的紧迫性块克团。各组块的数目并不需要相同。
各组块被重新排序分成许多子组为工作场所，考虑块的工作量，如重量或焊接长度。在每个子组的块具有类似的紧迫性和工作负荷。然后，在每个子组这些块是有序中的最早开始时间的升序排列。这种排序将被用来阻止在序列分配。该分组对应的工作场所。
如果块我必须在工作场所Wmacr;macr;进行处理，目前分配给其他工作场所或亚比W，块i在块我的最早开始时间升序的顺序相同的位置换了块在其工作场所（或子组）。由于对称块必须位于同一工作场所，可以使用一个类似的交换方法。需要首先选择的一个对称的块被分配到不同的工作场所（或子组）。在这项研究中，我们选择的任意显示了早些时候的最早开工时间升序排列在其相应的工作场所（或子组）对称块之一。然后，所选择的块被交换以在最早开始时间的升序排列在其工作场所（或子组）的对称块的相同位置的块。
4.2。第2阶段：空间分配
一旦在工作场所（或子组）块在不同的紧迫感优先群体顺序排序，每个块可以一个一个地被分配到工作场所，并分配给在工作场所的特定位置。已经有启发式放置方法以前的研究。提出左下角（BL）放置方法贝克，科夫曼和Rivest（1980）和地方在底部最左边的位置矩形顺序。雅各布斯（1996）使用的是用混合遗传算法（参照图8）相结合的底左方法。 Liu和腾（1999）开发了一个扩展的左下启发式赋予优先向下方移动，这里的矩形仅滑动向左如果没有向下的运动是可能的。 Chazele（1983）提出的左下方填充（BLF）方法，该方法搜索最低左下点，在最低左下点的孔，然后将矩形依次在左下位置。如果矩形不重叠，该矩形放置和点列表被更新，以指示新的放置位置。如果矩形重叠时，选择在点列表中的下一个点，直到矩形可以放置而没有任何重叠。料斗和特顿（2000年）提出的BL和BLF方法之间的比较。他们的结论是BLF方法算法获得更好的分配模式比BL法Hopper的例题。
在造船空间分配是从二维装箱问题不同。块不规则多边形形状的空间布局，板块不断出现和消失，因为他们有自己的处理时间。这种频繁块放置和取出使得大型装配块的空间分配不太有效的方法BLF。
为了解决这些缺点，我们修改适合于对大型组装块空间调度的BLF方法。在工作场所中，由于块被放置并连续地除去，这是更有效的同时考虑放置块而不是仅左下
资料编号：[3180]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
