SQL高效的计划生成算法 [英] SQL efficient schedule generation algorithm

问题描述

想象一下拥有分支机构的教育中心。该教育中心的课程对于所有分支机构都是通用的。

Imagine education center which has branches. Courses of this education center are common for all 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;

房间，用于管理员生成的每门课程。例如，管理员输入数学课程的房间数。系统生成3个房间。换句话说，它们受到计数的限制。

Rooms in every branch for each course generated by administrators. For example, administrator enters count of rooms for Math course. System generates 3 rooms. In other words they are limited by count.

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个不同的学生组。

Every room has 5 available teaching hours per day. In other words, Math-1 will have 1 different student group in each teaching hour (of 5).

学生-也按分支分组。每个学生都喜欢上中学的每周计划（ week_day_mode ）。

Students -also grouped by branches. Every student has preffered weekly plan (week_day_mode) to come to secondary school.

• 每周的1、3、5天


• 每周的2、4、6天

班级字段是学校（主要学校）的成绩，

class field is grade in school (main school),

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 是学生与课程之间的联系的价值。

When administrator registers student for the first time, he selects all the courses that student wants to participate. For example, if 5 courses selected StudentCourseAssoc will be filled with 5 rows for this student. After testing student for basic knowledge level for each course, administrator evaluates student as "clever" (+1) or "dumb" (-1) on particular course. So knowledge_level is the value for student-course connection.

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;

应用程序必须：

自动分组（它可以创建新组或将学生添加到现有组）具有以下条件的每个分支机构的学生

Automatically group (it can create new group or add student to existing group) students of each branch with following conditions

• 聪明而又愚蠢的学生必须位于单独的位置组


• 组可能包含一些年级组合。因此，可以将9年级和10年级混合使用。和11级一起毕业（12级意味着sql毕业）。但不是10日至11日。 （将有2种模式：9-10、11-12）


• 最多可容纳8名学生。


• 课程室有限。因此，每个房间每天最多只能容纳5个小组


• 每个学生必须在1天之内参加每门（由他自己选择）的课程

• Clever and dumb students must be in separate groups
• Group may consist of some grade mixes. So, it's okay to mix 9th grade with 10th. And 11th with graduated (12th class means graduated in sql). But not 10th-11th. (There will be 2 mode: 9-10, 11-12)
• Group may consist of 8 students max.
• Course rooms are limited. So every room might host only 5 groups during day
• Every student must seat on every chosen (by himself) course in 1 day

搜索符合上述条件的组后，如果未找到，则应用必须创建，然后将学生分配给组。然后：

After searching for group that meets conditions above, if not found, app must create and then assign the student to the 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;

我做了什么

我正在尝试在知识评估期间将学生置于组（现有的或创建新的）中。例如，如果学生选择数学作为课程之一，那么当管理员评估他的数学知识并标记为肯定时，该程序就会开始为该学生选择合适的组：

And here is fiddle to play with.

What I've done

I'm trying to place student to the group (either existing or to create new one) during knowledge evaluation. Like, if student choose Math as one of courses, when administrator evaluates his knowledge of Math and marks positive the procedure starts to pick right group for this student:

• 功能标记学生的知识水平


• 检查学生的可用时间（例如，已经花了1个小时，那么他就有4个小时）


• 为搜索添加班级覆盖条件（例如9-10年级或11-12年级）


• 检查时间表表中学生的每周计划中是否有可用时间的班次

• Function marks students knwowledge level
• Checks available hours of student (say, 1th hour is already taken, then he has 4 available hours)
• Adds class coverage condition to search (like 9-10th grades or 11-12 grades)
• Checks schedule table if has any group in available hours in student's weekly plans

如果没有人，则尝试创建。

If there is no one, then attempts to create.

因此，PHP表示形式如下

So PHP representation looks like this

        //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


        }

问题是

从理论上讲，我的做法就像买票飞机没有错误，并且必须有效，但效率不高且不理想。必须以最有效的方式满足所有分组条件：最少的组数和满足有限的房间数策略。这种方法很快将使很多团体无法适应可用的房间时间。

