blocks|key|2617174|text|这是一个著名的计算机科学问题(+考试调度问题)，它被称为NP-硬。你可能一个周末都解决不了这个问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2617175|entityMap|0|LINK|mutability|MUTABLE|url|http://scholar.google.com/scholar?q=exam%2Bscheduling%2Bproblem&hl=en&btnG=Search|1|http://en.wikipedia.org/wiki/NP-hard^0|G|6|0|S|4|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

This is a famous computer science problem (the <a href="http://scholar.google.com/scholar?q=exam+scheduling+problem&amp;hl=en&amp;btnG=Search" rel="noreferrer">exam scheduling problem</a>) which is known to be <a href="http://en.wikipedia.org/wiki/NP-hard" rel="noreferrer">NP-hard</a>. You might not be able to solve it over a weekend.

blocks|key|2617125|text|我知道这是个离题的话题，但我的大学只是把考试安排在与上课时间相匹配的几个环节上。所以，每个在下午1点20分上MWF课的人，都是在下午1点15点参加考试的。因为你不能同时上两门课，所以不可能有考试冲突。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2617126|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I know this is off-topic for SO, but my university simply scheduled the exams in blocks that matched the class times. So, everyone who had a class MWF at 1:20pm was in an exam on the 15th at 1:00pm. Since you can't take two classes at the same time, it was impossible to have exam conflicts.

blocks|key|2617095|text|这是一个约束满意问题的例子，它是一类困难的问题。他们中的一些人在NP班。大型商业软件包的存在是为了解决这样的问题(如CPLEX)+--一般来说，它们使用的是一些数学和许多启发式方法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2617096|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

This is an example of a constraint satisfaction problem, which is a difficult class of problems. Some of them are in the class NP. Large commercial software packages exist for trying to solve problems like these (eg CPLEX) - and in general, they use some mathematics and lots of heuristics.

blocks|key|2617111|text|我在我的主人期间使用了禁忌搜索。这个想法并不复杂：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2617112|从一个可能的解决方案开始(任何人)，然后对其进行测试(例如，如果一个学生同时进行两次考试，则给-1000分)。|ordered-list-item|2617113|改变这个解决方案，只需更改几个任务，并重新计算思量。|2617114|如果2优于1，则重复以2开头作为根解决方案。|2617115|如果您被阻止，您可以通过对初始解决方案进行重要更改来“访问”其他解决方案。|2617116|entityMap|0|LINK|mutability|MUTABLE|url|http://www.cs.sandia.gov/opt/survey/ts.html^0|B|4|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@$A|V|B|W|1|X]]|C|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|C|$]]|$1|G|3|H|5|F|7|Z|8|@]|9|@]|C|$]]|$1|I|3|J|5|F|7|10|8|@]|9|@]|C|$]]|$1|K|3|L|5|6|7|11|8|@]|9|@]|C|$]]|$1|M|3|-4|5|6|7|12|8|@]|9|@]|C|$]]]|N|$O|$5|P|Q|R|C|$S|T]]]]

I used the <a href="http://www.cs.sandia.gov/opt/survey/ts.html" rel="nofollow noreferrer">tabu search</a> during my master. The idea is not too complicated:

<ol>
<li>start from one possible solution (anyone) and pounder the it (e.g. give -1000 points if one student has two exams at the same time)</li>
<li>change that solution by just changing a few assignments and recalculate the ponderation</li>
<li>if 2. is better than 1. and repeat starting with 2. as the root solution</li>
</ol>

if you're blocked, you can "visit" other solutions by making important changes to the initial solution.

blocks|key|1076915|text|它是昂贵的，但我看到CPLEX用于类似类型的问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1076916|entityMap|0|LINK|mutability|MUTABLE|url|http://www.ilog.com/products/cplex/^0|A|5|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

It's expensive, but I've seen <a href="http://www.ilog.com/products/cplex/" rel="nofollow noreferrer">CPLEX</a> used for similar types of problems.

blocks|key|1092392|text|实际上，这个问题可能比这更普遍一些。例如，在我的学校，考试是按课时安排的--也就是说，所有通常在学期同一时间开会的班级，都在考试周的某一段时间进行考试(但不一定与定期班会的时间相同)。因此，冲突通常不存在，因为由于明显的原因，学生不会在相同的会议时间上两节课，因此不会同时进行两次考试。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1092393|但是，这意味着您仍然需要调度类，这样它们就不会发生冲突。:)|1092394|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

