SQL高效调度生成算法怎么设计？
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，第五天
- 每周2，4，第六天
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)
- 小组最多可由8名学生组成。
- 课程房间有限。所以每个房间白天只能容纳5组
- 每名学生必须在一天内(自行选择)上每门选修的课程。
在寻找之后group如果没有找到，则应用程序必须创建，然后将学生分配给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;fiddle
所以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
}问题是
理论上，我所做的就像买飞机票一样。 是错误的，并且必须工作，但是它不是有效和最佳的。 必须以最有效的方式满足所有分组条件：最少的组数和满足有限的房间数量策略。 这种方法很快就会产生大量不适合可用小时的房间的小组。
当我一个一个地抽出几个小时的学生，（在评估过程中），得到真正有效的结果变得越来越难。 由于房间的限制，找不到团体和无法创建新团体的机会正在上升，需要花费数小时的学生。
你有什么建议可以利用每个房间的每个小时？
我创建了“虚拟”课时表和以下视图，以获得所有可能的时间-房间-课程组合列表为每个学生。
小时计划的实际可用小时数是二进制开关。 所以在真正的代码中，我们添加一个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`)
)
)
)利用这一观点可以充分了解目前的情况。但我还是想不出算法
- 将学生分组
- 把小组放在房间里
以最有效、最优的方式创建最小的组数。
有什么建议吗？
回答 3
Stack Overflow用户
发布于 2018-02-12 12:53:05
所创建的，需要循环才能满足所有条件。
为了更快地解决这样的问题，在向量中，所有位置都表示为0(可用)和1(已取)，这是可行的。
学生/数学-1期：
假设有2个房间和3个小时：那么每个房间的数学向量是：
Room 1: [0 0 0]
Room 2: [0 0 0]基本上(至少我)并不关心，只要1可用，某个房间是否可用：因此，在这种情况下，an和per索引可能是可用性的答案(请记住：0可用)：
1室：1 0 0第2室：0 0 0客房结果：1 0 0和0 0 0=0 0 0
所以，一个和可以判断的第一个小时是否仍然可用。
如果您现在将它与一个学生结合起来使用可用的时间(本例中也只有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)时效果最好。
Stack Overflow用户
发布于 2018-02-12 13:30:37
约束满足问题解决了资源分配问题。很可能解决办法是NP-完全。
两个问题
至少有两个问题要解决：
- 是否有可能找到学生-团体-班级的组合，以适应可用的时间房间？
- 从可能的组合来看，其中一个比另一个更理想吗？是否有可能在合理的时间内确定哪种组合是最佳的？
设定合理限度
首先，很容易对可入学的学生人数设置一个绝对上限。理论最大入学人数等于
rooms * hours * students/room / hours/student
例如，如果你有100个房间，每个房间有5个小时，每个房间可以容纳8个学生，每个学生需要学习5个小时：
100 * 5 * 8 / 5 = 800 students
然而，考虑到随机收集的不同年级和能力水平的学生，你不太可能能够容纳这个理论上的最大值。
如果我们来自另一端，假设你有500个课时(100个房间)。*5小时)，然后你知道你总是可以容纳至少100名学生(每个房间有1名学生)。*5小时)。诀窍是找出一个合理的上限，在100到800之间，这使得这个问题可以在合理的时间内解决。
为了合理地猜测这个上限应该是什么，似乎谨慎地考虑对群体形成的限制。
分组约束
学生分为两类：
- 能力水平：哑巴，正常，聪明(D，N，C)
- 职等：9、10、11、12
这意味着你有12类学生：9d，9N，9C，10D，10n，10C，...
只有其中的一些类别是相互兼容的分组，这给您提供了有限的潜在组类型。假设你只有12名学生，12种类型中每一种都有一种，理论上最大的组类型数(假设任何学生类型都可以与任何其他类型配对)将是12!/4! = 19,958,400但是，考虑到这些限制因素，实际可能的组类型数量将更少。事实上，我认为我们可以安全地将分组类型减少到四种，每种类型都是由一些类型的学生组合而成的：
- 9d，9N，10D，10n
- 9N，9C，10N，10C
- 11d，11N，12D，12N
- 11N，11C，12N，12C
这里有一些明显的重叠，因为“正常”学生可以属于多个群体类型。但我们终于开始获得一些对团队形成有用的信息：
首先，将限制最严格的类别中的学生分配给组。然后将学生加入限制较少的群体中。
换句话说，“哑”和“聪明”的学生只能属于四种类型中的一种，所以他们应该首先被分配。因此，算法看起来可能如下：
- 每门课程
- 选择9/10或11/12年级的所有聪明/愚蠢的学生。
- 尽可能多地与这类学生一起创建8组。
- 用“普通”学生填补剩余组的空白槽。
- 将其余的“正常”学生分成8组。
这将导致分组，并尽可能减少组数。这方面的问题是，只有成千上万(也许是数百万)的其他分组是可能的。这个特殊的集团很不可能是正确的。我们仍然可以在不同的小组交换学生，但我们需要一个聪明的方法来做到这一点。
调度约束
现在已将学生分配到了组，可以开始将这些组放入教室/时段。 这里主要的约束是你不能将两个小组安排在一个时间段内，这个时间段要求学生同时在一个以上的地方。
我们再来从一个更简单的例子开始，我们可以在我们的脑海中真实地想象。 我们假设只有四门课程，艺术，音乐，数学和科学，将在4个教室的两个时间段内教授。 我们将有8组2名学生，并指出每个学生将参加两组课，因为每个学生都参加两门课。 为了简单起见，我们假设所有的学生都在同一类别中，例如 9N，所以可以在组之间交换而没有问题。 由字母A-H和组代表的学生由两个字母表示，例如， AB组包含学生A和B.假设系统生成的第一个时间表如下所示：
Art Music Math Science
Time_1 AB CD EF AH
Time_2 CD EF GH GB每门课程都会教两次，我们看到所有的小组都由一组有效的学生组成，但我们看到学生A和G都是双重预订的：A在Time_1有两门课，G在Time_2有两门课。 简单的做法是在科学时代交换A和G：
Art Music Math Science
Time_1 AB CD EF GH
Time_2 CD EF GH AB但也有更复杂的解决方案，涉及到调动许多人并改变所有群体，例如：
Art Music Math Science
Time_1 AC ED GF BH
Time_2 BD FC HE AG显然，其中的一个比另一个更有效率，但是计算机没有简单的方法来区分。 作为人类，我们可以在这个例子中比较快速地看到解决方案，但是想象几十个课程，每个课程有8个学生，你会发现这个过程变得如此之快。 显然，我们不希望用强力检查所有可能的排列来找到解决方案。
当然，另一种解决方案就是增加更多时隙，例如：
Art Music Math Science
Time_1 AB CD EF GH
Time_2 CD EF H B
Time_3 G A从计算的角度来看，这样做更简单快捷，但显然不会优化课堂空间和教师的时间，当然，如果所有可能的时间段都已经有了课程，那当然是不可能的。
对这件事很聪明
让我们退一步，想想我们对整个系统的了解。以下是我们所知道的一些事情：
- 相似的学生可能会选择类似的课程。
- 如果你有一组学生，他们都在上同一组课，那么就很容易安排他们的课程表。
例如，如果我们有4名学生(2组2人)都想参加同一组课程，那么很容易将这些组组合成一个矩阵：
Class_1 Class_2
Time_1 AB CD
Time_2 CD AB这样做，我们可以事先有信心，不会有冲突。这是直截了当的，规模很好，并使我们的第二个洞察力。
首先，创建一组学生，他们都在学习同一套课程。
考虑到这一点，我们可以将上面的算法更改为：
- 对于每一个限制类别中的学生(即哑巴/聪明)
- 循环遍历该类别中的所有其他学生，并从所有选择同一组班级的学生中创建组。
- 如果有一个组剩下的是<8名学生，请用选择同一组课程的非限制性组(正常)中的学生填充该组。
- 当学生被添加到组中时，将它们从总池中移除。
- 对所有受限制类别的学生重复这一步骤。
- 用网格矩阵的方式调度所有这些学生。
- 对正常类别中的其余学生重复此操作。
幸运的是，当这件事完成的时候，你会有一小部分学生，他们有一组更具挑战性的时间表要求。
接下来怎么办？
从现在开始，最聪明的事情似乎取决于有多少学生被留在计划外的游泳池里。可能性包括：
- 重复上述策略，但将学生分成四班五班。
- 根据其余池中请求的课程创建需要创建的课程列表。然后循环每一课程，并尽可能多地向每个课程中添加学生，从限制更严格的类别的学生开始，并在正常学生中填写。
- 如果数量足够小，只需手动创建任何剩余的课程。
在某些时候，我认为您会发现，只需手动为任何“怪胎”分配日程就更容易了。
你可能会考虑想出一种方法，让同年级学生分组的权重稍微高一点。
代码示例
下面是一些可能有用的代码片段。注意，在重读你的问题时我才意识到knowledge_level是按每门课程分配的，而不是全部分配给学生。我会设法调整一下以解释这一点。
// function to determine whether two students have selected the same classes
function studentsSelectedSameClasses($s1, $s2) {
// returns true if students selected the same set of classes
// returns false other wise
// this takes into account knowledge_level and will consider
// a class the same if the knowledge_levels are compatible
}
// create arrays of unscheduled students, i.e. not yet in groups, by grade
// 9th/10th and 11th/12th together since they can be in the same classes
$unscheduled["9_10"] = Student::find()->whereIn('class', [9,10])->all();
$unscheduled["11_G"] = Student::find()->whereIn('class', [11,G])->all();
// copy this array into another array from which we'll remove
// students as they get put into groups
$pool = $unscheduled;
// loop through unscheduled; try to match on course selections
foreach($unscheduled as $grade => $students) {
foreach($students as $i => $student) {
// make sure they are still in the pool, i.e. not already in a group
if(!in_array($student, $pool[$grade]) continue;
// now loop through other students
foreach($pool[$grade] as $j => $potential_classmate) {
if(studentsSelectedSameClasses($student,$potential_classmate)){
// create new groups for each class if necessary
// add both students to the groups if necessary
// remove them from the $pool
// if the group size reaches 8 go on to the next unscheduled
}
}
}
}
// At this point $pool may not be empty, but you should have a bunch of
// easily scheduled groups and a much smaller pool to resolveStack Overflow用户
发布于 2018-02-12 14:59:40
我可以按照所提出的收缩的不足，这让我想到线性问题/编程也需要精确的约束来计算最佳值。而且，我们可以将矩阵计算减半，首先除以2，然后搜索下半部分或上半部分的结果，因为它们不能同时在两者中。但是没有什么可以削减的，所以我认为它更合理地假设在这里必须有一种真实的生活，或者它不会起作用，或者快速加起来就是我的名词
所以我现在提出这种方法是有逻辑的：从介绍课程到考试课程是线性的。因此，没有采取介绍课程的学生可能会再次采用它，因为它只是愚蠢的（爱因斯坦等人）。所以每个参加过数学的学生都可以被排除在外。因此，如果我们采用数学1到5的渐进方法，并且规定所有课程都必须参加，当课程水平与学生水平相差不超过-2时，该水平等于给定学生以线性方式参加的课程，然后所有参加过课程1的学生都可以被排除在外。因此，对于数学2只有有水平的学生或课程出席，0和1可以参加。对于数学3级1或2级的学生可以参加。因此，如果我们开始创建可以参加任何课程的最大群体，并开始削减聪明和愚蠢，以节省时间削减毫无意义的选项，因为4级学生不能像0级一样参加相同的数学课程，一个学生？
我正在为这个图表工作，但是现在看起来更像是我邻居的车库，所以我不知道该怎么做。
https://stackoverflow.com/questions/-100004148
复制相似问题