The question is

Theoretically, the way that I'm doing is like buying ticket for airplane. Is errorless, and must work but it's not efficient and optimal. All of conditions of grouping must be met in a most efficient way: minimal group count and meeting limited room count policy. This methid soon will make plenty of groups which will not fit to available hours of rooms.

在评估过程中，我一小时一小时地学习学生，越来越难获得真正有效的结果。由于房间有限，找不到学生的团体和无法创建新团体的机会越来越多地花费了数小时的学生。

As I take hours of student one by one, (during evaluation process) it gets harder and harder to get really efficient results. Chance of not finding groups and not being to able to create new groups because of room limits is going up and up by taking hours of student.

您建议使用每个房间的每小时时间做什么？

What do you suggest to use to make use of every hour in every room?

基于@norbert_van_nobelen的答案，我创建了虚拟小时表并按照以下视图获取每个学生的所有可能的时空课程组合列表。

Based on @norbert_van_nobelen 's answer I created 'dummy' hours table and following view to get all possible hour-room-course combinations list for each student.

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

hoursthe real to be planned hour hours_available is the binary switch. So in the real code we add a where clause: WHERE hours_available=0 to get only the hours we want to plan against:

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`)
            )
        )
    )

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

Using this view gives full scene of current situation. But I still can't figure out the algorithm to

• 将学生分组的算法


• 房间中的组

以最有效，最优化的方式创建最少的组数。

in a most efficient, optimal way with minimal group count creation.

有任何建议吗？

推荐答案

此答案仅是作为计划部分的解决方案方向，而不是100％不错的解决方案：

This answer is just meant as a solution direction for the schedule part, not a 100% nice solution:

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

What you created, requires loops to be able to satisfy all the conditions.

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

To get such a case solved quicker, it can be practical to work in vectors instead in which in the vector all positions are represented by 0 (available) and 1 (taken).

所以学生/数学一期的问题：

So the student/math-1 issue:

说有2个房间和3个小时：那么每个房间的math-1向量为：

Say there are 2 rooms and 3 hours: The math-1 vector per room is then:

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

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

Essentially (I at least) do not care about if a certain room is available as long as 1 is available: So an AND per index could be the answer in this case for availability (remember: 0 is available):

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

Room 1: [1 0 0] Room 2: [0 0 0] Room result: [1 0 0] AND [0 0 0]=[0 0 0]

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

So an AND can tell if the first hour is still available.

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

If you now combine this with a student with the available hours (also just 3 for this example):

学生A：[0 0 1]
房间结果：[0 0 0]
Studen t使用此操作的OR匹配房间：
[0 0 1] OR [0 0 0] = [0 0 1]

Student A: [0 0 1] Room result: [0 0 0] Student matches with room using an OR for this operation: [0 0 1] OR [0 0 0]=[0 0 1]

因此，学生A将匹配到房间结果中。

So the student A would match into room result.

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

In SQL: The data model (part: Missing is the course match): Table room:

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个可用位置。

All data has been inserted into tables in full: In this case 1 room, 3 hours, 3 places available.

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);   

因此，学生仅在前两个小时有空。

So the student is available in the first two hours only.

现在要从查询中获取结果：

To now get a result from a query:

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

此结果仅需分成最多8个组，最后是

This result only has to be split into the groups of maximum of 8, in which it is the end of the SQL part and time for another programming language.

此模型可以用日期进行扩展，但是在仅使用小时和工作日的情况下效果最佳（再次提供工作日可用性） 0或1）。

This model can be expanded with a date, however it works best when using just hours and weekdays (weekday availability is again 0 or 1).

我说过：这是一个概念/想法，而不是100％的解决方案，因此在使用它之前需要先做一些工作。

As I stated: this is a concept/idea, not a 100% solution, so it needs work before you can use it.....

这篇关于SQL高效的计划生成算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！