船舶设计任务分配优化的案例分析

摘要 - 本文重点介绍船舶设计项目中复杂，难以控制的任务分配问题。 在分析设计任务中的内部和外部约束之后，一个数学模型被开发出来。 于是出现了结合循环关键路径和反向关键路径的方法。 本文采用基于工作时间和工作量的优化策略，以完成项目期间的所有任务

关键词—任务分配 船舶设计流程; 内部约束 外部约束; 优化

1.绪论

船舶设计对象的基本单位是船舶类型[1]，作为任务的基本单位的图形是物理对象，设计者是执行者。调度的核心是将每个任务按工作领域分配给每个设计人员以缩短设计周期。这个类型的问题在涉及多个领域的其它设计项目中同样存在，项目期限长和大量设计图纸，比如飞机，海上工程和摩天大楼等。在船舶设计期间，绘图任务不仅受到图纸之间的逻辑约束，还受到设计领域，持续时间，时间窗，设计师日历和设计人员负担的限制。船舶设计任务的特点之一是其为包括数千张图纸的一个庞大而复杂的内部约束关系网络。在调度期间[2]，前面提到的内部约束和设计者的工作量平衡和项目周期的外部约束都应该得到满足[3]。有许多侧重于作业车间调度问题的研究，其中大多集中在遗传算法（GA）的应用程序上。Ref.[4] 使用GA高度函数，来解决简单序列约束的多处理器调度的调度问题，达到最小完成时间。有许多侧重于作业车间调度问题的研究，其中大多集中在遗传算法（GA）的应用程序上。Ref.[4] 使用GA高度函数，来解决简单序列约束的多处理器调度的调度问题，达到最小完成时间。Ref.[5] 提出了一种使用GA的混合算法，通过使用定期性能指标，如加工厂的机器负载平衡问题[6]，最大限度地利用工厂空间来解决柔性作业车间调度问题中的单个对象。 所有这些问题都是基于单个机器的对象。 然而，船舶设计调度问题包括两个类型的主要对象，图纸和设计者，约束不仅存在于图纸之间，还存在于图纸和设计者之间。 作业车间调度算法无法解决这些问题。

2.图纸和约束

船舶设计院的组织模型主要是矩阵模型[7]。 船型是项目的基本单位。 在船舶设计项目中，输出是图纸，执行者是设计师。

绘图属性包括内在表现，开始条件，完成状态，领域，持续时间和截止日期。 内在表现包括绘图的名称，代码和船型，设计师属性由领域，工作时间，加班时间和工作负荷组成，代表设计师一天的工作时长。 此外，绘图任务应分配给相同领域的设计师。 绘图和设计者之间的这一场约束如图所示

启动条件是图纸之间的逻辑约束，限制了绘图在前一个图纸完成之前无法启动，或者前面的图纸处于必要状态，这是图纸间的特殊约束，我们称这种约束为部分结束-开始约束。 例如，直到General一半的任务完成，Hull的图纸才可以开始设计。 这是船舶设计任务分配中的约束和作业车间调度中的操作约束的主要区别。对绘画和设计师来说船舶设计中有五个主要领域：通用，船体，管道，舾装和电气。

3.调度模型

这个调度问题可以用一个数学模型来表示。

A. Notation

m The number of drawings;

n The number of designers;

d The index of work day;

i,k The index of drawing;

j The index of designer;

S. Li et al. bull; A Case of Ship Design Tasks Assignment and Optimization

T_i Start date of drawing i;

X_i The duration of drawing i in hours;

E_i End date of drawing i;

Z_i Field of drawing i;

D_i The deadline of drawing i;

Z_j Field of designer j;

W_ij Work hours of designer j spend in drawing i

in everyday exclude overtime hours;

O_ij Overtime hours of designer j spend in

drawing i in everyday;

W_ijd The work hours of designer j spend in

drawing i in day d include overtime hours;

D_o The deadline of project;

• Symbol of sequence constraints, T_k ε T_i means drawing k is the former task of drawing i, drawing i cannot start until drawing k complete or partly complete;

B. Expression of internal and external constraints

这限制了2次绘制与约束之间的开始时间。 如果绘图i和k之间存在约束，而绘图k在绘图任务i之前，如果约束是gik = 0的完成—开始类型，则绘图i的开始时间不早于k的完成时间; 如果约束是gikgt; 0的部分—完成—开始类型，则绘图i的开始时间不早于开始绘制k的 gik天。

式（3）是结束日期Ei，开始时间Ti，持续时间Xi，工作时间Wij和加班时间Oij之间的关系。

E D

这个约束表示结束日期Ei不应晚于绘图i的截止日期Di。

WT O

每个设计师在d天内的总工作时间不得超过标准工作时间和加班时间的总和。

Max E D

这是为了确保所有图纸在项目截止日期前完成。

Min Max E

这是用于寻求早期完成项目的第一个对象模型。

Min S W

这个表达式是平衡设计者的工作负担与工作时间差异的对象。

4.启发式算法

在船舶设计调度，图纸和设计人员中有两个实际的对象。 本文使用基于图纸持续时间和设计者工作量的双线程启发式分配算法。 第一个线程是基于图纸的持续时间，并找出需要首先分配哪个图纸，第二个线程是基于所有分配的图纸的结束时间和顺序，并找出绘图开始的时间。

A．循环关键路径

