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

作     者：刘焕玉 喻小光 LIU Huanyu;YU Xiaoguang

作者机构：华侨大学计算机科学与技术学院福建厦门361021 

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：2016年第52卷第22期

页      面：226-231页

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：泉州市科研基金资助项目(No.2013Z29 No.2012Z89) 

主　　题：空间资源 权值 多启发式 粒子群算法 时间复杂度 资源利用率 

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