这是最优调度任务NPC吗？

Question

我自愿写了一个程序来安排家长和老师的会议。校长希望家长选择三次可能的约会时间来拜访他们的英语和数学老师(同时)。

一旦所有的家长都选择了三次约会，我就应该想出一种最佳的方法来安排家长和老师的会议，以便尽可能多的家长可以和两位老师见面。

(如果有时间冲突，数学老师不能出席会议，家长只会见英语老师)

我对NP类型的问题不太了解，但是当我听到“最优”和“计划”这个词时，我开始怀疑……

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

• 500个父母
• 15名英语教师
• 5名数学教师
• 25次约会

在你奶奶的电脑上，几秒钟、几分钟或几小时就能正确地解决这个问题吗？

Answer 1

我对你的问题有一个部分的答案和一个模拟，可以让我尝试不同的情况。以下是我的工作(但却是可变的)假设：

• 参数与您列出的参数相同
• 家长对会话时间的选择遵循幂律(本福德氏分布)，因为它模拟了期望的偏好不均匀性。
• 根据具体情况，大约有20位家长是“不妥协”的，只能在一次会议上来。
• 每个英语老师都有一个，也只有一个对应的数学老师，因为他们的相关性被认为是很高的，但我不知道有多高。该代码可以处理0到1之间的任何相关系数。
• 产生看似可信的模拟父母的整个过程(“史密斯”)“‘atkins”)、老师、时间选择和满意的结果在一台中间机器(5300 BogoMIPS)上花费了300毫秒。

我的第二顺序优化甚至没有启动，因为第一关允许每个家长的第一选择在一个会话中容纳最多11个家长。这一结果对于那些必须参加大约一半时间间隔、平均家长组为3的教师来说是不太理想的。

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