【作者】 曾丽；

【导师】 陈雪波； 于政军；

【作者基本信息】 辽宁科技大学 ， 控制工程， 2007， 硕士

【摘要】 时间表问题是运筹学领域和系统工程领域中的典型组合优化问题,是由于事件对时间和空间的资源争夺而产生的,属于NP完全类问题。大学课程表问题,作为时间表问题的一个重要组成部分,是时间表问题的研究重点,研究该类问题的解决方法和技巧,是极具理论和实际意义的。群集智能,则由于其在解决分散的、强非线性的、多变量问题中的独特优势,而得到众多研究者的重视,成为一个新的研究方向和热门课题。然而尽管群集智能在很多方面得到了应用,但在大学课程表问题这一领域,却未能得到比较好的应用。因为上述原因,本文研究了如何基于群集智能来解决大学课程表问题,其主要贡献有:(1)介绍了自然界中鸟群的一些栖落习性和大学课程表的一般解决步骤,然后通过模拟鸟群的栖落习性,建立了大学课程表问题的鸟群栖落模型;(2)讨论了学校课程集、学校教室集等集合的基本属性,给出了班级课程对信息素、班级教室信息素的计算公式,并分析了它们的基本特点;(3)根据鸟群栖落模型及班级课程对信息素、班级教室信息素的特点,得到了一种新的解决大学课程表问题的鸟群栖落算法。文中详细介绍了该算法的基本原理和基本步骤,并给出了流程图;(4)根据鸟群栖落算法,设计了一个自动编排大学课程表的软件系统。文中介绍了该系统软件平台的选择策略、输入输出界面的设计、程序编写的基本技巧等,并给出了该系统的测试结果。最后的测试结果表明,鸟群栖落算法是可行且有效的,大学课程表自动编排系统软件平台的选择及输入输出界面的设计,是合适且方便的。更多还原

【Abstract】 Timetable problem is a typical problem of combined optimization in the fields of operational research and systems engineering, which belongs to NP problem. The problem usully occurs when the events dispute their space-time resources each other. University curriculum schedule problem is one of important component of the timetable problem. It becomes a highlight of timetable problems to which a lot of reseacheres have paid more attentions. Recently, more and more scholars have been focusing on swarm intelligence, because of its properties in the field of optimization. Althogh a variety of applications by swarm intelligence have been achived, the university curriculum schedule problem has not been extended, so it is of interest to study how to solve the university curriculum schedule problem based on swarm intelligence.For the above reason, this thesis presents a modeling, algorthim and design of a software system for the university curriculum schedule problem, by using swarm intelligence. The main contributions of this thesis are listed following:(1) The occupancy habits of a group of birds and the general steps for planning a university curriculum schedule are introduced firstly. Then, a bird occupancy model for university curriculum schedule planning is proposed with simulation of the occupancy habits of birds.(2) Some properties of certain sets, such as university subject set and university classroom set, are discussed. The formulas for class-subject pheromore and class-classroom pheromore are given and their basic properties are derived.(3) According to the model and the conditions of university timetable problems and the properties of class-subject pheromore and class-classroom pheromore, an algorithm for automatic planning of university timetable is presented, which can automatically plan timetables and consider the problem of deadlocks by coordination when the plan is in progress. The basic principle and general steps of the algorithm are introduced with its flow chart.(4) In order to implement the proposed algorithm, a software system is designed for university curriculum schedule problem, and its selecting strategy of software platform and the design of input-output interface are also introduced. Furthermore, the algorithm is programmed.Finally, the testing result shows that the proposed algorithm for automatic planning of university timetable is feasible and effective. The design of the software system is of convenience.更多还原