王津剑，杜吉旺，范秀敏，2+，何其昌，2

（1.上海交通大学 机械与动力工程学院，上海 200240；2.上海市网络化制造与企业信息化重点实验室，上海 200230）

0 引言

船舶建造作为传统产业，随着精益生产、成组技术等新技术在该领域的应用，催生了新的现代船舶建造模式，在此模式下，船舶以分段为单元制定生产计划并进行生产［1］。分段是由船体的零件、部件组成的局部结构，由于分段建造占用大量空间区域和设施资源，对分段生产进行安排，在满足调度约束的条件下获得最优的动态空间布局即为分段空间调度问题［2］。

船舶分段空间调度是NP完全问题，一般采用启发式调度算法求解。Lee等［2-3］最早对船舶分段空间调度问题进行了研究，提出最大剩余空间利用规则、初始定位规则、边规则和混合规则等启发式调度规则，用时空坐标系对分段进行三维空间调度，基于此开发了韩国大宇造船厂的DAS-CURVE软件。此后，国内外对空间调度算法进行了深入研究并进行了改进。Lee［4］研究了空间调度专家系统的搜索空间，证明了对于投影形状是多边形的分段，以顶（角）点为搜索空间的启发式算法在空间调度上是有效的，但是并没有考虑分段摆放方向。Liu等［5］针对矩形分段，将分段边界延长线的交点增加到启发式算法的搜索空间，但是随着分段的增加，搜索空间的容量急剧增加。Varghese等［6］采用类似于“二维装箱”的算法，采用最下最左（Button Left，BL）的启发式定位策略，计算矩形分段的布局。Shin等［7］先使用矩形计算分段的初步位置，再换上实际形状，调整分段的局部位置，使分段布局紧凑。……