调度的主要目的是在考虑到图纸约束，工作时间和持续时间的情况下缩短整个项目的时间。 如果目的是使项目时长最小化，关键路径法（CPM）[8]是很好的方法，可以获得大量图纸中的主要关键路径，以确保主要关键路径上的图形按时完成，然后整个项目的完成时间将在一定程度上得到保证。然而，在实际的图纸分配中，存在大量的图纸，而设计人员资源往往有限，由于图纸在非关键路径中的等待效果，这将改变主要的关键路径。 对于这种问题，使用循环关键路径将第一个图形分配在关键路径上并结合关键路径相关理论，以获得有效的解决方案。 在所有未分配的图纸中寻求关键路径，并获得第一个绘制作业的关键路径。 因为删除第一个节点的剩余路径可能比将成为新的关键路径的其他路径短，这就是我们需要在每次分配后计算关键路径的原因。当一个绘图可以分配给多个设计者的情况下，对于各种关键路径，分配过程中的每个步骤将影响下一个步骤最终调度结果。在这种情况下，需要与不同的最终结果进行比较选择更好的分配方案。

B.反向关键路径

使用循环关键路径，我们得到最适合分配的图形。 但是我们仍不知道什么时候开始的最好时机。 为了实现这一点，我们使用反向关键路径来确定最佳的开始时间，即使用所选图形作为起始节点，在所有分配的图纸中计算反向关键路径，并确定分配的图纸是否可以优化以提前开始日期。

C. 使用加班来满足截止日期

有时，由于完成时间无法满足截止日期，无法分配选定的图形。 在这种情况下，将使用以下三个步骤：

bull;加班工作，执行此图的设计人员在本次绘图任务中应加班，日加班时间不得超过最长加班时间;

bull;如果问题仍然存在，请使用相同的方法缩短同一设计人员执行的上一个绘图的持续时间，并以相同的加班时间提前该图的开始时间;

bull;如果上述两个步骤不起作用，则从前两张图纸开始加班，以缩短设计时间，直到满足时间要求。 如果仍无法满足，则需要手动处理作业。

D.工作量平衡优化

最好的安排是所有设计人员的工作量相同。为了在一个领域保持设计师的相同分层，更好的方法是在保持区域工作负载平衡。 这是一个在复杂的设计环境中重新安排设计人员过载和空缺的困难问题。 为了实现这一目标，有效的方法是基于上述手动输出的算法调整。

5.实例

在本节中，给出了一个假设的例子来介绍算法如何在船舶设计项目中分配图纸。 示例的信息位于表I中。

我们使用代码Z，C，L分别代表通用区域，船体和管道，绘制代码作为图纸名称。 两个图之间的线表示约束关系，实线表示结束—开始约束，虚线表示部分—结束—开始约束，这意味着绘图可以在预绘图开始之后启动。 如D5，它可以从D2完成时和D3开始三天后启动。 节点上的标签表示区域工作时间和持续时间，例如（Z，10，11）在节点D1下表示节点D1 属于Z的区域，数字10是绘制的持续时间为10天，数字11 是D1的最后期限是项目启动后的第11天。图3的颜色表示不同的区域。 绿色是通用区域，灰色是船体区域，蓝色是管路区域。 这个例子中，红色虚线中有三个部分—完成—启动约束，它们是D3-D5，D4-D8和D31-D32。标准工作时间为每个工作日7.5小时，最长加班时间为2小时。使用启发式算法调度的结果且不考虑超时工作，如图4所示，在本次调度中，图纸D5和D9的分别晚于结束日期1天和2天。 在这种情况下，我们考虑加班工作，加班时间分别为0.68和0.83小时，小于最大加班时间，于是我们得到如图5所示的新调度安排。观察图5所示的调度。我们发现在绘制D28，D30和D31之前，有一些长的空缺（8天）。 那就是D30，D31被D28限制。 因此，如果D28可以提前完成，另外两个任务也会提前完成。 那么我们考虑到所有的D28图纸之前的最大加班时间。 最后，我们得到满足所有约束的调度如 6，所有分配给设计人员的图纸都按时完成。

6.总结

在本文中，我们将重点放在，涉及多个领域和大量设计图纸以及图纸与设计者之间约束的的其他设计项目也经常出现的，并将这些约束图纸分配给同一领域的设计人员的船舶设计图纸分配问题，部分—结束—开始约束，和限制人力资源的变量关键路径上。 我们提出了一个这个问题的数学公式，且分两阶段启发式算法。

第一个阶段是循环关键路径方法，用于选择哪个图是最佳分配图，第二个阶段是反向关键路径，用于确定对同一领域的设计师来说何时最早开始绘图。 此外，我们已经提出了优化基于加班的调度策略以缩短设计时间。 还给

全文共6484字，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[143850]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

您可能感兴趣的文章

• 船舶在浅水航道中航行时的岸壁效应数值研究外文翻译资料
• 基于三维面元法限制水域船体下蹲的数值研究外文翻译资料
• 关于甲板大开口船体梁极限抗扭强度的实验研究外文翻译资料
• 基于斯托克斯方程计算和系统识别 方法预估实船操纵模型参数外文翻译资料
• 水面舰艇5415在PMM演习中的基准CFD验 证数据-第二部分:平均相位的立体PIV流 场测量外文翻译资料
• 初步设计阶段船舶功率推进预测第二部分初步设计中有用的服务速度船舶功率推进数学模型外文翻译资料
• 对某高速船模湍流自由表面的数值与试验研究外文翻译资料
• 第三章水下搜救与恢复操作外文翻译资料
• 液化天然气供求关系的现状与展望:一个全球性展望外文翻译资料
• 基于CFD的高层钢结构建筑风效应数值评估外文翻译资料