algorithm - 资源分配任务

Question

我正在研究解决此类问题的可能性:

我有任务，描述如下:

1. 允许的天数(何时可以完成)
2. 执行此操作所需的技能
3. 执行此操作所需的工具
4. 任务持续时间(以小时为单位)
5. 任务的利润价格
6. 如果未在最后允许的一天完成，则每周没收。

例如:在 8 月 1 日至 15 日(允许的天数)之间由电工(技能)用万用表(仪器)修理熨斗 2 小时(任务持续时间)。价格是 10 美元(利润)，但如果在 8 月 15 日之后完成，8 月 15 日之后的每一天将被罚款 1 美元。

我还有 Worker 的资源，描述如下:

1. 天
2. 技能
3. 仪器
4. 当天的表现(可能的工作小时数)

例如:一位带万用表的电工可以在 8 月 2 日工作 3 小时。

需要将Tasks和Worker的进行匹配。 worker 的资源必须具备任务所需的所有技能和工具。我想最大化收入(盈利-亏损)。

不幸的是，这个问题似乎无法引出线性规划问题。 (我错了吗？)那么你会建议我研究什么算法来解决这个问题？

Answer 1

抱歉，如果您确实想要利润最大化并且想要有所不同，那么我不敢苟同，那么您可以将问题表述为混合整数问题(线性规划的一个子集，其中一些变量是整数，可能是二进制)。在你的例子中 To fix an iron by electrician (skill) with multi-meter(instrument) between 1 and 15 august (allowed days) for 2 hours (task's duration). The price is $10 (profit), but if it is done after 15 august $1 forfeit will be payed for every day after 15 august.您可以为 8 月 1 日至 15 日期间分配给修理熨斗的电工时间表的每个小时创建二进制变量，这意味着电工是否会花费该小时来修理熨斗。然后你只需要两个这样的二进制变量是一个，其余为零(实际上是两个小时)。

PS:我 100% 确信这可以表述为 MIP 问题(我在该领域有 9 年以上的经验)，根据你的问题，你正在征求有关此问题的建议。