【摘要】 车间作业排序理论是生产管理与组合优化领域的重要研究方向 ,由于其固有的计算复杂性( NP-Hard) ,一般无法利用经典方法求出最优解。本文针对一般作业排序问题 ,将遗传算法与启发式方法相结合 ,建立了一种混合算法框架 ,利用遗传算法改进启发式方法的求解性能 ,同时利用启发式方法引导遗传搜索过程 ,以提高其搜索效率。通过对完工时间与平均延误时间等不同优化目标的计算分析与比较表明 ,该方法对不同类型的排序问题均具有相当满意的求解效果更多还原

【Abstract】 Job shop scheduling is an important subject in the fields of production management and combinatorial optimization. It is usually hard to achieve the optimal solution with classical methods due to its high computational 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 various heuristic methods. With this algorithm framework, the heuristics can be greatly improved by GA, while the searching efficiency of GA can be increased as well under the guidance of the heuristic rules. Finally, comprehensive numerical experiments have been made for optimizing makespan and mean tardiness, which show that satisfied solutions can be achieved for various scheduling problems with the hybrid algorithm.更多还原