【重要】多机调度问题贪心算法

//【重要】 多机调度问题  贪心算法
//https://www.cnblogs.com/cxmhy/p/4477670.html
#include <iostream>
#include <cstdio>

using namespace std;
int main(){
    int m; //m台机器
    int n; //n个任务
    int time; // 记录最小的处理时间
    cout<<"请输入相同的机器数目:";
    cin>>m;
    cout<<"请输入独立的作业总数：";
    cin>>n;

    int *pro = new int[m]; //记录每个机器的处理时间
    int *t = new int[n];    //记录每个任务的处理时间

    cout<<"请输入独立作业的处理时间t:"<<endl;
    for(int i=0;i<n;i++)  cin>>t[i];
    int temp;
    for(int i=0;i<n-1;i++){ //冒泡法  若进行进一步优化，则采用快速算法
        for(int j=0;j<n-i-1;j++){
            if(t[j] < t[j+1]){ //从大到小排序
                temp = t[j];
                t[j] = t[j+1];
                t[j+1] = temp;
            }
        }
    }

    time = t[0]; // 初始值赋值为单个作业的最大时间
    int min;
    int min_pos;
    if(n>m){
        for(int i=0;i<m;i++)  pro[i] = t[i];
        for(int i=m;i<n;++i){ //对于剩下的n-m个作业，则每次都要找到已经处理的最小时间的机器
            min = pro[0];
            min_pos = 0;

            for(int j=1;j<m;j++){ //找到m个机器中处理所用最小时间的机器
                if(pro[j] < min){
                    min = pro[j];
                    min_pos  = j;
                }
            }

            pro[min_pos] += t[i]; //并把该任务交给这个处理时间最小的机器，并对其处理时间进行更新
            if(time < pro[min_pos]){ //比较总体的处理时间，保证最后得到的时间是这些机器中最大的
                time = pro[min_pos];
            }
        }

    }


    cout << "机器最短的处理时间是:"<<time << endl;

    return 0;
}

/**
 *
 * 多机调度问题类型一：机器是完全相同的，不同的作业处理时间是独立的

问题描述：

设有n个独立的作业{1,2,...n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现规定，任何作业可以在任何一台
机器上加工处理，但未完工之前不允许中断处理。任何作业不能拆分成更小的子作业。



解决思路：

需要实现将n个独立的作业按照时间从大到小排序;在这里需要考虑的是:
如果n<=m,则需要的时间就是n个作业当中最长处理时间t。
如果n>m,先给每个机器分配作业，这一趟下来就分配了m个作业。然后对每个作业而言，选取处理时间最短的机器区域处理。
以上就是贪婪算法的思路。



 
 * 多机调度问题类型二：任务是完全相同的，每个服务器的执行时间是独立的
 * 假设有一个中央调度机，有n个相同的任务需要调度到m台服务器上去执行，由于每台服务器的配置不一样，因此服务器执行一个任务所花费的时间也不同。
现在假设第i个服务器执行 一个任务需要的时间为t[i].


例如：有2个执行机a,b,执行一个任务分别需要7min,10min,有6个任务待调度。如果平分这6个任务，即a,b各3个任务，则最短需要30min执行完所有。
如果a分4个任务 ，b分2个任务，则最短28min执行完。

 * 用一个数组记录每台机器已执行的时间(初始为0)，在调度每一个任务的时候，对每一台机器需要执行的时间进行对比(已执行的时间加上需要执行该任务的时间),
选取执行时间最短的机器进行处理.
 */
#include <iostream>
#include <cstdio>

using namespace std;
int main(){
    int m; //m台机器
    int n; //n个任务
    int time; // 记录最小的处理时间
    cout<<"请输入机器数目:";
    cin>>m;
    cout<<"请输入作业总数：";
    cin>>n;

    int *pro = new int[m]; //记录每个机器的处理时间(当前时间位置)
    int *t = new int[n];    //记录每个机器的处理时间

    cout<<"请输入每个机器处理时间t:"<<endl;
    for(int i=0;i<m;i++)  {
        cin>>t[i];
        pro[i] = 0; //每个机器的初始值都设置为0
    }

    int min;
    int min_pos;

    for(int i=0;i<n;i++){ // 对于n个任务，每次都要找到处理时间最小的机器
        min = pro[0] + t[0];
        min_pos = 0;

        for(int j=1;j<m;j++){ //找到m个机器中处理所用最小时间的机器
            if(pro[j] + t[j] < min){
                min = pro[j] + t[j];
                min_pos = j;
            }
        }

        pro[min_pos] += t[min_pos]; // 把该任务交给处理时间最小的机器，并对其处理时间进行更新
        time = pro[min_pos];

    }

    cout << "机器最短的处理时间是:" << time << endl;
    for(int i=0;i<m;i++){
        cout<<"标号为"<<i+1<<"的机器共调度的任务数目是:"<<pro[i] / t[i] << endl;
    }

    return 0;
}