基于回答集程序的排课系统设计与实现

Timetabling System Design and Implementation Using Answer Set Programming

排课问题是典型的组合优化和NP完全问题。一个好的排课系统既需要能高效地求解排课问题,也需要能提供灵活的定义各种用户约束的方式,但现有的排课系统通常不能同时兼顾这两点。通过实现一个基于回答集程序的排课系统,较好地解决了这一问题。系统的前端接受用户的各种约束条件,并将其转换为回答集程序,后端调用回答集求解器实现排课问题的求解。实验表明,这种实现方式能适应排课条件的变化,具有灵活和可扩展的特点,并在可接受的时间内能排出教师满意度较高的课表。

Timetabling problem is a typical combinatorial optimization problem as well as a NP-complete problem.A good timetabling system needs not only the efficiency in timetabling solving but also the flexibility in definning user constraints.However,the systems at present usually can＇t deal with these two points at the same time.In this paper,realize a better timetabling system based on answer set programming.The system＇s Front-End receives various constraints before transforming them into answer set program.The Back-End solves timetabling problem through answer set solver.The experimental results show us that it can arrange a satisfied timetable in an acceptable time because of its flexibility and scalability.