并行混合遗传算法在车间调度问题的应用  

APPLYING PARALLEL HYBRID GENETIC ALGORITHM TO JOB SHOP SCHEDULING

作　　者：祁建程[1] 杨建刚[1] 

机构地区：[1]浙江大学计算机科学与技术学院,浙江杭州310027

出　　处：《计算机应用与软件》2011年第1期227-230,255,共5页Computer Applications and Software

基　　金：宁波市自然科学基金(2006A610011)

摘　　要：结合先后表编码和完全活动调度概念,设计了基于先后表的完全活动调度算法PLFA,该算法能将可行解与不可行解转化为完全活动调度。并将PLFA算法与遗传算法结合,提出了一种并行混合遗传算法,初始种群由PLFA G-T算法产生,其产生的解都是完全活动调度,采用LOX的交叉算子与基于PLFA G-T算法的变异算子,并使用主从模型的并行遗传算法模型。最后JSP基准实例验证了算法的有效性。In this paper,PLFA,an algorithm of full active scheduling based on preference list is designed,which is in conjunction of the preference list-based representation and the concept of full active schedule,and is able to transform feasible or infeasible solution into full active schedule.We present parallel hybrid genetic algorithm（PHGA） by integrating PLFA with genetic algorithm.Its initial population is generated by PLFA G-T algorithm,the solutions generated are all of full active schedules,the LOX crossover operator and PLFA G-T algorithm-based mutation operator are adopted,and the parallel genetic algorithm model in master-slave model is used.At last the validity of scheduling method is attested on standard benchmark instance of JSP.

关 键 词：车间调度 遗传算法 完全活动调度 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]