英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
船舶建造中大型组装分段的空间调度方法
摘要：本文讨论了船厂装配车间中出现的大型组装分段的空间调度问题（SPP）。空间调度问题是调度管理一系列的工作问题，这些工作会在有限的范围内占据一定的物理空间。该问题较为复杂，因为需要同时考虑分段调度时相异的最早开工日期和完工日期，以及空间排列时不同的尺寸大小和重量。研究该问题的目的是缩短建造周期，并且在各种实际操作出现的限制条件中平衡工作量，这些限制条件包括可能出现的方向旋转、对称布置以及某些需要分配到特定工作场地或工人团队的分段。该问题将用混合整体规划（MIP）模型来进行分析，并利用商业软件来计算处理。本文还提出了一个两阶段启发式算法，包含优先级分配规则和由下-左-填充空间分配方法改进而来的对角填充空间分配方法。对比和计算后得到的结果可以表明，本文提出的混合整体规划模型能够符合各种限制条件，启发式算法能够有效且高效地解决空间调度问题。
关键词：大型组装分段；空间调度；工作量平衡；建造周期；船舶建造
1. 背景介绍
船舶建造是一个非常复杂的建造过程，因为它具有分段沉重且巨大、装备多样、技能要求高、建造周期长、资源需求复杂的特点。船舶建造的流程会在船厂内划分为一些二级流程，包括船体设计、切割和弯板工作、分段组装、舾装、涂装、预装配和装配。分段组装时根据分段的大小和组装流程中的顺序分为小型组装分段、二级组装分段和大型组装分段。本文研究的是装配车间内大型组装分段的空间调度问题。图1展示了船厂装配车间内组装大型分段时的情形。
最近，学术界的研究学者和船舶建造工业的从业者齐聚“船舶建造及海洋建筑工业智能制造技术论坛”，认识到在船舶建造中，由于空闲、设施、工具、人力和时间的限制，各个方面具有多种空间调度上的问题。空间调度问题会发生在各个工作区域，包括切割和喷丸除锈车间、装配车间、舾装车间、预装配场地和干船坞。不同区域的空间调度问题会有不同的需求和限制条件，它们使得每个空间调度问题都独一无二。此外，陆地上的能源枯竭显得海洋发展尤为重要。船舶建造工业正面临由传统船舶建造到海洋建筑工业的转型。因此，船厂内组装分段、材料、设施和操作的多样性正在快速增长。
西门子trade;和达索系统trade;等解决方案提供商提供的集成软件包含产品寿命管理、企业资源计划系统、模拟计算等功能。这些集成软件的效果表明，目前仍需要能够在20分钟内计算处理中到大规模的大型组装分段问题的高效算法，因为利用这样的算法，车间才能在多次出现计划之外的变化后快速重新优化生产规划，并保证完工分段的后续操作不受影响。
现在，已经有很多需要在多种限制条件和特点下进行高效调度的算法的实际应用（Kim和Moon，2003；Kim等，2013；Nguyen和Yun，2014；Yan等，2014）。然而，需要考虑空间布局和动态工作调度的空间调度问题并未得到广泛研究。直到现在，空间调度的工作不得不由人工依靠经验和历史数据来完成。由于需要考虑分段的几何形状、工作量、所需设备等等，即便是拥有大量的空间调度经验的专家，也需要很长的时间和极大的努力才能得到令人满意的调度结果。实际上，时间跨度达到6个月的空间调度工作已经超越了人类的能力。此外，工作区域的空间通常是船舶建造中最重要的资源。因此，在空间调度过程中利用自动化的操作来高效管理空间资源是优化船厂生产工作的关键问题。
船厂的装配车间是由固定的工作场地、设备和悬臂吊组成的。由于大型组装分段的重量较大，需要使用悬臂吊来无障碍地到达装配车间的任何角落，悬臂吊的高度则会限制车间内所能组装分段的最大高度。车间可以视为二维平面，所有分段放置在精确固定的工作场地中。
由于大型组装分段的尺寸和重量较大，一旦分段已经分配到工作场地内的确定位置，最好就不要再将其移动。因此，必须将空间认真分配给每个分段，这样才能最有效地利用装配车间内的空间。除此之外，由于每个分段在船体设计阶段就决定了其完工日期，在装配工作中出现的拖沓会造成后续工作严重拖延。所以对于大型组装分段的空间调度问题，必须同时考虑在装配过程中的分段调度和需要到特定工作区域的分段分配。正如这个名词，空间调度要做到最佳的空间分布和能同时满足传统的调度限制条件的动态调度。此外，在车间中还有很多需要重点关注的限制条件或要求，这些也使得空间调度问题变得复杂。本文会关注的限制条件和要求有这些：1. 分段可能以任意方向放置，包括横向和纵向；2. 由于船体沿中轴线对称，也就会有很多对称分段。这些分段需要在同一工作场地内相邻放置；3. 部分分段需要分配到工作场地内的特定位置，因为该位置可能有达到一定质量水平的特定设备，或完成任务的技术工人团队；4. 通常，生产计划并没有变化快，所以也需要能够在车间内多次根据变化来调整计划。这些调整需要能不移除或移动工作场所内已经存在的分段并完成后续的工作。5. 如果条件允许，不同工作团队的工作量，例如使用工作场地的时间，应达到平衡，以让不同团队的工作分配公平且统一。
Lee、Lee和Choi（1996）研究的空间调度问题不仅包含资源量和完工日期的传统调度约束，还包含物体的动态空间布局。他们使用了Lozano-Perez（1983）提出的二维排列算法，以确定船舶建造中的分段空间布局。Koh、Park、Choi和Joo（1999）提出了一个适合船舶建造公司的分段装配调度系统，以及一个包含调度阶段和空间布局阶段的两阶段步骤。Koh、Eom和Jang（2008）推广了他们先前的工作（Koh等，1999），提出了一个最大的接触面方法以选择分段的最佳分布。Cho、Chung、Park、Park和Kim（2001）提出了一个船舶建造中分段涂装流程的空间调度系统，包含分段调度、四排列算法和分段分配算法。Park等（2002）推广了Cho等（2001）的成果，在喷砂和涂装的连续的流程中使用了策略模拟。Shin、Kwon和Ryu（2008）提出了一个适用于分段装配的空间计划的下-左-填充启发式方法，并通过差分进化排列算法推荐了分段的放置算法。Liu、Chua和Wee（2011）提出了一个利用多重优先级来相互比较的仿真模型。Zheng、Jiang和Chen（2012）提出了一个空间调度的数学规划模型，利用了多种启发式空间调度策略（网格搜寻和遗传算法）。Zhang和Chen（2012）提出了另一个数学规划模型和聚集算法。
本文展示了一个全新的混合整体规划方法来考虑分段的旋转、对称分段、已存在分段、工作量平衡和需分配到预定区域的特定分段。该混合整体规划模型通过商业软件LINGOreg;加以应用，并测试了多种规模的空间调度问题。计算结果表明随着计算规模的增长，该模型的计算处理变得相当困难。为了高效地解决问题，又提出了一个两阶段启发式算法。
本文第2部分描述了空间调度问题的内容，和本文中使用的假定。第3部分展示了一个混合整体规划方法。第4部分提出了一个两阶段启发式算法，包括分段优先级分配规则和由下-左-填充空间分配方法改进而来的对角填充空间分配启发式方法。第5部分展示了计算结果。结论则在第6部分。
2. 问题描述
船舶设计决定了如何把船体分割为多个小片段，这些金属板通过切割、除锈、弯曲和焊接得到小型分段，小型分段再组装得到更大的分段。在这个船舶建造的流程中，每个分段都有最早的开工日期——上一个步骤完成的时间，和完工日期——下一个步骤要开始的时间。在每个步骤中，分段形状的大小和加工方式都各不相同。在组装时，任何分段都不能重叠于其他分段或超出工作场地的边界。
空间调度问题可定义为同时决定一组分段的最佳调度形式和确定分段工作场地的布局的问题。顾名思义，空间调度追求能满足传统调度限制条件的最佳动态空间布局调度方案。动态空间布局调度方案可以包括空间分布问题、时间分布问题和资源分布问题。
图2中展示了一个空间调度的实例。在这个矩形工作场地中需要分布和调度4个分段，每个分段用不同形式的阴影区分。图2展示了该工作场地中4个分段在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. 混合整形规划模型
本部分将介绍混合整形规划。该规划方法的目的是在考虑分段旋转、对称分段、已有分段、工作量平衡和部分需要分配到特定区域的分段这些内容的前提下，缩短建造周期和减小工作场地内平均工作量的偏差。
长度为LENW、宽度为WIDW的工作场地可以视为一个二维矩形平面。由于分段也可以视为矩形，所以可以通过指定坐标（X,Y）的方法来定位，其中0le;Xle;LENW，0le;Yle;WIDW。因此，场地内分段的动态布局类似于一个二维装箱问题。在空间调度问题中，除了分段定位，还要同时考虑最佳的调度方案，于是再引入Z轴来描述时间维度。这样，空间调度问题就变成了带有限制条件的多目标三维装箱问题。
空间调度问题的决策变量是每个分段的（X,Y,Z）坐标，该坐标位于X、Y、Z轴分别为LENW、WIDW和T的三维空间内，其中T代表计划方案的纵向内容。该三维空间如图5所描述。
图6展示了一个二分段空间调度方案作为例子。参数P1和P2分别代表分段1和2的加工时长。通过Z轴的描述，分段2是在分段1完成后开始加工的。
4. 两阶段启发式算法
本文第3部分中提到的混合整形规划模型通过商业软件LINGOreg;进行了计算实验。考虑到变量和限制条件数量众多，获取总体最优解需要消耗非常多时间。一艘船由超过800个大型分段组成，利用混合整形规划模型的计算量已经超过了当今的能力。于是，本文又提出了一个包含优先级分配规则和对角填充空间分配方法的两阶段启发式算法。
4.1 第1阶段：工作量平衡及排序
过去关于空间调度问题的研究考虑了多种优先级规则。Lee等（1996）使用优先级规则来缩短分段的闲置时间。Cho等（2001）和Park等（2002）利用了分段加工最早完工日期。Shin等（2008）使用了3种优先级分配规则，分别为分段的开工日期、完工日期和几何特征（长、宽和面积）。Liu和Teng（1999）比较了9种优先级分配规则，包括先来先服务、最短加工时间、最短闲置时间、最早完成时间、紧迫系数、最大等待时间与吨位乘积、最小空间浪费和随机选择工作。Zheng等（2012）使用了最长加工时间和最早开工日期来分配优先级。
本文使用了两个优先级规则来将分段分组以进行工作量平衡和排序，分别是分段加工的最早开工日期和完工日期。如图7所述，这两种优先级规则在工作量平衡和排序的算法上配合完美。该阶段算法的第一步是根据每个分段的紧急程度优先级来分组，紧急程度优先级是计算每个分段的完工日期减去最早开工日期和加工时间，紧急程度优先级越小，就越需要尽快完成加工工作。然后，根据紧急程度优先级，所有分段都能根据其合理的等级划分到数量合适的分组。用G表示此任意分组的数量，那么根据分段的紧急程度就可以分为G组分段。每个分组内的分段数量不必相等。
考虑到每一组内的分段的重量或焊接长度的工作量不尽相同，还要根据其工作场地分为数个二级分组，同一二级分组内的分段的紧急程度和工作量都接近。然后，再对每个二级分组内的分段根据其最早开工时间进行升序排列，利用该顺序再依次进行位置分布。二级分组与工作场地一一对应。
如分段I需要分配至工作场地W，但它目前位于另外的工作场地，或被分配到不对应工作场地W的二级分组，那么分段I就要与它所在工作场地（或二级分组）内按最早开工时间升序排列时靠后的分段交换位置。由于对称的分段必须分配至同一工作场地，也可以使用类似的交换方式，不过要先判断并选择分配到错误工作场地（或二级分组）的分段。在本文中，我们选择对称分段中按最早开工时间升序排列时靠前的分段，然后将这个分段与另一个分段所在工作场地（或二级分组）内按最早开工时间升序排列时位置相同分段交换位置。
4.2 第2阶段：空间分配
当同一工作场地（或二级分组）内的分段按照不同的紧急程度优先级排序之后，所有分段都可以依次分配到工作场地中，以及工作场地内的特定位置。先前已有人研究过空间分配启发式方法。Baker、Coffman和Rivest（1980）提出了一个下-左（BL）空间分配方法，是把矩形形状按照下方-左侧的顺序依次填充。Jakobs（1996）使用了结合了混合遗传算法的下-左方法（如图8）。Liu和Teng（1999）推广了一个拓展版下-左空间分配启发式方法——向下的移动具有更高优先级，这样每个矩形只需在无法向下移动时向左移动。Chazele（1983）提出了一个下-左-填充（BLF）空间分配方法——先搜寻并记录最靠近下、左侧的点，再以这个次序依次填充矩形。如果矩形不相互重叠，则矩形可以分配在该位置并更新点的序列，指向下一个位置；如果矩形相互重叠了，就将矩形移动到下
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[237396]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
