调度优化

问题描述 投票:0回答:1

(我已经为以下内容编写了一个蛮力解决方案,但我想知道是否有更优雅的路径。)

我高中的学生有 8 门选修课。他们选择了第一、第二、第三和第四个选择。由于将有两个选修课,每个人都可以参加他们选择的两个选修课。

然而,尚未确定哪些选修课将安排在这两个期间中的哪一个期间。调度问题是,在了解偏好的情况下,优化这两天的选修课分配,以便尽可能多的学生能够参加他们喜欢的两门选修课。

比如我报了IT和Art,如果时间不同,我只能同时报。当然,您可能已经注册了艺术和法语,而其他人则注册了法语和 IT。

由于只有两个时段,不可能每个人的选择都在不同的时段。我们如何才能找到选修课的最佳分配日期,让尽可能多的人获得他们的两个最佳选择?

我的蛮力解决方案是创建所有可能分配的列表(使用组合包)并测试每个分配。这很好用,因为数据集很小,但肯定有一个更优雅的图论或矩阵解决方案——并且不会与 n 成比例地增加资源! (n 是提供的课程数量)!

optimization graph-theory resource-scheduling
1个回答
0
投票

无需测试两个插槽中所有可能的课程组合。您只需要存在于学生选择中的测试组合。每个学生选择 4 门课程会创建 6 对,让学生可以参加两门课程

A,B,C,D => AD,AB,AD,BC,BD,CD

因此,枚举满足至少一个学生的课程配对,并为每个配对计算有多少学生包括该对。学生最多的一对就是答案。

- Construct empty map M, keyed by course pair, value count of students
- LOOP S over students
  - LOOP P over the pairs that let S take two courses
     - IF P in M 
          -increment value of P in map
     - ELSE 
         - add P to M with value 1
- SET PMAX to first pair in M
_ SET VMAX to value of first pair in M
- LOOP P over pairs in M
   - SET V to value of P in M
   - IF V > VMAX
        SET PMAX to P
        SET VMAX to V
- OUTPUT PMAX
© www.soinside.com 2019 - 2024. All rights reserved.