贪心算法多机调度问题 贪心算法多机调度问题

1、问题描述

假定存在n个独立进行的作业编号为1至n，并使用m台功能相同的设备来进行加工。每个操作所需时间为t_i的时间单位。规定不论哪个操作都可以分配到任意一台设备上进行处理，在未完成前不得中途断掉操作，并且不允许将任何一个操作分解成更小的部分来分别处理。我们的目标就是制定一个最优的任务分配策略，在最短时间内完成所有n个任务。

一个多任务调度系统的多机调度问题是属于NP-Complete类别，在理论研究上尚未找到一种完美的解决方法。针对这一类具有复杂性的调度问题，在实际应用中经常采用基于贪心的选择策略来开发较好的近似算法。

2、贪心算法求解思路

遵循最长处理时间作业优先原则:
当任务数量小于等于机器数量时, 只需将第i台机器的时间区间[0, ti]用于完成第i项任务即可。
当任务数量多于机器数量时, 需先根据每个任务所需计算时间从高到低排序后依次将其分配至空闲状态的机器上。

具体代码如下：

(1)MinHeap.h

 #include <iostream>

    
 using namespace std;
    
 template<class T>
    
 class MinHeap
    
 {
    
 	private:
    
 		T *heap; //元素数组，0号位置也储存元素
    
 		int Current