Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (22): 226-231.

Previous Articles     Next Articles

Algorithm integrates multi-heuristic rules with particle swarm optimization for spatial resource constrained project scheduling

LIU Huanyu, YU Xiaoguang   

  1. College of Computer Science and Technology, Huaqiao University, Xiamen, Fujian 361021, China
  • Online:2016-11-15 Published:2016-12-02

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

刘焕玉,喻小光   

  1. 华侨大学 计算机科学与技术学院,福建 厦门 361021

Abstract: As a kind of spatial resource, assembly platform plays an important role in ship building. Spatial resource constrained 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 presented. 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.

Key words: spatial resource, weight, multi-heuristic, particle swarm optimization, time complexity, utilization rate of resource

摘要: 在船舶生产的现实背景上,对船舶生产过程中如何利用总装平台这一瓶颈资源建立空间资源受限项目调度的问题模型。利用空间资源和分段任务对象的特性,在最大面积优先、最长边优先、BL(Bottom-Left,一种解决布局问题的启发式规则)规则等启发式规则的基础上,提出多启发式规则融合粒子群算法的空间资源受限项目调度算法。将分段任务对象根据几何特性和拖延惩罚因子赋予不同的权值,确定其实际开始时间,再通过最长边优先和BL规则确定其空间位置。设计了具有初始解集并且能够自动识别的粒子群算法,加速其收敛以更快更优地获取分段任务对象序列。通过和其他几种主流的空间调度方法(分支界定和遗传算法)进行不同规模的实验对比,得出该算法在时间复杂度和平均资源利用率方面都有所提高。

关键词: 空间资源, 权值, 多启发式, 粒子群算法, 时间复杂度, 资源利用率