贪婪算法在排课统中的应用研究.pdf

摘 要 科学、规范的教学管理是获得高水平教学质量的必要条件，课表安排则是教 学管理中最为关键的一环。制定一个灵活、高效、人性化的课程表，将对后继教 学活动的有序开展起到至关重要的作用。因此，对课表安排问题进行深入、细致 的研究，具有非常重要的现实意义。 近年来，随着高校招生人数的增加，各高校都面临着教学资源紧张的问题， 传统的手工排课方式工作繁琐、效率低下、易出错的缺点已经越来越突出，难以 适应现代化的教学管理需求。由于计算机具有运算速度快，处理能力强等特点， 很自然地进入到“排课”这一应用领域中。所谓计算机排课，就是把排课问题化 为计算机应用领域的有约束的时空组合优化问题进行求解。排课问题实际上是有 约束的多目标组合优化问题，它针对有限的教师、教学场地及教学时间等有限资 源，为达到最佳教学目标而进行的综合规划。即安排适当的教室、教师在恰当的 时间完成全部的教学任务。 本文分析了排课问题中的各种因素，并分析了遗传算法与贪婪算法的各自优 缺点，最终决定根据实际情况采用贪婪算法来解决排课问题这种资源有限、随机 性不是很强的编排问题。我们知道，贪婪算法在对问题求解时，总是做出在当前 看来是最好的选择。它不追求最优解，不要求回溯，只希望得到当前局部最优解。 虽然贪婪法不是对所有问题都能得到整体上的最优解，但对于范围十分广泛的求 最优解问题来说，是一种最直接、实用的算法设计技术，通过一系列局部最优选 择，即贪婪选择，最终可以得到整体最优解。 本文给出了基于贪婪算法的排课系统的详细设计方法，利用Delphi 可视化 编程语言加以实现，并对系统进行了多次测试，试验结果表明基于贪婪算法的排 课系统能够很好的从实际情况出发，有效地满足事先规定的各种排课限制条件， 达到了实际排课的需要，安排出一份高效、科学、合理的课表。 最后对本文所做的工作进行了总结，并对下一步的研究工作进行了展望。 关键词：贪婪算法、遗传算法、排课系统、Delphi I Abstract Scientific and standard teaching management is the necessary condition to obtain a high level of teaching. And, curriculum instruction management arrangement is the most critical link. Developing a flexible, efficient, personalized curriculum will play a crucial role to carry out follow-up teaching activities. Therefore, studying curriculum arrangements in-depth, detailedly has a very important realistic significance. In recent years, with the increase in university enrollment, all colleges and universities are facing the problem of the shortage of teaching resources. The shortcomings of cumbersome, inefficient, error-prone of the traditional manual arranging become more and more serious. The traditional manual arranging is hardly adapted to modern teaching management. Because of the fast speed, strong numerical skills of the computer, it has been applied to the areas of the curriculu