基于双线性链表编码的并行机大规模调度遗传算法  

Genetic algorithm for large-scale scheduling of parallel machines based on double linear-linked-list encoding

作　　者：赵振[1] 刘钢[2] 严隽薇[1] 刘敏[1] 

机构地区：[1]同济大学电子与信息工程学院,上海201804 [2]上海宝钢设备检修有限公司,上海201900

出　　处：《计算机集成制造系统》2011年第2期301-309,共9页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(61073090;61034004);上海市科学技术委员会科研计划资助项目(09DZ1122302);上海市重点学科建设资助项目(B004);广东省教育部产学研结合资助项目(2009GJE00026;2009B090300429)~~

摘　　要：面向并行机大规模调度问题,提出了一种以工件聚类作为初始染色体种群构成基础的遗传算法。算法首先采用改进的模糊C-均值聚类算法,按影响调度的工件重要特性指标,将工件进行聚类;然后采用基于双线性链表结构的编码方式,表示工件聚类在并行机上的生产次序及任务数量,并据此设计了相应的交叉和变异算子;最后进行了实验分析及实例应用,该算法可以在合理的计算时间内获得满意的优化质量。A new genetic algorithm was presented for large-scale scheduling problems,in which the chromosomes were initiated and founded by the jobs＇ clusters.Firstly,an advanced fuzzy C-means clustering algorithm was used to divide the jobs into different clusters according to important characteristics which affected the scheduling.Then,a encoding method based on double linear-linked-list was proposed to represent the processing sequences as well as the tasks＇ numbers of the jobs＇ clustering on the parallel machines.Corresponding crossover,mutation operators were also designed.Finally,this algorithm was testified by analysis and application.Results demonstrated that it could acquire a satisfactory optimization quality within a reasonable time period.

关 键 词：调度 并行机 遗传算法 工件聚类 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]