algorithm - Max-Min 和 Min-Min 算法实现

Question

我正在尝试模拟 Max-Min 和 Min-Min 调度算法，并在模拟中自己编写代码。但是不太了解如何在代码中实现它们的工作方式。

例如，在 FCFS 算法中我使用了 3 个服务器 (vms)，每个服务器都比另一个服务器快，并且有 5 个任务具有不同的到达时间。所以第一个任务将检查第一台服务器并将安排在那里，第二个如果在第一个尚未完成时到达，将检查可用性并安排到第二台服务器。如果所有 3 个服务器都被占用，则下一个任务将被安排到剩余执行时间最短的服务器。

现在对于 Min-Min 和 Min-Max，这是理论背景:

敏敏:阶段 1:首先计算每台机器上每个任务的完成时间，然后为每个任务选择在最短可能时间内处理任务的机器。阶段 2:在元任务中的所有任务中，选择完成时间最短的任务，并将其分配给预期执行时间最短的机器。该任务从元任务列表中删除，该过程将继续，直到元任务列表为空。

最大-最小值:阶段 1:首先计算每台机器上每个任务的完成时间，然后为每个任务选择在最短可能时间内处理任务的机器阶段 2:在 Meta Task 中的所有任务中，选择完成时间最长的任务并将其分配给机器。该任务从元任务列表中删除，该过程将继续，直到元任务列表为空。

我得到了两种算法的第 1 阶段，我需要检查任务的突发时间和服务器的加速 -> 突发/加速 = 执行时间。我会为每项任务找到最好的服务器。但我无法理解第 2 阶段。对于 Min-Min，我必须每次都选择最快的任务，当我找到它时，我必须将它安排到更快的服务器上。但是工作量会不平衡，正如我所说的 3 台服务器，至少有一台速度更快，比如说 ID 为 1 的服务器，所以每次任务安排到这台服务器时，我还需要另外 2 台服务器来工作。

与 Max-Min 相同的问题，找到最差的任务，将它安排到最差的服务器，但只有一台服务器是最差的，所以其他 2 台将无法工作。我应该如何进行平衡并考虑到任务在不同时间到达？

如果您还需要什么，请告诉我并提前致谢!

Answer 1

您可以在 A Comparative Analysis of Min-Min and Max-Min Algorithms based on the Makespan Parameter 中找到对这两种算法的详细描述。 :

我在这里粘贴了 Min-Min 的伪代码。 ET_ij 是任务 t_i 在资源 R_j 上的执行时间。 r_j为R_j的就绪时间。

你确实可以有不平衡负载，因为所有小任务都会先执行。 Max-Min算法克服了这个缺点。

Max-Min algorithm performs the same steps as the Min-Min algorithm but the main difference comes in the second phase, where a task t_i is selected which has the maximum completion time instead of minimum completion time as in min-min and assigned to resource R_j, which gives the minimum completion time.