英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

用于解决大学时间安排问题（UGA）的基于利用率的遗传算法

Esraa A. Abdelhalim *，Ghada A. El Khayat

埃及亚历山大亚历山大大学商学院信息系统和计算机系

摘要：摘要建立大学时间表是一个复杂的过程，其考虑了从一个机构到另一个机构的不同类型的约束和目标。本文解决的问题是一个真正的问题，其中包含一些不是很常规的硬约束和软约束。所追求的目标是也是新的，考虑最大化资源利用率。本文介绍了一种使用一些启发式的遗传算法来生成可行的优质时间表的初始种群。该算法使用简单的加权和公式来尊重教授的喜好和处理冲突。为了减少浪费，介绍了以学习空间利用率为重点的交叉型。还使用使用本地搜索启发式的目标变异算子。该算法应用复合适应度函数，其考虑空间利用，事件之间的间隔和每天的最大讲座数。来自埃及亚历山大大学商学院的实际数据的大型数据集被用来测试这种协同算法。该算法也针对文献中的两个困难的基准问题进行了测试。测试证明，开发的算法是大学管理时间和资源的有效工具。它在两个基准问题的大数据集上表现良好，并且还比两个基准数据集的初始问题陈述中所述的约束更多。

关键字：大学时间表、资源管理、空间利用率、遗传算法、高等教育问题

第一章 介绍

时间安排是一个NP-硬优化问题^[1-3]，需要在一组复杂变量和约束之间找到一个很好的解决方案。问题是分配一个可变的元组，优化一组度量和指标，例如最小化时间间隔，最大化空间利用率，并最大限度地减少与资源使用相关的成本^[4]。为这种问题找到一个有效的算法是困难和复杂的，特别是当问题变大时。根据Tovey ^[5]，当硬度或简易性更好地理解问题时，可以提供良好的解决方案。教育机构等组织使用时间表来安排班级或讲座，通过以最佳利用可用资源的方式分配未来事件的时间和地点^[6-10]。大学越来越多地处理了大量的课程，小组和教授。设计不当的时间表不仅不方便，而且导致时间，精力和金钱方面的巨大损失。

大学校园空间分配越来越重要。大学内的空间包括房间，大厅，露天剧场，办公室，停车场。越来越多的学生每年流动，增加了管理和利用这些空间的需求。空间分配问题也是NP-Hard作为时间安排问题。当寻找最优解时，存在将E事件分配给P个地方的PE方法^[11]。这意味着不存在有效的算法来解决这些问题在一个可重用的时间的大的事例^[12]。问题的大小，其约束和目标的变化也将影响执行空间分配所需的时间，同时保证空间的良好利用水平^[13]。

Shove ^[14]在她的“空间经济学黑洞”报告中指出了学生，讲师，时间表和行政人员的相互依赖和相互冲突的关系。她强调，每个人都善于利用空间和他自己对什么有效的空间管理手段的定义。Shoves解释说，高估对更多空间的需求是对不确定性的理性反应。她确认，如果没有适当的计划和愿景来确定良好的利用水平，空间被视为一种自由的好处就是这种情况。空间分配不足可能迫使决策者提供不必要的资源。在解决高等教育中的空间分配问题时，可以使用的空间不同，每个空间的不同用途，可用时间和所有其他约束需要被识别。在学术机构中，人工解决资源分配问题的方法可能会浪费大量资源，从而更好地管理和利用资源。

推动这项研究的一个关键方面是，以前的研究主要集中在提出的算法的计算时间^[15-20]，即使考虑到一个小问题实例和很少的约束。相比之下，埃及公立大学现有的资源有限，还有大量的学生和教授，迫使我们把重点放在真正的问题上以及相关的制约。事实上，计算时间不应该再成为这种问题的焦点，在这些问题上，解决方案并不是瞬间需要的。即使开发的算法具有相对较长的时间，它们至少能够满足以下要求：（i）响应一个实际问题的约束，（ii）解决大尺寸问题实例，（iii）花费更少的时间比手册过程是因为构建时间表在实际需要之前开始很长时间^[21,22]。

本文提出了一种用于解决大学课程时间安排问题的遗传算法。研究的案例是埃及亚历山大大学商学院，在学术期开始前六周开始建立本科学期课程。

本文的组织结构如下：第二章回顾有关时间安排和空间分配问题的相关工作。第三章描述了贡献的解决方法。第四章是测试和结果。第五章包括结论和未来工作，并在上一章中做出了确认。

1. 相关工作

