基于资源受限的非线性约束多目标排课模型及算法  

Design of course arrangement model and algorithm of non-linear constrait and multi-object based on finite resource

作　　者：马绍惠[1] 徐立新[1] 郭祖华[1] 谌湘倩[1] 

机构地区：[1]河南机电高等专科学校计算机科学系,河南新乡453002

出　　处：《计算机工程与设计》2007年第3期520-523,共4页Computer Engineering and Design

基　　金：河南省自然科学基金项目(0411013300)

摘　　要：通过对排课资源和约束规则的分析与描述,提出并建立了一个基于资源受限的非线性约束多目标的排课模型。在该模型中,运用鸽子巢原理对问题是否有解加以判断,利用分治策略将问题分解,用主合取范式寻找所有可选方案,利用析取范式求得排课结果。在排课算法的设计中,综合应用了最小离差平方和法和间隔法。实验及应用证明该排课算法灵活高效,具有较强的冲突解决能力,并能在时空方面确保课表分布的均匀性。Accrording to the analysis and description of the course arrangement and constrait rules, a course arrangement model of nonlinear constraint and Multi-object is presented and set up. In this model, whether the problem has solution is judged by using pigeon＇s nest principle; the problem is analysed by using the dividing and conquering strategy, and all the alternative solution is found out by using principle conjunctive normal form, the result of course arrangement is got by using principal disjunctive normal form. During the design of arranging course algorithm, mini mizing the sum of the squared deviations and the interval method are applied integrately. The experiment and application prove that this arranging course algorithm is flexible and efficient, has great ability of dealing with conflics, and ensure the equality of the course distribution in space.

关 键 词：排课算法 鸽子巢原理 主合取范式 资源配置 非线性约束 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]