我正在尝试为特定域中贪婪调度程序的性能创建一个分析模型。

我已经创建了一个初步模型，但我认为这对其他人来说非常混乱，并且想知道是否有人可以提供反馈。

我的问题域如下。贪心调度器有能力调度 c 个任务，并会选择 c 个最高回报的任务。任务从到达模式 A 动态在线到达——即对于时间范围内的每个时间单位 X 任务将到达，其中 X 是任意随机变量。任务详细信息均来自任意预定义分布。任务详细信息包括，奖励、服务前的最长等待时间（即，如果一个任务在 m 个时间单位后没有服务，则该任务将失败）和持续时间。我将相应的分布标记为 R 表示奖励，M 表示最长等待时间，D 表示持续时间。

我知道这个问题非常大，所以我想专注于这个更大问题的一个小部分。

考虑一个容量为 c 且当前没有任务组合为 T 的任务的贪心代理，其中 T 的大小大于 c 并且 T 的任务奖励代表 R 奖励分布。

我的问题是从 T 中选择的 c 个任务的预期奖励（甚至更好的奖励分配）应该是什么。这类似于 k 阶统计问题；但是，由于我对统计的基本/有限理解，我无法将此问题格式化为 k 阶统计问题。（我学习计算机科学，只知道基本的统计分析）。

我的方法如下；但是，我觉得它可以改进。在我的方法中，我尝试计算最高奖励任务的最低奖励：

如果调度器可以从 T 中选择 c 个任务且 c < |T|，则调度器将选择奖励最高的 c 个任务。由于 T 的任务奖励代表 R，单个任务的预期奖励将是上层 c / |T| 的预期奖励 R 分布的一部分。

为了计算奖励分配的期望值，我们需要

integral from x= -infinity to x=+infinity of P(R=x)*x

类似地，为了计算最高 c 奖励分布的期望值，我们取

integral from x = Y to x = +infinity of P(R=x)*x 其中 y 是最高奖励任务的奖励中的最低值。

计算上 c/ |T| R 分布的一部分，我让最高奖励任务的最低奖励为 Y，因此 c / |T| = 1 - CDF(Y)，其中 CDF 是应用于奖励分布的累积分布函数。

c / |T| = 1 - CDF(Y) states that:

可调度任务占总任务的比例等于奖励分配的上半部分最高奖励任务的比例。

通过求解 Y，我们得到

Y = inverse_CDF(1 - c/|T|)

然后，我们可以更早地将最高奖励任务的奖励代入我们的期望值方程，然后最高 c 个奖励任务的期望值是从 x = Y 到 x = + P(R=x)*x 的无穷大的积分。

任何关于我如何提高清晰度或改进我的分析方程的反馈将不胜感激，或者如果有更标准/正确的方式来描述我正在做的任何建议，我们将不胜感激。另外，我不确定这个社区是否是发布这个问题的正确社区。如果不是，请提供有关我应该在哪里发布此问题的建议。我看过类似的工作，他们通常使用无所不知的调度，我不太了解他们的语法/方法。