2

我有一个任务 Z,只有在任务 X 或任务 Y 完成后才能完成。还:

% 任务 Z 的长度取决于完成 X 或 Y 中的哪一个:

% 如果任务 X 完成,任务 Z 需要 4 小时

% 如果任务 Y 完成,任务 Z 需要 7 小时

% 任务 X 需要 5 小时才能完成

% 任务 Y 需要 3 小时才能完成

% 任务 X 和任务 Y 是互斥的:你不能两者都做(但这可能无关紧要,因为这永远不会是最佳的)

问题:我能以最快的速度完成任务 Z 是什么?

在这种情况下,答案显然是 9 小时(X 然后 Z),但我真正的问题有很多这样的情况。

taskjuggler 可以帮助我吗?可以换个工具吗?补充说明:

% 这是“旅行推销员问题”的扩展,因此是 NP-hard。我会对一个好的但非最佳的解决方案感到满意。

% 在实际问题中,一些任务是具有非负值的“里程碑”。我的目标是最大化这些值的总和。不过,我很乐意先解决最短时间问题。此外,所有里程碑的值可能相同,从而简化了问题。

注意:由于 Mathematica 具有快速(但非最佳)解决 TravelingSalesman 问题的功能,因此将其添加为标签。

4

1 回答 1

0

您应该研究动态编程。基本上,您将重用子问题的解决方案来为您的整个问题构建解决方案。您可以在 Mathematica 或大多数任何编程语言中执行此操作。

于 2010-09-01T12:04:30.643 回答