龙源期刊网 http://www.qikan.com.cn
遗传算法解决车间调度问题的研究
作者：王淑平
来源：《商情》2011年第24期
[摘要]：遗传算法近年来在优化领域，特别是生产调度问题中得到了广泛的应用，取得了很好的效果。它操作简单，全局搜索能力很强，这是其他优化方法所不能比拟的。本文综述了遗传算法及基于遗传算法的混合算法在作业车间调度问题中的应用。 [关键词]：遗传算法 车间调度 混合算法 优化问题
1 车间调度问题简介
作业车间调度问题（Job-shop Scheduling Problem，JSSP）是一个典型的NP难问题，同时也是最有名的复杂组合优化问题之一。车间调度问题可描述为用m台机床加工n个零件，已知每个零件各个工序的加工时间以及在各个机床上的加工顺序，调度的任务是确定每个机床上工序的加工顺序及每道工序的开始时间，并且要满足一定的约束条件，同时使性能指标得到优化。这里的性能指标可以是使所有工序的完工时间最小，也可以是其他的指标，如加工过程中成本最低等等。
近年来，随着新的相关学科的不断建立和发展及优化技术的完善，在车间调度问题上出现了许多研究方法，比如启发式算法、模拟退火法、神经网络法、禁忌搜索法等等。遗传算法经过近四十年的发展在优化领域取得了丰硕的成果，特别是近年来受到了广泛的关注。 2 遗传算法介绍
遗传算法(Genetic Algorithms)简称为GA，是由John Holland及其合作者在20世纪70年代所提出的，实质是通过对染色体(问题解)群体重复地进行“选择、交叉、变异”三个基本遗传操作，不断地产生出比父代更适应环境的新一代染色体群体，直到满足要求条件为止。 遗传算法的特点：①自组织、自适应和自学习性；②本质上并行性；③遗传算法不需求导或其他辅助知识，而只需影响搜索方向的目标函数和相应适应度函数；④它强调概率规则，而非确定的转换规则；⑤它可以更直接应用；⑥它对给定问题可以产生许多的潜在解，最终选择可以由使用者确定。
遗传算法原理和操作简单，全局搜索能力强，但是它易早熟收敛，在解决调度问题时还有一个不足之处——不能完全保证找到最优解。 3 作业调度中的遗传算法
遗传算法解决车间调度问题的研究
