多启发式规则融合粒子群算法的受限项目调度

摘要

在船舶生产的现实背景上，对船舶生产过程中如何利用总装平台这一瓶颈资源建立空间资源受限项目调度的问题模型。利用空间资源和分段任务对象的特性，在最大面积优先、最长边优先、BL（Bottom-Left，一种解决布局问题的启发式规则）规则等启发式规则的基础上，提出多启发式规则融合粒子群算法的空间资源受限项目调度算法。将分段任务对象根据几何特性和拖延惩罚因子赋予不同的权值，确定其实际开始时间，再通过最长边优先和BL规则确定其空间位置。设计了具有初始解集并且能够自动识别的粒子群算法，加速其收敛以更快更优地获取分段任务对象序列。通过和其他几种主流的空间调度方法（分支界定和遗传算法）进行不同规模的实验对比，得出该算法在时间复杂度和平均资源利用率方面都有所提高。%As a kind of spatial resource, assembly platform plays an important role in ship building. Spatial resource con-strained project scheduling is proposed for optimizing utilization rate of assembly platform. On the basis of the spatial resource and constraints between tasks, algorithm integrates multi-heuristic rules with particle swarm optimization is pre-sented. In this paper, the start time of blocks are according to their different weight which is decided by their geometrical features and delays, and the position of blocks are according to Bottom-Left and Longest edge rules. In order to achieve the optimal sequence of tasks, a novel adaptive particle swarm optimizer is designed via optimizing initial particles and self-check. An experiment compared with the traditional algorithms is provided to illustrate the high effectiveness of the proposed approach in both time complexity and utilization rate of resource.