摘要
通过把调度方案表示成基于约束的图模型,在遗传算法求解过程中,采用了基于约束的二维数组编码方式,使算法的通用性得到提高。借助拓扑排序来判断个体的合法性及进行适应度的求解,在交叉和变异算子中引入关键工序的指导,缩小搜索空间从而提高了算法求解的效率和质量。最后给出相应实例,并与其它文献中的方法比较验证了本算法的可行性和有效性。
A graph model for Job_Shop scheduling is established by describing the scheduling scheme as a weighted directed graph.The validity of scheduling scheme is judged by topological queuing and the key job is extracted based on the key path. The improved genetic algorithm is subsequently presented for Job_Shop scheduling.The chromosome is coded with the constrained planar array and the evaluation function is computed with topological queuing.The operations of crossover and mutation are also directed by the key job.An example is given to demonstrate the proposed algorithm by comparing it with the other genetic algorithms presented in preterit articles.
出处
《计算机工程与应用》
CSCD
北大核心
2007年第10期35-37,40,共4页
Computer Engineering and Applications
基金
国家自然科学基金(the National Natural Science Foundation of China under Grant No.50575026)
辽宁省优秀青年科研人才培养资金项目(No.3040014) 。
关键词
车间作业调度
拓扑排序
关键工序
遗传算法
Job_Shop scheduling
topological queuing
key job
genetic algorithm
