1、北京化工大学本科毕业设计（论文）翻译毕业设计（论文）翻译Using Tabu Search for Solving a High School Timetabling Problem用禁忌算法解决高中排课问题Khang Nguyen Tan Tran Minh1, Nguyen Dang Thi Thanh1, Khon Trieu Trang1, and Nuong Tran Thi Hue2摘 要 : 禁 忌 搜 索 被 称 为 是 在 解 决 一 个 各 种 难 的 组 合 问 题 的 高 效 方 式 ， 其 中 包括 时 间 表 。 这 分 论 文 用 禁 忌 搜 索 解 决 真 实
2、世 界 的 高 中 时 间 表 的 问 题 。 该 算 法有 两 个 阶 段 ： 用 贪 婪 算 法 的 初 始 化 阶 段 和 使 用 禁 忌 搜 索 改 进 阶 段 。 在 禁 忌 搜索 算 法 三 种 移 动 使 用 ： 单 移 动 ， 交 换 移 动 和 块 移 动 。 该 算 法 的 实 现 已 有 效 试验 在 越 南 两 所 高 中 。关 键 词 ： 排 课 ， 高 中 时 间 表 ， 共 通 启 发 式 演 算 法 ， 禁 忌 搜 索 。1 引言一般来说，高中时间表问题包括每周都在适当的时期安排学校的讲座，但高中学校的差异让大多数算法不能够单凭一种算法就能有效地解决所有高中的问
3、题。我们在本文中考虑的问题是由采取了现实世界中越南学校的问题,我们提出的解决方案的解决了这个具体问题。像大多数的教育时间表问题，高中时间表是已知是 NP 难题。由于该问题的复杂性，在近数十年来（从 20 世纪 80 年代），共通启发式演算法是解决组合难题的优秀方法。其他热门的共通启发式演算法如遗传算法，模拟退火，禁忌搜索.已应用于高学校排课成效显着8 - 10-12。我们用来解决我们的问题的方法是禁忌搜索，这是第一次由弗雷德格洛弗于1989 年推出了2。到现在为止，许多学界的科学家已经改革了禁忌搜索算法的不同版本来解决高中时间表的问题4-6 - 13。我们的建议是用禁忌搜索算法的求解概率一个简
4、单而有效的适应适当的时间分配连续的讲座块 LEM。我们在两所高中做实验。结果在合理的时间得到的（少于十五分钟）。北京化工大学本科毕业设计（论文）翻译1本文组织如下：第 2 节给出禁忌搜索的概述及发展，第 3 节描述了我们认为高中时间表的细节问题，第 4 节介绍了该算法的细节，第 5 节呈现的实验结果，而第 6 节示出的结论。2 禁忌搜索 禁忌搜索算法是一种用于求解最流行的启发式组合优化问题的方法。现在我们简要介绍一下最基本的禁忌搜索的组成部分。我们指的9进行了全面的描述与各种变种和这种算法许多有效的额外策略。从一个初始解，禁忌搜索迭代，从一个解寻找另一个搜索空间的不同部分，试图找到一个解决方案
5、，最小化目标函数的值的一个函数，评价该解决方案的成本。在每一次迭代中，选择一个解决方案作为当前的解决方案，以及在这个迭代的搜索空间的一部分是根从它产生的，这部分被称为当前解的邻域。禁忌列表是用来储存信息的最近应用的移动。移动目前被储存在禁忌表中被称为禁忌移动。这些动作是被禁止的只要他们仍然在禁忌表中使用。然而，一些禁忌移动有足够的高度来提高目前的解决方案，并应考虑使用，这意味着他们的禁忌状态应该被丢弃，这就是为什么使用意愿准则。在每次迭代中，如果它们被检查，将检查禁忌动作满足愿望的标准，如果他们这样做，他们的禁忌状态会下降迅速地。在许多情况下，吸入的标准，常常是，“如果新方案应用禁忌移动到当前
6、的解决方案的目标函数的值小于迄今为止发现的最好的解决方案，这将是禁忌的从禁忌列表中删除。”3 问题描述高中排课问题，本文考虑的是从两越南的高中。它包括寻找一组课程和一个地图之间的地图这样一种方式，满足了高中的要求尽可能。过程是一组演讲（演讲持续了一个时期），有相同的老师，上课和课题。课程的主要信息包括教师这门课，一门或北京化工大学本科毕业设计（论文）翻译1几门课，在涉及的主题和一些讲座属于本课程。课程同一个老师或同一个班级被分为一个有冲突的课程群。有 3 个硬约束，必须满足，和 7 个软约束，尽可能地满足。第一硬约束（H1）：一个课程的数量在一个连续范围内 minconsecutivelect
7、ures 范围，maxconsecutivelectures 。第二硬约束（H2）：教师不能被分配给他们不可用的时间。第三硬约束（H3）：所有课程必须分配。第一软约束（S1）：冲突的课程不能够重叠。第二软约束（S2）：课程数量（应在 minsessions 范围，maxsessions 。第三软约束（S3）：课程分配到的时期，他们优先。第四软约束（S4）：空闲时间的讲座在一个集合的老师应该避免一个类。第五软约束（S5）：期间，一类是分配在一个天数应等于或小于maxstudyingperiods。第六软约束（S6）：一天之间老师和教师都空闲的情况应该避免。第七软约束（S7）：那是指定老师的会话数
8、应该尽可能小。（注意：每门课程都有自己的 minconsecutivelectures，maxconsecutivelec的特点，minsessions 和 maxsessions 参数）目标函数wi and di 是重量和对违反软约束数。北京化工大学本科毕业设计（论文）翻译14 算法 4.1 阶段 1：利用贪心算法构建初始解在这一阶段，课程分块（一块是一组连续的 LEC等），例如，课程的时间是 5期（即包括 5 讲）分为两块： 2-lecture 块和 3-lecture 块，这些块将分配到适当的时期。所有这些步骤都是使用贪心算法完成的。每一步的细节描述如下：1。对于每一个课程，列出了所有的
9、块分裂的方式，即，本课程的方法可以分成块。例如：课程的持续时间是 6 个时期，其 minconsecutivelectures 是 2 它是 3 maxconsecutivelectures 有 2 块分裂方式：第一块的分裂方式（B1）：（2,2,2），即，课程分为三块；每个区块包括 2 个讲座（最后 2 个持续时间）。第二块的分裂方式（B2）：（3,3），即，课程分为两块；每个区块包括 3 个讲座（最后三个连续的时期）。2。当然每个块的分裂方式大艾，列出所有的时间块（即集连续周期），块大能分到和插入为列表 LIJ 时期分配方式（注意期 PK 可以分配给当然如果课程的老师和课程都可以在期 PK
10、）。3。选择一个具有最小总次数分配的过程方法（基于二步的结果）。4。从所有列表 LIJ 当然 AI，选择一段 sijk 分配方式的影响其他课程尽可能少。这意味着，如果课程的人工智能被分割成块分裂方式和分配方式分配这段 sijk，减少总一个属于同一类课程的时间分配方式冲突过程中的课程群当然是最小的。5。指定课程 AJ 选择块分裂方式和时间分配方式 sijk ij。如果所有的列表 LIJ当然爱是空的，块分割的方式和时间分配在随机选择过程中使用的方法是随机选择的。6。更新信息（删除过程中的人工智能和所有分配的时间从探讨）。7。如果没有课程供考虑，移动到 2。否则，返回到第一步。北京化工大学本科毕业设
11、计（论文）翻译14.2 阶段 2：使用禁忌搜索的改进得到的解决方案 在这个禁忌搜索阶段，使用的主要种类是单动作。更多 另外，其他 2 种动作，包括互换动作和块移动， 当使用一些原始动作（动作，不完善的最好 解决方案发现到目前为止）已经通过。禁忌搜索的每一个组件的详细信息 下面描述：单步移动一个单一的行动包括三个部分：一个课程的 AI，当然 Pij 一块 AI，和一个新的合适的时间块 Rij 表示（即课程的老师，上课必须用能够在所有时期的 RIJ）阻断Pij 将分配给。我们只是考虑 vsinglemove（qcur），附近的 nsinglemove 子集（qcur）目前的解决方案 qcur。vs
12、inglemove（qcur）通过检查所有块的所有课程和choosingfeasible 创建的解决方案（满足硬约束的解决方案），或非禁忌愿望函数满足。交换移动在某些情况下，单一动作不能改善当前的解决方案和搜索过程将被卡住，例如，当时间表创建的太紧，有可能没有洞可以移动一个课程的块。交换动作可能是一个很好的候选人解决这个问题。一个交换移动有五个部分：两课的 AI 和 AJ，两块（PIM PIM 和该大小必须大于或等于该课程的 AI）和 AJ 和整数 exchangingway。如果 PIM 的大小等于该尺寸，对 exchangingway 值总是 1，否则，exchangingway 是在 1
13、 的范围。让 RIM，rjn 是 PIM 和该当前块和 rim，rjn 应用交换移动后的 PIM 和该新时期块。rim 和 rjn 是基于对移动 exchangingway 价值确定： ExchangingWay = 1: Rim = Rjn, Rjn = Rim. ExchangingWay = 2: Rim = Rjn - 1, Rjn = Rim. ExchangingWay = 3: Rim = Rjn - 1, Rjn = Rim + 1. ExchangingWay = 4: Rim = Rjn, Rjn = Rim + 1.北京化工大学本科毕业设计（论文）翻译1这种移动应用的每一
14、 nswapmove 连续未改进的迭代 单动。当使用交换移动时，该单移动不 考虑。在三个连续的迭代中所使用的交换动作只是选择 只要能提高当前解的目标函数值 qcur。在那之后，单一的动作将被使用。无禁忌表，无误 标准是用来交换移动。块移动块改变移动改变了当前块分裂的方式和时间一个课程的新的区块。这些移动应用都 changingmove NBLOCK 改良的连续迭代与单一运动。当它们被应用时其他动作不考虑。这一举动将在一次迭代中被考虑只是如果它能改善 qcur qcur 应用到当前解决方案。这类包含 3 个组成部分：一个当然是人工智能，一个新的分块当然，这一段路 AI，AI会分配，新时期的方式
15、sijk 被分配给。该子集的 Vblock changingmoves（qcur）附近的 NBLOCKchangingmoves（qcur），其中包含的可行解，无禁忌或愿望满足，检查。因为课程总数大，我们只是调查的子集 vswapmove（qcur）交换的移动邻域nswapmoves（qcur）。vswapmove（qcur）是通过对现有课程设置百分之 30、选择产生ING 的动作，可以提高 qcur。请注意，交换移动具有更高的优先级块移动。禁忌表禁忌表是：一个用于单个移动，另一个用于块改变移动。单一动作的禁忌表的元素有三个组成部分：当然，人工智能，块 Pij 和老年期阻滞 Rij 表示分配给
16、 Pij。当一个移动被选择适用于当前的解决方案，这些信息将被添加到禁忌表和将存在一个禁忌任期数的迭代。一个移动是禁忌的时候它的课程，它的块和它的新时期是在禁忌表。在每次迭代中，禁忌使用权价值是在 0.25tb 范围内随机选择，0.5TB （TB 是课程数量的平方根。一种块变化移动的禁忌表的元素包含的信息当然 AI 当然老块分裂的方式大爱。如果是一个移动是禁忌的课程及其新的分块拆分方式都在禁忌表中。禁忌使用权固定到三。愿望准则北京化工大学本科毕业设计（论文）翻译1在许多其他的论文中，所使用的愿望准则是一样的 4 5 6 。一个qnei 满足期望标准的当且仅当 F 的邻居解（qnei） F（qbe
17、st）而 qbest 是最好的解决办法是迄今为止所发现的。停止条件搜索过程被停止，当它符合下列标准之一：迭代次数为 3000。迄今为止发现的最佳解决方案满足所有约束。连续的未改进的迭代次数为 1000。5 实验结果所提出的算法应用到三个真实世界的情况下，高学校在越南为天才 Tran Phu 高中高中。这个每一个实例的详细信息都在表中列出，有以下简称：S:试者的数量，Cr：课程的数量，T：教师数量 C：班级人数。Co：课程的冲突百分比冲突过程对的数量：属于课程的总数同一冲突课程群。 AvT (Available Teachers): 可用百分比的教师。PpD 是每天的时间段，D：时间表的天数。北
18、京化工大学本科毕业设计（论文）翻译1 AvCr (Available Courses) : 课程的可用性用于测试的软约束的权重：w(S1) = 100, w(S2) = 5, w(S3) = 10, w(S4) = 5, w(S5) = 5, w(S6) = 5, w(S7) = 5 ，运用这些值， maxStudyingPeriods, PpD 和 D 的值为 9, 12 and 6. 我们选择 nSwapMove 和 nBlock-changingMove 10, 20,30,40,50,70,100,200,测试这些参数的值对所有可能的发现对20,30(nSwapMove = 20 an
19、d nBlock-changingMove = 30)给出最佳结果，因此，结果下面列出了这两个参数的值。源代码是由作者来实现的。的配置用于测试计算机的 CPU 酷睿 2 双核，1GB RAM，和 Windows XP 操作系统。每个实例的算法进行了测试十次。一般的结果，包括初始解，最佳解，平均解和平均运行时间表 2 中显示。平均详细结果见表三、表四表手工制作的时间表以侵害结果的实践。实例 1 和 2 的大小分别为 128 和 244 个课程，例如 3 是一个有位大，有 401 门课程。类的可用性都大于 90%，这可能有助于排课容易。然而，老师的时间有点紧课程之间的冲突不小。因此，在一般情况下，
20、排课任务可能不容易。禁忌搜索阶段后，初始解得到了很大的改善。平均结果没有太大的不同，从最好的结果。时间运行的建议在这些情况下的算法不太大（不到十五分钟）。第一软约束S1，这是最重要的（即具有最高的重量），在所有情况下都满足。违反约束的 S7 是大数（25%在数据 1、80%在数据 2 和数据 3）。原因是我们使用的方法计算约束 S7 违规只是一个近似的一个原因。如下：北京化工大学本科毕业设计（论文）翻译1比精确的一个要快得多，所以得到的违规总是大于或等于真正的违规。从该算法获得的时间表都与手工得到的算法相比，更实用。事实上，当教师的可用性百分比用手工拍课程表中列出的数字都增长了 85（大于表一
21、中的数据），这意味着在手工制作的时间表考虑的问题比我们更简单。大多数的软约束中的自动化较少违规版本，除了第二约束。在一般情况下，自动时间表解比手动的好。另一方面，时间手工排课程表的时间总是比自动化系统用的时间长，大约一天到一天半左右。北京化工大学本科毕业设计（论文）翻译16 结论 在本文中，通过使用禁忌搜索算法，有效的研究了并解决了两个具体高中学校的排课问题。得到的结果比手工排课方法好。该算法也可以扩展以适应其他高中排课问题的要求。此外，作者还开发了一个基于网络的自动排课组利用该算法作为内核解算器的系统。该系统还提供许多功能，支持高学校的工作人员和教学管理机构在互联网上制作时间表。更多细节访问
22、 www.fit.hcmuns.edu.vn/nmkhang/hts 。参考文献1. Nguyen, D.T.T., Khon, T.T.: Research on university timetabling algorithms. Bachelor Thesis, Information Technology Faculty, Ho Chi Minh University of Science, Vietnam (2007) 2. Glover, F.: Tabu Search - part I. ORSA J. Comput. 1(3), 190206 (1989) 3. Schaerf
23、, A.: A Survey of Automated Timetabling. Dipartimento di Informatica e Sis-temistica, Dipartimento di Informatica e Sistemistica (1999) 4. Schaerf, A.: Tabu search techniques for large high-school timetablingproblems. Com-puter Science/Department of Interactive Systems (1996) 5. Santos, H.G., Ochi, L.S., Souza, M.J.F.: A Tabu Search Heuristic with Efficient Diver-sification Strategies for the Class/Teacher Timetabling Problem. ACM J. E. A 10, 116 (2005)
