基于遗传算法的车间作业调度问题求解  

Solving Job-shop Scheduling Problem by Genetic Algorithm

作　　者：谢胜利[1] 董金祥[2] 黄强[2] 

机构地区：[1]温州师范学院计算机科学系,温州325003 [2]浙江大学人工智能研究所,杭州310027

出　　处：《计算机工程与应用》2002年第10期79-82,共4页Computer Engineering and Applications

基　　金：国家博士点基金项目(编号:2000033554)

摘　　要：文章提出了一个求解车间作业调度问题的完备的、强壮的遗传算法。在分析车间作业调度问题的数学模型的基础上,给出了:(1)采用分段结构的染色体编码思想;(2)生成可行调度的算法;(3)计算调度目标函数的算法;(4)三种遗传算子及其辅助算子———修正算子的设计。最后,通过仿真验证了算法的有效性和稳定性。A complete and robust genetic algorithm to solve Job-shop Scheduling Problem(JSP)is presented in this pa-per.Through analyzing the mathematical model of JSP,the authors put forward:(1)the coding idea of subsection chromo-some structure;(2)an algorithm of making the feasible scheduling;(3)an algorithm of computing the fitness function;(4)three genetic operator and the assist operator,modify operator.Digital computation results show the effectiveness of the proposed genetic algorithm.

关 键 词：遗传算法 车间作业调度问题 可行调度 遗传算子 NP问题 

分 类 号：O224[理学—运筹学与控制论]