大学课程时间安排问题由卡特和拉波特[23]定义为多维问题，其中一些学生和教授被分配到讲座和事件。一个事件是一对合适的房间和时间段^[24]。作者^[25]指出，房间和空间分配决定是与机构内部的时间安排程序相关的问题。Burke和Varley ^[26]也认为，学术机构的空间分配和时间安排问题是密切相关的。Schaerf ^[27]进行了一项调查，以收集必要的信息，以了解不同的时间安排问题以及用于解决这些问题的不同方法和方法。他声称所有使用方法背后的基本概念依赖于“首先安排最有限的讲座”，并且区别于另一个的事物是如何将表达“最紧张”定义在不同的问题正在解决。大学和学术机构的空间分配是为一套房间和时间间隔设置一次讲座或会议^[26,28,29]。

Burke和Varley ^[26]为在英国九十六所大学和学术机构中定义和发现空间分配问题的不同维度和要求作出了许多努力。他们通过问卷调查了大学的信息。调查问卷主要在三个方面强调：空间分配过程的规模和多样性，用于自动化空间分配过程的工具以及分配这些空间时所考虑的限制。这项调查的主要目的是发现问题的一般解决方案是否可以阐明，否则大学之间的差异将会阻止这种做法。他们得出结论，空间分配的通用系统必须能够满足大学规定的所有要求。

用于解决空间分配问题的不同方法也用于解决时间安排问题。这些包括模拟退火^[30-32]，禁忌搜索^[15,33-35]，整数规划^[36]和遗传算法^[37-39]。一些贡献如下。

Sutar和Bichkar ^[16]引入了一种遗传算法来解决印度真正的大学时间安排问题。随机生成初始种群，并根据其适应度值选择父母进行交叉。所有从交叉产生的浮泉都会发生突变；然而，应用的交叉和变异算子的实现在他们的工作中并不清楚。在一系列硬、软的关系中，没有提到学习空间能力。Lect tures的时间段可用性没有被优先考虑，但是每个工作时间的最小和最大限制被设定。

Rakesh和Gupta ^[40]使用混合算法构建了大学课程时间表。他们使用遗传算法和迭代本地搜索来避免被困在局部最优中。他们的做法的目标是满足一系列严格的限制，并最大限度地减少对软约束的侵害。困难的限制包括让学生在任何时间都参加一个活动，将所有活动分配给具有足够座位数的合适空间，并且在任何时间段内为任何一个房间分配一个活动。软限制是在最后一天的时间段内避免调度事件，避免为学生安排一天以上的连续两次事件，并确保为所有学生安排一天以上的事件。他们的混合算法没有考虑到所提出的目标函数中的利用率。

El-Sherbiny等人^[41]提出了攀登优化和遗传算法的组合来建立大学课程时间表。作者的目标是最小化违反任何软约束条件。严格限制的一套方面，教师或教授不得在任何时间被分配到多个班级，一个班级不能在一个时间段内分配给多于一名教师，而且房间不能多于一次分配给定的时间。此外，该算法应该每星期遵守一定数量的时隙，而一个班级每周应该参加一定数量的讲座。在成本函数中表示的一套软约束中，空间的利用是相符合的。成本函数旨在最大限度地减少参加的学生人数与学习空间的能力之间的差异。

Socha等人^[42]提出了两种蚂蚁系统，用于解决大学课程时间表：蚁群系统（ACS）和MAX-MIN蚂蚁系统。他们的目标是在可行的时间表中尽可能减少软约束违规的数量。这些约束包括以下几点：最大限度地减少学生在日期插槽中学习的课程数量，并最大限度地减少学生每天有不止一班课程的概率。这两种算法都以蚂蚁种群开始，每个蚂蚁通过将所有事件分配给时隙来开始构建时间表。蚁群基于启发式信息和信息素值矩阵来概率地选择时隙。然而，两种提出的算法在更新信息素值方面是不同的。MAX-MIN蚂蚁系统使用全局更新规则设置上限和下限，以控制最高和最低信息素水平之间的最大差异。另一方面，ACS将全局更新规则添加到特殊的本地更新规则中。该局部更新被应用于信息素矩阵中的所选元素，对应于事件（e）的某个时隙（t），以降低其他蚂蚁在同一事件中选择相同时隙的概率，并且鼓励他们选择其他时间很多。在将所有事件分配给时间间隔之后，分配房间并应用爬山本地搜索启发式来改善所产生的解决方案。考虑到空间能力和参加人数的困难因素。

