创建基于偏好的调度算法
Creating a scheduling algorithm based on preferences
目前，我们正在尝试构建一个匹配应用程序，将学生与校友匹配到一个活动中。该活动由多个时间段组成，每个时间段中的每个学生都可以分配给一个校友。
对于每个时隙，校友有一个最大和最小数量的学生可以分配给他们，学生有一个最小数量的时间段可以分配给一个校友。学生也不应该被分配给同一个校友两次。不过，真正重要的是：学生可以提交一份对活动的偏好排序列表，其中包含他们想与之交谈的校友的排名。
该算法必须创建一个时间表，其中包含 "fair" 学生在校友和时隙中的分布。
我们已经得出结论，我们可能无法获得最佳解决方案，因此我们想尝试使用本地搜索来获得某种程度的 "fair" 时间表。然而，对于 运行 本地搜索，我们首先需要创建一些随机（但有效！）的计划，并考虑到容量和限制。这个 "random fill" 算法是我们 运行 遇到一些问题的地方，因为我们无法弄清楚如何创建一个具有上述约束的非确定性算法，甚至可以创建一个随机调度。
我们已尝试将问题转换为流问题，但生成的图太大，无法在合理的时间内解决，我们已尝试某种 FCFS 方法，但总是存在冲突的边缘情况存在要求算法进入递归循环，这可能需要很长时间，我们不妨强行执行时间表。
虽然我们自己无法弄清楚任何事情，但我们觉得一定有一些类似的问题可以用以前已经找到的算法来解决。如果有人遇到过与此类似的问题，我们很乐意提供帮助。
我会推荐一种简单的贪婪方法。每当您分配学生时，请将学生分配到他们最好的位置。其中best定义如下：
- 如果任何想要的校友在学生有空的某个时间段内没有达到最小值，那么最想要的这样的校友，在距离达到最小值最远的可用时间段中。
- 如果任何想要的校友在学生可用的某个时间段内没有达到最大值，那么最想要的这样的校友，在距离达到最大值最远的可用时间段中。
- 如果学生没有达到他们的最低要求，所有可用位置中的所有校友都达到了最大值，并且这些位置中的任何学生都超过了他们的最低要求，然后撞到指定的学生。选择基于该学生的偏好减去学生偏好尽可能高的学生（即，从第 5 个槽位撞到某人比从第 1 个槽位更容易撞到一个学生），并通过撞到最远超过他们最小值的学生来打破平局。
- 这次没有分配。
随机分配所有学生，并尝试分配给他们。再次打乱它们，然后重复。当有一个完全没有分配的通行证时停止。
此算法不能保证找到最佳解决方案，或找到解决方案。但是在合理的约束下，很有可能在多项式时间内找到一个像样的解。
目前，我们正在尝试构建一个匹配应用程序，将学生与校友匹配到一个活动中。该活动由多个时间段组成，每个时间段中的每个学生都可以分配给一个校友。
对于每个时隙，校友有一个最大和最小数量的学生可以分配给他们，学生有一个最小数量的时间段可以分配给一个校友。学生也不应该被分配给同一个校友两次。不过，真正重要的是：学生可以提交一份对活动的偏好排序列表，其中包含他们想与之交谈的校友的排名。
该算法必须创建一个时间表，其中包含 "fair" 学生在校友和时隙中的分布。
我们已经得出结论，我们可能无法获得最佳解决方案，因此我们想尝试使用本地搜索来获得某种程度的 "fair" 时间表。然而，对于 运行 本地搜索，我们首先需要创建一些随机（但有效！）的计划，并考虑到容量和限制。这个 "random fill" 算法是我们 运行 遇到一些问题的地方，因为我们无法弄清楚如何创建一个具有上述约束的非确定性算法，甚至可以创建一个随机调度。
我们已尝试将问题转换为流问题，但生成的图太大，无法在合理的时间内解决，我们已尝试某种 FCFS 方法，但总是存在冲突的边缘情况存在要求算法进入递归循环，这可能需要很长时间，我们不妨强行执行时间表。
虽然我们自己无法弄清楚任何事情，但我们觉得一定有一些类似的问题可以用以前已经找到的算法来解决。如果有人遇到过与此类似的问题，我们很乐意提供帮助。
我会推荐一种简单的贪婪方法。每当您分配学生时，请将学生分配到他们最好的位置。其中best定义如下：
- 如果任何想要的校友在学生有空的某个时间段内没有达到最小值，那么最想要的这样的校友，在距离达到最小值最远的可用时间段中。
- 如果任何想要的校友在学生可用的某个时间段内没有达到最大值，那么最想要的这样的校友，在距离达到最大值最远的可用时间段中。
- 如果学生没有达到他们的最低要求，所有可用位置中的所有校友都达到了最大值，并且这些位置中的任何学生都超过了他们的最低要求，然后撞到指定的学生。选择基于该学生的偏好减去学生偏好尽可能高的学生（即，从第 5 个槽位撞到某人比从第 1 个槽位更容易撞到一个学生），并通过撞到最远超过他们最小值的学生来打破平局。
- 这次没有分配。
随机分配所有学生，并尝试分配给他们。再次打乱它们，然后重复。当有一个完全没有分配的通行证时停止。
此算法不能保证找到最佳解决方案，或找到解决方案。但是在合理的约束下，很有可能在多项式时间内找到一个像样的解。