论文总字数：22495字

目 录

1、绪论 1

1.1 排课问题概述及研究意义 1

1.2 排课问题的国内外研究背景 1

2、排课问题建模 2

2.1 排课问题的目标分析 2

2.11 排课问题的因素 2

2.12 排课问题的约束条件 2

2.13 排课问题的求解目标 3

2.2 排课问题的数学模型 3

2.22 排课问题的约束条件 4

2.23 排课问题的求解数学模型 5

3、排课问题的算法理论 5

3.1 遗传算法简介 5

3.11 遗传算法的研究背景 5

3.12 遗传算法的基本思想和步骤 6

4、基于遗传算法的排课方案 7

4.1 基因编码规则 7

4.2 初始化种群 8

4.3 适应度函数 8

4.4 选择操作 9

4.5 交叉操作 10

4.6 变异操作 10

4.7 课表解码 10

4.8 排课问题的实现与验证 10

4.81 遗传参数的确定 10

4.82 排课规模 11

4.83 实例验证结果 11

5、总结 15

致谢 16

参考文献 17

附录 18

基于遗传算法的排课模型研究

包丽君

，China

Abstract: Due to the growing scale of colleges and universities, the difficulty of arranging classes is greatly increased. Nowadays, the problem of arranging classes has become a prerequisite for efficient management of daily teaching affairs in colleges and universities. Only when an effective curriculum is determined, all departments of the university can carry out teaching activities in an orderly manner, but at the same time, it also requires a lot of manpower and material resources to allocate resources, that is, how to effectively solve courses, classrooms and Pairing relationships between classrooms. At this time manual scheduling not only consumes time and energy, but also difficult to get high-quality results, so the use of computers to intelligently arrange classes has become the primary choice of colleges and universities. Actually, computer intelligence algorithms first originated in the 1950s, and various solutions have emerged.

The genetic algorithm applied in this paper is a random search method based on the concept of biological evolution of Darwin's survival of the fittest, which is characterized by high degree of concurrent behavior. This article will study the correspondence between the genetic algorithm and the queuing problem factors, apply the principle to establish a scheduling model, and use examples to verify, mainly discussed the following aspects:

(1) A brief introduction to the research background and significance of the arranging problem, and specifically listed the factors involved in the problem, the constraints to be satisfied and the solution objectives;

(2) Using 0-1 integer programming and quantifying constraints to establish a multi-objective combinatorial optimization mathematical model for class scheduling problems;

(3) Briefly introduce the basic idea and basic operation of genetic algorithm, and carry out the specific operation analysis of the mathematical model in (2) corresponding to the genetic algorithm, and establish a solution model that is suitable for the problem.

Keywords: Timetable problem, multi-constraint combinatorial optimization, genetic algorithm

1、绪论

1.1 排课问题概述及研究意义

高校排课问题本质是多元时间的NP资源分配问题，换而言之就是需要根据教学计划和教学资源的需求将全校的课程进行快速优化配置，以达到合理执行全校的教学安排工作的目的。

高校课程表是整个学校开展教学活动，提高教学质量的重要环节之一，但由于高校课程和教学资源众多，并错杂复杂，于是随着高校扩招，学生数量急剧增加，同时教学资源等各种因素也随之变化，高校排课问题的困难程度就与日俱增，此时再使用人工排课不仅消耗时间和精力，而且难以得到优质的结果，于是利用计算机来智能排课就成了高校的首要选择，从而构建高效的课程表，使高校的各项工作得以有效地进行，从而推动教学管理工作。

1.2 排课问题的国内外研究背景

计算机智能算法最早起源于20世纪50年代，从这以后，有关课程表问题的数学模型以及是否存在可行解成为了科学家们理论研究和探索的重点对象，但始终未得到优质的结论。

Gotlied^[1]在1993年首次建立了排课问题的数学模型，于是排课问题进入数学问题的范畴，之后Seven^[2]在1976年运用理论推导证实了高校排课问题可以转化为NP完全问题，简而言之，就是源于实际问题边界易对它产生影响，计算机难以求出最优解，这一次理论依据真正确定了该问题在学术界的地位。此后Ferland^[3]等人和吴金荣^[4]将排课问题转化为仅适用于小规模排课的整数规划问题。而何永太和胡顺仁^[4]等人则试图采用基于NP完全问题的图染色理论，但对这些因素处理的方法严重受制于该问题的具体约束条件。

课表问题始终是国内外学者研究的焦点，20世纪90年代起，加拿大Montreal大学的Jacques A.Ferland^[17]等人开始将排课问题转化两个字问题求解，即时间表和分组； Kirkpatrick^[17]等人则在1983年首次提出了模拟退火的求解方法^[21][22]，此后一大批学者随之效仿，不断引进了新的求解方式。

国内学者对于排课问题的求解起源于80年代，人们开始运用人工智能构建专家系统（或决策支持系统）。经典的方法有基于时间位图迭加匹配算法^[20]、基于优先级的自动排课算法^[19]以及基于专家系统求解算法^[18][23]等，在原来的基础上逐渐从二维分配问题转化为四维搜索问题，再加之构建特殊专家系统，使排课逻辑和结果越来越趋于实际情况。

但是当前的排课问题的解决方法仍存在欠缺，一方面国内排课软件大多都是人工与计算机排课相辅相成，自动排课系统稀缺，并没有独立存在；另一方面自动排课系统在排课过程中会产生无法合理安排的冲突，使得需要后期的人工调整，很难应用于实际。

排课问题实质是多约束条件的NP问题，随着人工智能的广泛应用，以进化论为基础的遗传算法，由于具有高度并行和鲁棒性能来解决组合优化问题，已经受到各领域的广泛应用和推广。

2、排课问题建模

2.1 排课问题的目标分析

2.11 排课问题的因素

我们从人工排课的整个过程中可以明显看出，排课问题涉及诸多因素^[5]，乃至牵动全校，需要全校各部门的紧密配合。排课最终得到的应该是最合理的解决方案，通过对既定的教学任务单元在满足各种需求的条件下，在时间和空间的二维表上进行排列组合，以达到全校各部门的正常运作和教学任务的正常完成。

首先从人工排课的角度考虑排课过程中可能会存在的冲突，由此可以将排课问题的因素^[6]分为以下几种：

剩余内容已隐藏，请支付后下载全文，论文总字数：22495字