SQL高效的时间表生成算法

Question

这个想法

想象一下有分支机构的教育中心.所有分支机构都有这个教育中心的课程.

分行

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;

管理员生成的每个课程的每个分支中的房间.例如,管理员输入数学课程的房间数.系统生成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个不同的学生组.

学生 - 也按分支分组.每个学生都有每周计划(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满足上述条件后,如果找不到,app必须创建然后将学生分配给group.然后 :

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;

这里有小提琴.

我做了什么

我正在尝试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`)
            )
        )
    )

使用此视图可提供当前情况的完整场景.但我仍然无法弄清楚算法

• 将学生分组
• 把小组放在房间里

以最有效,最优的方式创建最少的组计数.

有什么建议？

Answer 1

这个答案只是作为计划部分的解决方向,而不是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]和[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%的解决方案,所以它需要工作才能使用它.....