论文部分内容阅读
时间表问题(TTP)是一个应用广泛的、典型的组合优化和不确定性调度问题，并且已经被证明是NP完全问题，课程表的编排问题是TTP的一种典型实例。排课是教学管理中最基本、最重要、同时也是最复杂的管理工作之一，其实质就是为学校所设置的课程安排一组适当的教学时间与空间，从而使整个教学能够有计划有秩序地进行。动态规划是解决多阶段决策过程最优化问题的一种方法，它把比较复杂的问题划分为若干个阶段，通过逐段求解，最终求得全局最优解。 本文立足农林职业技术学院的实际情况，运用多阶段决策技术和动态规划技术对排课问题进行了分解，在分析现有软件系统算法的基础上，提出了一种新的多阶段自动排课算法MACA(Multistage Auto-arranging Course Algorithm)，并在此基础上建立了一个通用的排课系统，能有效的满足各种排课需求。 2005年1月，该系统在农林职业技术学院投入运行，至今为止，运行效果良好。2005年7月，系统通过软件著作权申请。2006年初，在该系统基础上申请通过了上海市教委项目“通用多学制型-排课考试费用计算链应用系统研究”。 本论文主要完成了以下工作： (1) 详细分析了课表编排问题，分析了课表编排过程中涉及的因素及各种约束条件； (2) 根据数据库系统设计理论，讨论了排课系统设计过程，包括数据库的概念模型设计、逻辑设计、物理设计及其实施； (3) 详细分析了排课中各种冲突，并对每种冲突采取不同的冲突稽核方法； (4) 设计了教师分配算法：教师等概率分配算法EPDA和首次适应分配算法FMDA，并分析比较了这两种方法的优缺点，最后提出了将这两种分配算法结合起来的优化算法——等概率首次适应分配算法EPFMDA； (5) 设计了场地最佳适应分配算法OADA，把场地按类型和大小进行分配，实现了资源的既充分又合理的利用； (6) 引入三维时间片划分方法，在此基础上分析了排课问题的可行解和近似最优解，并设计了时间片分配算法TSDA，采用了加权分组匹配思想。 (7) 立足农林职业技术学院的实际情况，实现了功能强大的排课系统，不仅可以实现手动排课和自动排课两大基本功能，还可以打印各种报表。