论文部分内容阅读
作业调度问题是一个被广泛认可的在实践中所遇到的最难解决的NP完全问题之一,对作业调度问题解法的研究不仅对于制造业有特殊的意义,而且对所有NP完全问题的解法都有普遍的借鉴意义。
全文共分为四章。第一章概述了当前制造业的现状,引出车间作业调度问题在计算机集成制造系统中的重要地位以及研究它的重要性。
第二章简述了什么是计算机算法理论中的NP完全问题,它既是难于解决的困难问题,又是我们要面对不能回避的问题,只能想办法解决它。如果采用传统的算法在目前的计算机系统中运行所花费的时间是指数级的,是不现实的,因此在改变不了硬件的情况下,只能通过寻求一种新的算法来解决此类问题。
第三章介绍了现代优化算法之一的遗传算法,它是借鉴生物界自然选择和进化机制发展起来的高度并行性、随机、自适应搜索算法。文章通过对遗传算法的思想、操作原理的分析得出遗传算法不同于传统搜索方法的突出特点是:全局性、并行性。即在全局范围内进行的快速搜索,满足终止条件后停止,得到一个最终解。虽然这个解并不是精确解,也不一定是最优解,但是却在有限的时间内,在全局范围内做了大量的、快速的、随机性的搜索,这个结果对实际问题的解决还是有意义的。
第四章以作业调度问题为例,阐述了用遗传算法求解的过程。包括如何建立作业调度问题的数学模型、如何确定适应度函数、如何用POX交叉算子完成交叉操作、如何完成变异操作等。最后,通过VisualC++环境,实现了仿真程序,并通过对比,说明了用遗传算法求解作业调度问题的有效性。
在总结中指出论文中的不足及今后努力的方向。
通过本课题的研究,使我对计算机算法理论有了新的、深刻的理解,特别是对遗传算法的思想有了本质的认识,感谢李学武教授对我的指导和支持。