Lu和Hao ^[15]开发了一种自适应禁忌搜索，其中使用贪婪搜索启发式构建了初始时间表。这个贪婪的搜索从空的时间开始，并通过选择未签名的讲座和合适的时间间隔事件来开始分配讲座。然而，贪婪搜索启发式在开始执行时间表构建过程时往往能够有效地工作，同时又引发了后续事件的分配^[32]。该方法的目标是在可行的时间表中尽量减少软约束冲突的数量。虽然教师的时间段可用性被认为是一个主要的困难限制，但是如果一位以上教师的可用插槽数量相同，则没有纳入优先考虑方法来处理此问题。

萨巴尔等人^[18]引入了一种蜜蜂交配优化算法（HBMO）来解决检测和课程时间问题。目的是满足一系列严格的限制，并且在软约束被违反的情况下尽量减少受影响的学生人数。萨巴尔等人^[18]使用最小饱和度优先（SD），最大程度优先（LD）和最大入学首（LE）启发式与蜜蜂算法来创建初始可行时间表。所采用的交叉是通过从蜂后和雄蜂中选出两个随机基因（时隙）完成的，并将所有事件从时隙1（T1）移动到例如雄蜂中的女王到时隙2（T2）。如果事件不与新时隙中的事件相冲突，或者在新时隙中不存在，则会成功执行此操作。适用于在两个时隙之间交换事件子集的突变算子，用于防止雄蜂的精子在另一个交配飞行中再次被使用。作者表明，蜜蜂交配优化算法是解决教育时间安排问题的有前途的方法。一系列艰难的压力与以前的贡献非常相似。该集合包括根据房间容量分配事件。教授的可用性时间和偏好被认为是硬约束或软约束。

Chen和Shi ^[20]使用两种粒子群优化（PSO）类型：惯性权重和压缩版本来构建大学时间表。目标是尽可能尊重软约束，增加教师和班级的满意度。在一整套软约束下，教师的偏好以及学生受到尊重。通过调查表收集教师的优先权，通过问卷调查，将教师的时间从1到5从最不利的时间到最有利的时间段排列，而不可能到时间表的时间是10。然而，没有任何硬或软的限制提到尊重房间能力的重要性。陈和士认为，优先考虑教师是对时间表质量有重要影响的有效因素^[20]。本文提出的研究考虑了这一方面。

选择遗传算法来解决本文的问题，因为它们在解决复杂的组合问题中具有优势^[43,44]。遗传算法的特点是灵活性和在复杂，大空间中搜索的能力^[45]。他们被认为是解决课程和考试时间安排问题最有力的工具之一^[46-48]。此外，遗传算法具有自适应搜索算法的优点^[49]。

第三章方法论

在时间表方面的发展导致启动了自动化时间表（PATAT）系列会议的实践与理论，该计划主办了国际时间表大会（ITC）^[50]。本次比赛旨在鼓励在时间表方面的研究，弥合现实应用中的理论与实践之间的差距。本文提出了一种解决现实世界大尺寸时间安排问题的新方法。由于时间安排问题的复杂性，使用了广泛的启发式来找到可行的解决方案^[4,18,50]。本文有助于将教学事件分配给空格和时隙的遗传算法方法。它使用一些启发式来找到初始可行的解决方案，并考虑以下一组硬和软约束：

硬约束

1根据一定的优先级度量，贡献者分配其偏好的时隙。

2许多学生与房间容量兼容。

3在同一时间段，投资者不被分配到不同的房间。

4学生组在同一时间没有分配到不同的房间。

5不允许日期和日期时间（星期六和星期三结束周数）。

6所有时间表应包括所有讲座。

软约束

1每位教授每天不得超过两个讲座。

2每个团体每天不得超过两个讲座。

3一组的讲座之间没有差距。

4教授讲课之间没有差距

5每个事件的超时率不小于75％或等于0％。

大部分研究大学时间表的研究并没有考虑每个教授的时间可用性作为硬约束^[51-56]。其他一些人并不认为它是一个软约束^[18]。主要焦点往往是为了避免同时进行两次讲座的不可行性；对于教授或团体来说，房间的能力是根据预计参加人数^[57,29,58,9]考虑的，而不包括更多的现实生活中的困难约束，如教授的偏好和他们的时间段可用性。作为软约束的理论偏好很少有贡献^{[60,61,52,16]}。Badri ^[60]构建了一个部门时间表，分两个阶段来考虑专业人士的偏好：第一，最大限度地提高教师对课程偏好的矩阵；其次，他最大限度地提高了教师在阿拉伯联合酋长国大学讲授时间的偏好。一些研究人员建议引入教授偏好的效用函

全文共31431字，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[143953]，资料为PDF文档或Word文档，PDF文档可免费转换为Word