The problem can actually be a bit more general than that. For instance, at my school, exams are scheduled by when the class is scheduled - i.e. all classes which meet at the same time normally during the semester, have an exam scheduled in a certain block of the exam week (not necessarily the same time as the regular class meeting, however). Thus, conflicts generally don't exist since students wouldn't be attending two classes in the same meeting time for obvious reasons, and thus wouldn't have two exams at the same time.

However, this means that then you still need to schedule classes so that they don't conflict. :)

blocks|key|1077048|text|当我在大学高年级的时候，我们在我们的人工智能课上做了一个类似这样的最后一个项目。我们编写了一个(勉强)工作系统，以便在适当的时候安排建筑物的班次。某些规则不能被违反:如果教授。需要一个多媒体教室，他有一个。如果它是一个CS类，那么它不应该安排在艺术建筑。教授上课间隔不得超过2小时等。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1077049|我们使用了遗传算法。|1077050|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

When I was a senior in college, we did a final project in our AI class similar to this. We wrote a (barely) working system to schedule classes in buildings at appropriate times. Certain rules could not be violated: if the prof. needed a multimedia classroom, he got one. If it was a CS class, then it shouldn't be scheduled in the Art building. Profs shoulnd't have more than 2 hours between a class, etc.

We used a genetic algorithm.

blocks|key|1076405|text|一些事情可以使问题变得更简单。通过观察参加同一组考试的人，你可能会把“计划单元”的数量从数万个减少到几百个。如果你有300人都坐在“计算机科学导论”和“CS学生数学”中，你可以把所有300人都排成一个单元，因为他们都有相同的限制，你(可能)不希望在多个时段进行相同的考试。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1076406|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

A few things to make the problem simpler. You can probably shrink the number of "units to schedule" down from tens of thousands to a few hundred, by looking at people who are sitting the same set of exams. If you have 300 people who all are sitting "Introduction to Computer Science" and "Maths for CS students", you can schedule all 300 as a single unit, because they will all have the same constraints and you (probably) do not want identical exams to be given in multiple slots.

blocks|key|1076433|text|滴水规划师有一个考试调度示例(称为考试，请参阅下载和参考手册)。该问题是在ITC2007比赛项目1中指定的。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1076434|entityMap|0|LINK|mutability|MUTABLE|url|http://www.jboss.org/drools/drools-planner#EducationalTimetabling|1|http://www.cs.qub.ac.uk/itc2007/examtrack/exam_track_index.htm^0|0|5|0|11|C|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

<a href="http://www.jboss.org/drools/drools-planner#EducationalTimetabling" rel="nofollow">Drools Planner</a> has an exam scheduling example (called examination, see download and reference manual). The problem is specified in <a href="http://www.cs.qub.ac.uk/itc2007/examtrack/exam_track_index.htm" rel="nofollow">the ITC2007 competition track 1</a>.

blocks|key|1077137|text|这是图着色问题的一个应用程序。这个问题可以表示为一个图，其中每个顶点都是一个过程，两个顶点之间的一个边意味着两个课程中都有一个普通的学生。这是一个图着色问题，其中最小时隙数等于图的顶点着色所需的最小颜色数，这样就没有两个相邻的顶点共享相同的颜色。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1077138|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Graph_coloring^0|2|5|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

This is an application of the <a href="http://en.wikipedia.org/wiki/Graph_coloring" rel="nofollow">graph coloring problem</a>. This problem can be represented as a graph where every vertex is a course and an edge between two vertices mean there is a common student enrolled in both courses. So this is a graph coloring problem where minimum number of time slots is equal to the minimum number of color required for coloring the vertices of the graph such way that no two adjacent vertices share the same color.

I'm bored, and this problem just haunted me again. Back at university, I used to always wonder how they schedule exams. The ability to schedule 10k student to do exams in 2 weeks and guarantee that no student will have an exam in two consecutive periods. I'm assuming some form of heuristics be applied.

I'm bored tonight, and if you give me the right tools, I'll work on it tonight and up to the weekend

cheers,
dassouki

EDIT 1:
I guess the assumption would be that all we know is the following:

<ol>
<li>Number of students and the courses that they're each enrolled in</li>
<li>Number of exam period spots</li>
</ol>

Scheduling algorithm/problem

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

我很无聊，这个问题又一次困扰着我。回到大学时，我总是想知道他们是如何安排考试的。有能力安排10k名学生在两周内进行考试，并保证任何学生在两周内都不会有考试。我假设采用某种形式的启发式方法。我今晚很无聊，如果你给我合适的工具，我今晚就会做，直到周末干杯，达苏基编辑1: --我想我们所知道的假设是：学生人数和他们每个人注册的课程考试期间点数

问调度算法/问题
EN

回答 10

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问调度算法/问题EN

回答 10

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问调度算法/问题
EN