Abstract: In order to solve the problem of spatial scheduling of irregular blocks in stacking field after they were built, a dynamic stacking algorithm based on grid searching was proposed. An improved Particle Swarm Optimization (PSO) algorithm was used to determine the optimal processing sequence, and the locations of blocks were determined in spatial layout decoding by a dynamic location strategy based on grid technology. In the decoding process, bitmap was used to describe the information of yard and polygon and find the best location for every block. The space utilization and the quantity of blocks that need moving were used as the evaluation function, which fully considered the dynamic nature and the correlation between time and space in a stacking problem. Every particle in population was a stacking sequence, and the optimal solution could be found in the process of evolution by the improved PSO. Finally, the results of an actual data of a shipyard and the comparative analysis with other stacking algorithms show that the proposed algorithm is the best when comprehensively considering the space utilization, the number of movements of other blocks and efficiency of the algorithm.

Key words: dynamic stacking, grid search, irregular blocking, Particle Swarm Optimization (PSO), bitmap

摘要： 针对船体分段建造后在堆场中的空间调度问题，提出基于网格搜索的分段动态空间调度算法。首先，利用改进的粒子群算法产生多个可行的分段堆放序列;然后，采用基于网格搜索的定位策略对堆放序列进行空间布局解码。在解码过程中，运用位图对场地及投影多边形进行信息描述，快速寻找多边形的最佳定位位置。考虑分段堆放问题的动态性的时空关联性，同时以场地平均利用率和需要挪动的场地内分段总数的综合加权作为评价函数，利用改进的粒子群算法对方案进行择优，得到近似最优解，实现了堆放方案的全局优化。通过对船厂实际生产数据的实证分析以及堆放算法间的对比分析，结果证明，所提算法在综合评价场地利用率、移动分段数和运算效率的条件下是最优的。

关键词: 动态堆放, 网格搜索, 不规则分段, 粒子群算法, 位图