相关疑难解决方法(0)

我正在编写一个带有困难编程问题的调度程序.有几个事件,每个事件都有多个会议时间.我需要找到会议时间的安排,以便每个时间表包含任何给定事件一次,使用每个事件的多个会议时间之一.

显然我可以使用蛮力,但这很少是最好的解决方案.我猜这是一个相对基本的计算机科学问题,一旦我开始学习计算机科学课程,我就会学到这些问题.与此同时,我更喜欢任何我可以阅读的链接,甚至只是我可以谷歌的名字.

我正在开发一种应用程序,可以最佳地为医院的护士分配班次.我认为这是一个带离散变量的线性规划问题,因此可能是NP难的:

• 对于每一天,每位护士(约15-20岁)都会被分配轮班
• 有少量(约6个)不同的班次
• 有相当多的约束和优化标准,无论是关于一天,还是关于一个emplyoee,例如:
  • 每天必须为每个轮班分配最少数量的人员
  • 有些班次重叠,所以如果有人做中间班,可以让一个人在早班换一个人
  • 有些人更喜欢提前班次,有些人更喜欢延迟班次,但需要最少的换班才能获得更高的轮班工资.
  • 不允许一个人一天工作到第二天工作到第二天早班(由于最短的休息时间规定)
  • 满足指定的工作周长度(不同的人不同)
  • ...

因此,基本上存在大量(约20*30 = 600)变量,每个变量可以采用少量离散值.

目前,我的计划是使用修改后的Min-conflicts算法

• 从随机分配开始
• 每个人和每一天都有健身功能
• 选择具有最差健身值的人或日
• 随机选择该日/人的任务之一并将其设置为导致最佳适合度值的值
• 重复直到达到最大迭代次数或者找不到所选日期/人的改进

有更好的想法吗？我有点担心它会陷入局部最佳状态.我应该使用某种形式的模拟退火吗？或者不仅考虑一次改变一个变量,而且特别考虑两个人之间的转换(当前手动算法中的主要部分)？我想避免将算法定制到当前约束,因为那些可能会改变.

编辑:没有必要找到严格的最佳解决方案; 名单目前是手工完成的,我很确定结果在大多数时候都是非常不理想的 - 不应该难以击败.短期调整和手动覆盖也一定是必要的,但我不认为这是一个问题; 将过去和手动分配标记为"已修复"实际上应该通过减少解决方案空间来简化任务.

我正在研究一个简单的应用程序,它将为学校生成时间表(每日计划).我已经阅读了算法的基础知识,但对于从哪里开始感到困惑.

问题:
考虑到很多限制,将教师分配到课堂上:
1)学科
2)教师的专业知识
3)不超过2个班级等等

不言而喻,应该没有重叠.基本上我需要将N名教师分配到每天有固定工作时数的M班(8).

输入:
1)班级总数
2)教师及其专业知识
3)每个班级的科目/课程
4)每班每天的讲座数量
5)其他灵活的约束条件,如教师每天的最小/最大工作时间,每位教师每周的总工作时间等

我的问题:
1)将它视为具有多个约束的赋值问题是否正确？
2)我应该使用哪种算法？(匈牙利算法？)
3)我应该从一开始就获得整套约束,然后生成表,还是应该在中间步骤中完成？

我是学习/实现算法的初学者,所以任何指导我正确方向的帮助都值得赞赏!谢谢.

是的,在SO上有很多这样的问题.我看到遗传算法是最常见的答案.

制定时间表和时间表

用于创建学校时间表的算法

但是,我担心GA的这些特征

• 程序的终止条件很难定义
• 不能轻易逃脱局部极大值

我希望该程序能够被用户轻松推向相互冲突的标准和不可能的解决方案 .

因此,我想要一种方法

• 是决定性的 - 保证达到接近最佳状态或报告算法无法达成解决方案
• 可以采取硬(不可侵犯)限制和软限制
• 优雅地接受用户输入约束; 如果用户输入不起作用,可以将其添加到代码中而不会破坏它

有100000个尽可能详尽的时间表.

我四处搜索,发现像模拟退火这样的元启发式算法是一个很好的选择.那么动态编程算法呢？

对于这样的数据集,蛮力方法是否合适？

什么是符合标准的好算法？