r - 用于工作项目调度和优化的遗传算法或模拟退火

Question

我的任务是改进我公司的基本调度流程，并使其更加数据驱动、高效和精简。就目前而言，我们目前只是每月汇总项目所需的总小时数，并将此值与可能的工作时间 * 员 worker 数进行比较。我们比较这些结果并确定是否需要提供更多帮助。

我想在此过程中更加精确，因此我开始研究使用稳定婚姻问题等资源进行优化。最终，我从 Job-Shop 问题中偶然发现了遗传算法和模拟退火，因为我相信我的问题最终会比多婚婚姻问题复杂一点，但我可能是错的。

我的基本问题是设置为具有许多限制条件的优化任务。

worker :John、Jane、Dale等
他们也都可以担任多个角色(约翰可以是经理或劳工)

项目:项目A、项目B、项目C等
项目有开始日期和结束日期。
理想情况下，我想限制项目的不同阶段的子开始和结束日期，但总的开始/结束日期就可以了。这些子日期包括每种角色类型所需的小时数(经理 8 小时，劳工 20 小时等)

工时:每位员工不超过 45 小时。

我的问题是我真的需要使用 GA 或模拟退火还是有更简单的过程。此外，我还没有在 R 中找到任何这两个过程的伪代码。

感谢所有帮助，如果需要更多详细信息，我很乐意为任何人澄清!

Answer 1

您可以尝试将其建模为混合整数程序，例如使用 lpSolve 程序包。您将有像 john_manager_project_A_week_1 这样的变量(约翰在第 1 周作为经理在项目 A 上工作的小时数)，求解器要确定这些变量，以及像这样的线性约束

john_manager_project_A_week_1 + john_manager_project_B_week_1 + ... <= 45
john_manager_project_A_week_1 + jane_manager_project_A_week_1 + ... >= 8

这个框架似乎有些局限，但通过一些建模技巧，您还可以表达条件，例如“约翰在第 1 周不能同时担任项目 A 的经理和 worker ”。

解决这些问题是 NP-hard，但求解器往往非常好，如果你只有几十个人、项目和时间段，它应该是可以解决的。您甚至可以有一个要优化的线性目标函数(例如，将上面的“45”替换为 max_work_hours，并将其最小化)。