SQL高效调度生成算法

2024-01-16

The idea

想象一下教育中心有branches. Courses该教育中心的信息对所有分支机构都是通用的。

Branches

CREATE TABLE `Branch` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8;


CREATE TABLE `Course` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `active` tinyint(1) DEFAULT '1',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

Rooms在管理员生成的每门课程的每个分支中。例如，管理员输入数学课程的房间数。系统生成3个房间。换句话说，它们受到数量的限制。

CREATE TABLE `Room` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `branch_id` int(10) unsigned DEFAULT NULL,
  `course_id` int(10) unsigned DEFAULT NULL,
  `occupied_hours` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

每个房间每天有 5 个小时的可用教学时间。换句话说，Math-1每个教学小时（共 5 个）将有 1 个不同的学生小组。

Students-也按分支分组。每个学生都有自己喜欢的每周计划（week_day_mode）来中学。

一周中的第 1 天、第 3 天、第 5 天
一周中的第 2 天、第 4 天、第 6 天

class字段是学校（主要学校）的年级，

CREATE TABLE `Student` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `fullname` varchar(255) NOT NULL,
  `class` tinyint(2) DEFAULT NULL,
  `branchID` int(10) unsigned DEFAULT NULL,
  `week_day_mode` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `branchID` (`branchID`)
) ENGINE=InnoDB AUTO_INCREMENT=246 DEFAULT CHARSET=utf8;

当管理员第一次注册学生时，他选择了学生想要参加的所有课程。例如，如果选择了 5 门课程StudentCourseAssoc将为该学生填充 5 行。在测试学生每门课程的基础知识水平后，管理员将学生在特定课程上评估为“聪明”(+1) 或“愚蠢”(-1)。所以knowledge_level是学生与课程连接的价值。

CREATE TABLE `StudentCourseAssoc` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `studentID` int(10) unsigned DEFAULT NULL,
  `courseID` int(10) unsigned DEFAULT NULL,
  `knowledge_level` tinyint(1) DEFAULT NULL,
  `group_id` int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1144 DEFAULT CHARSET=utf8;

申请必须：

自动对符合以下条件的每个分支的学生进行分组（可以创建新组或将学生添加到现有组）

聪明和笨的学生必须分在不同的组
组可能由一些等级混合组成。所以，把9年级和10年级混在一起是可以的。第 11 名已毕业（第 12 名意味着 sql 专业毕业）。但不是10日至11日。（将有2种模式：9-10、11-12）
团体最多可包含 8 名学生。
课程房间有限。因此，每个房间白天只能接待 5 组客人
每个学生必须在 1 天内选修（自己）选择的每门课程

搜索后group满足上述条件，如果没有找到，应用程序必须创建并将学生分配给group. Then :

CREATE TABLE `StudentGroupAssoc` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `group_id` int(10) unsigned DEFAULT NULL,
  `student_id` int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

