algorithm - 最佳调度工作

Question

我一直在研究这个问题，但似乎找不到正确的答案。有人可以帮我解决这个问题吗？

我们有 N 个工作 [1,..,N]。完成一份工作 i，我们将获得薪水 S(i) >= 0，并扣除 D(i) >= 0 这对过去的每一天都加起来。

我们需要 T(i) 天来完成作业 i。假设工作 i 在 d 日完成，我们将获得 S(i) - d.D(i) 的奖励。如果 d 太大，则奖励可能为负。我们可以在此过程中切换工作并按任何顺序处理工作，这意味着如果我们在第 1 天开始需要 5 天的工作 1，我们就不必连续 5 天花在工作 1 上。

我们如何确定工作的最佳时间表，以便我们能够完成所有工作并获得最高薪水？

Answer 1

我认为夏皮罗是对的。您需要为每项任务确定适当的加权成本公式。它必须考虑剩余天数、每天的扣除额，可能还有总扣除额。

获得加权成本后，您可以按加权成本对任务列表进行排序，并对列表中的第一项任务执行一天的工作(如果未完成，则应该是成本最高的任务)。然后重新计算一天过去后所有任务的加权成本，对列表进行排序，并重复直到完成所有任务。

通常，当您在现实世界中优化计划时，就是这种方法。弄清楚应该先处理哪个任务，对其进行一些处理，然后重新计算以查看是否应该切换任务或继续处理当前任务。