algorithm - 优化任务执行顺序

Question

有n个任务要执行（彼此独立）。每个任务都使用一个资源列表（预先知道），这些资源的获取成本很高，可以用于多个任务（每个任务都有不同的列表，但存在重叠）。系统按顺序处理任务，并使用固定大小M的缓存作为资源缓存只保留最近使用的资源。
问题：如何优化任务的执行顺序，使我们最大限度地重用资源（即，我们最大限度地减少所需的次数来获取资源）给定的大小的缓存M？缓存的最佳大小是多少，即最小的m，这样我们最多一次创建每个资源？
这个问题的指数解相当微不足道，所以我要么是多项式解，要么是一个好的近似。

Answer 1

为了清楚起见，对问题重新措辞。为了解决这个问题：
问题是一组可以按任意顺序顺序执行的独立任务。
任务需要按特定顺序使用的资源数组。
缓存适合m个资源的有序集，并将其项保存在最近使用的基础上。
其思想是以尽可能保持缓存稳定的顺序执行任务，因为打开一个文件指针等代价高昂。
我假设确定任务顺序所需的时间无关紧要（因为它比打开文件指针快）或者不相关（因为顺序随后被缓存在某个地方）。
我希望这些建议看起来是合理的：
缓存的填充顺序很重要因为M=2和一个使用资源[A, B, A, A, C]的任务在一次交换后（如果从[A, C]开始）将离开缓存保持[A, B]，而另一个使用[C, B, A, B, C]的任务将使用两次内部交换从[B, C]离开缓存保持[B, C]。
有些任务比其他任务更昂贵，我们可以将它们分为两组：便宜的任务是那些资源数量为m或更少的任务；昂贵的任务是那些使用更多资源的任务，可能的顺序是，缓存在完成时已经更改了好几次。
对于每个任务，第一眼就注意到使用的前M个资源；最后使用的M个资源；以及当需要超过M个资源时，这两个资源的差异有多大是合理的尽管事实上有一点比眼前更多。
如果您有任何昂贵的任务，并且实际上可以在缓存更改的中间步骤中将它们置于休眠状态，则可以进行进一步的优化。
直观地说，我们希望以这样的方式对任务进行排序：下一个任务的前m个资源与当前任务的最后m个资源尽可能接近：
用m个资源初始化缓存。
如果你能运行便宜的任务，那么就这样做。
如果你能运行一个昂贵的任务，这样做并转到2。
如果只更改一个资源就可以运行任务，请执行此操作并转到2。
重复步骤4，进行两次更改、三次更改等。
理想情况下，第3步应该选择与第4-5步相同的任务，这会让我们暂时进入第二个问题，因为这会产生有趣的见解。
为了避免昂贵的任务，最小的缓存大小直观地等于在单个任务中使用的最大资源数，即为了避免步骤3和随机状态，它可以使您进入。
然而，避免多次创建资源的最佳缓存大小取决于初始状态（步骤1）和我们选择的排列（步骤3-4）简单地说，在最佳情况下，两者是相等的，最佳缓存大小最多等于资源数量这种病理病例的一个例子是：[[A, B], [B, C], [C, A]]。
假设您满足最小缓存大小，我们可以使用蛮力来找到最佳排列并确定最佳缓存大小；步骤3总是被跳过，因此成本为零；对于每个候选排列，我们为运行步骤1（=M）和步骤4-5（=1/资源交换）分配成本计算总成本——如果我们已经找到了更好的排列，就中断这个过程。
如果不满足最小缓存大小的要求，我们将修改该过程，因为我们还需要考虑步骤3中涉及的成本（运行任务时每个资源交换1个资源：交换发生的顺序计数，因此我们无法从初始和最终缓存状态中了解任何信息）。
在那个阶段，我们应该能够用最小的得分计算排列的集合，并选择提供最低最佳缓存大小的排列。