基于佳点集遗传算法求解Job-shop调度问题  

Solving Job-Shop Scheduling Problem Using Good Point Set Based Genetic Algorithm

作　　者：程军盛[1] 张铃[1] 

机构地区：[1]安徽大学人工智能研究所

出　　处：《计算机科学》2002年第4期67-68,共2页Computer Science

基　　金：973基金(G98030509)

摘　　要：1.介绍 Job-shop调度同题(JSSP)是极为困难的带约束组合优化问题,是NP难的.典型的Job-shop调度问题可描述为n个工件要在m台机器上加工,每个工件有其特定的加工工序,每道工序加工时间已知,并符合以下假设[1]:Job-shop is the representative of constrained combinatorial optimization problem and extremely hard to solve. By analyzing the crossover operation, that is choosing a point in the family whose ancestors have schema of high fitness, we utilize the principles of good point set in number theory and redesign the crossover operator. Then a new GA called good point set based GA is presented and applied to solve the benchmark problem of MT06 and MT10. The experimental result shows this new GA works well.

关 键 词：JOB-SHOP调度问题 组合优化问题 佳点集遗传算法 启发式算法 

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