Abstract: Aiming at the spatial scheduling of ship blocks construction,a mathematical model was proposed to abstracting the block and work plates.On the basis of the configuration space theory,a single venue scheduling algorithm based on task priority and heuristic space layout rules(maximal remnant space utilization strategy,initial positioning strategy and BL rectangle strategy)was provided.An experiment compared with the traditional grid search method was made with different scale data and the result showed that relatively good performance and higher efficiency could be achieved in a short computational time.

Key words: spatial scheduling, configuration space, spatial layout, priority, scheduling algorithm

摘要： 针对船舶分段建造等空间问题,对分段和组立平台进行抽象,建立数学模型,在配置空间理论的基础上提出基于任务优先级和启发式空间布局规则(最大残余空间利用规则、初始配置规则和BL矩形规则)的单场地空间调度算法。在不同规模的实验数据下与传统的基于网格的近似全局搜索算法进行对比,结果表明所提算法在相对短的运算时间内能够获得更优的调度方案。

关键词: 空间调度, 配置空间, 空间布局, 优先级, 调度算法