一种改进混合遗传算法解决车间作业调度问题的研究

An improved hybrid Genetic Algorithm for Job-shop Scheduling

车间作业排序理论是生产管理与组合优化领域的重要研究方向,由于其固有的计算复杂性(NP-Hard),一般无法利用经典方法求出最优解.针对作业车间调度问题,提出一种求解作业车间调度问题改进的遗传算法.该算法对交叉算子和变异算子进行改进,并将遗传算法和启发式算法相结合,建立一种混合算法框架,能有效避免局部最优.通过实例的计算和分析,取得了良好的调度效果,论证了算法的有效性和稳定性.

Job-shop Scheduling is an important subject in the fields of production management and combinato- rial optimization. It is usually hard to achieve the optimal solution with classical methods due to its high compu- tational complexity （NP-Hard）. A hybrid algorithm framework is proposed for general Job-shop Scheduling problem in this paper, in which Genetic Algorithm （GA） is integrated with a heoristie method. And it improves and designs crossover operation and mutation operation for avoiding the local optimum. By testing and analyzing some instances, it gets good computational results. Experiments show that the algorithm is efficient and stable.