这就是最优调度任务NPC吗？

Question

我自愿编写一个程序来安排家​​长会。校长希望家长选择 3 个可能的约会时间（同时）拜访他们的英语和数学老师。

一旦所有家长都选择了 3 个日期时间，我就应该找出安排家长教师会议的最佳方式，以便最多数量的家长可以与两位老师会面。

（如果时间冲突，数学老师不能参加会议，家长只会和英语老师见面）

我对NP类型的问题了解不多，但是当我听到“最优”这个词时“安排”在一起，我开始怀疑......

我已经告诉校长我不能这样做，但我想知道它是否是 NP 完全的。如果是的话，假设有：

• 500 位家长
• 15 名英语老师
• 5 名数学老师
• 25 个可供选择的日期时间

可以在你奶奶的电脑上在几秒钟、几分钟或几小时内正确解决这个问题吗？

Answer 1

好吧，我对你的问题有部分答案，并且有一个模拟，可以让我尝试不同的场景。以下是我的工作（但可变）假设：

• 参数如您列出的那样
• 家长对会议时间的选择遵循幂律（本福德分布），因为此模型模拟了预期的偏好不均匀性。
• 根据运行情况，大约有 20 位家长“不妥协”，只能参加一次会议。
• 每个英语老师都有一位且只有一位对应的数学老师，因为他们的相关性被认为很高，但我不知道有多高。该代码可以处理从 0 到 1 的任何相关系数。
• 从生成合理的模拟父母（“史密斯”..“阿特金斯”）、教师、时间选择到令人满意的结果，整个过程在中型机器上花费了 300 毫秒（5300 BogoMIPS）。

我的第二阶优化甚至没有启动，因为第一次允许每个家长的第一选择在一次会话中最多容纳 11 名家长。对于必须参加大约一半时间段且平均家长人数约为 3 人的教师来说，这一结果并不是最优的。

如果有任何表达的兴趣，我可以提供代码，因为它大约有 125 行。