CREATE TABLE `Schedule` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `group_id` int(10) unsigned DEFAULT NULL,
  `week_day_mode` tinyint(1) DEFAULT NULL,
  `hour` tinyint(1) DEFAULT NULL,
  `room_id` int(4) unsigned DEFAULT NULL,
  `teacher_id` int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `Unique Room for exact time` (`week_day_mode`,`hour`,`room_id`) USING BTREE,
  UNIQUE KEY `Unique Group for exact time` (`group_id`,`week_day_mode`) USING BTREE,
  KEY `Unique Teacher for exact time` (`week_day_mode`,`hour`,`teacher_id`),
  KEY `room_id` (`room_id`),
  KEY `teacher_id` (`teacher_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

这是可以玩的小提琴。 http://sqlfiddle.com/#!9/7de96

我做了什么

我正在尝试将学生安排到group（现有的或创建新的）在知识评估期间。例如，如果学生选择数学作为其中一门课程，当管理员评估他的数学知识并评分为肯定时，程序开始为该学生选择正确的组：

功能标志着学生的知识水平
检查学生的可用时间（例如，第 1 个小时已经占用，那么他有 4 个可用时间）
添加班级覆盖条件进行搜索（例如 9-10 年级或 11-12 年级）
检查学生的每周计划中是否有可用时间的小组

如果没有，则尝试创建。

所以 PHP 表示看起来像这样

        //sets knowledge level of student
        $studentCourse->knowledge_level = intval($_POST["mark"]);

        //check hours of student, and keep only available hours
        $availableHours = array_combine(range(1, 5), range(1, 5));

        //Unsets students unavailable hours from possible hours
        if ($student->GroupRels)
            foreach ($student->GroupRels as $groupRel)
                unset($availableHours[$groupRel->hour]);

        //Checks available groups based on class coverage
        if (in_array($student->class, ['11', 'G']))
            $classCoverage = "11-m";
        else if (in_array($student->class, ['9', '10']))
            $classCoverage = "9-10";

        $availableGroups = Group::find()
            ->with("schedule")
            ->where([
                    "Group.class_coverage" => $classCoverage,
                    "Group.knowledge_level" => $studentCourse->knowledge_level,
                    "Group.participiant_count<8",
                    "Schedule.hour" => $availableHours,
                    'Schedule.week_day_mode' => $student->week_day_mode
                ]
            )->all();


        if (count($availableGroups) > 0) {
             //Selecting one of groups
             //adding row to StudentGroupAssoc
            //adding row to Schedule
        } else {
            $group = new Group();
            $group->branch_id = $student->branchID;
            $group->class_coverage = $classCoverage;
            $group->course_id=$studentCourse->courseID;
            $group->knowledge_level=$studentCourse->knowledge_level;
            $group->save();
            ...
            //adding row to StudentGroupAssoc
            //adding row to Schedule


        }

问题是

理论上，我所做的就像买飞机票一样。没有错误，并且必须工作，但它不是高效和最佳的。必须以最有效的方式满足所有分组条件：最小组数并满足有限房间数政策。这种方法很快就会造成大量无法容纳可用房间时间的团体。

当我一个接一个地对学生进行数小时的培训时，（在评估过程中）获得真正有效的结果变得越来越困难。由于房间限制，找不到小组并且无法创建新小组的可能性会随着学生的时间而不断增加。

您建议用什么来充分利用每个房间的每一个小时？

UPDATE

根据 @norbert_van_nobelen 的回答，我创建了“虚拟”小时表和以下视图，以获得每个学生所有可能的小时-房间-课程组合列表。

hours实际计划时间hours_available是二进制开关。因此，在实际代码中，我们添加一个 where 子句： WHERE hours_available=0 来仅获取我们想要计划的小时数：

SELECT
    `s`.`id` AS `student_id`,

IF ((ifnull(`sch`.`hour`, 0) > 0), 1, 0) AS `hour_available`,
 `d`.`hours` AS `hours`,
 `sca`.`courseID` AS `courseID`,
 `sch`.`room_id` AS `room_id`,
 `sca`.`knowledge_level` AS `knowledge_level`,
 (
    CASE
    WHEN (
        (`s`.`class` = 9)
        OR (`s`.`class` = 10)
    ) THEN
        '9-10'
    WHEN (
        (`s`.`class` = 11)
        OR (`s`.`class` = 12)
    ) THEN
        '11-12'
    ELSE
        '??'
    END
) AS `class_variant`
FROM
    (
        (
            (
                (
                    `dummy_hours` `d`
                    JOIN `Student` `s`
                )
                LEFT JOIN `StudentCourseAssoc` `sca` ON ((`s`.`id` = `sca`.`studentID`))
            )
            LEFT JOIN `StudentGroupAssoc` `b` ON ((`s`.`id` = `b`.`student_id`))
        )
        LEFT JOIN `Schedule` `sch` ON (
            (
                (
                    `sch`.`group_id` = `b`.`group_id`
                )
                AND (`d`.`hours` = `sch`.`hour`)
            )
        )
    )

使用此视图可以全面了解当前情况。但我仍然无法弄清楚算法

将学生分组
将组放置在房间中

以最有效、最佳的方式创建最少的组数。

有什么建议么？

这个答案只是作为日程部分的解决方案方向，而不是 100% 好的解决方案：

您创建的内容需要循环才能满足所有条件。

为了更快地解决这种情况，可以在向量中工作，而不是在向量中所有位置都由 0（可用）和 1（采取）表示。

所以学生/数学 1 问题：

假设有 2 个房间和 3 小时：每个房间的 math-1 向量为：

Room 1: [0 0 0]
Room 2: [0 0 0]

本质上（至少我）不关心某个房间是否可用，只要有 1 个房间可用即可：因此，在这种情况下，每个索引的 AND 可能是可用性的答案（记住：0 可用）：

房间 1：[1 0 0] 房间 2：[0 0 0] 房间结果：[1 0 0] AND [0 0 0]=[0 0 0]

因此 AND 可以判断第一个小时是否仍然可用。

如果您现在将其与具有可用时间的学生结合起来（本例中也只有 3 个时间）：

学生A：[0 0 1] 房间结果：[0 0 0] 学生使用 OR 与房间进行此操作匹配： [0 0 1] 或 [0 0 0]=[0 0 1]

所以学生 A 会匹配到房间结果。

在 SQL 中：数据模型（部分：缺少课程匹配）：表间：

CREATE TABLE room(
room_id INT,
space TINYINT DEFAULT 0,
hour INT DEFAULT 1
);

CREATE TABLE student(
student_id INT,
space TINYINT DEFAULT 0,
hour INT DEFAULT 1
)

所有数据均已完整插入表中：在本例中，1 个房间、3 小时、3 个可用位置。

INSERT INTO room VALUES (1,0,1);
INSERT INTO room VALUES (1,0,1);
INSERT INTO room VALUES (1,0,1);
INSERT INTO room VALUES (1,0,2);
INSERT INTO room VALUES (1,0,2);
INSERT INTO room VALUES (1,0,2);
INSERT INTO room VALUES (1,0,3);
INSERT INTO room VALUES (1,0,3);
INSERT INTO room VALUES (1,0,3);

学生有：

INSERT INTO student VALUES(1,0,1);   
INSERT INTO student VALUES(1,0,2);   
INSERT INTO student VALUES(1,1,3);

因此，学生只能在前两个小时内有空。

现在获取查询结果：

SELECT room_id
FROM room a
INNER JOIN student b ON a.space=b.space AND a.hour=b.hour;

这个结果只需被分成最多8个组，其中它是SQL部分的结束和另一种编程语言的时间。

该模型可以使用日期进行扩展，但是在仅使用小时和工作日时效果最佳（工作日可用性再次为 0 或 1）。

正如我所说：这是一个概念/想法，不是 100% 的解决方案，所以在使用它之前需要做一些工作......

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)