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

tpffy 2021-08-14 原文

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

　　有这么个问题：有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的处理时间为works[i]。任何作业可以在任何一台机器上面加工处理，但未完工之前不允许中断处理。任何作业不能拆分成更小的作业。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

　　这个问题是NP问题，可以使用贪心算法求解出其近似解。

　　贪心的规则：将作业按照执行时间从大到小排序，每当机器空闲时选取剩余作业中执行时间最长的作业。每次选取时间最长的作业，而且是已经空闲的机器，如果安排给忙碌的机器只会让总的完成时间更长，这样可以避免由时间长的作业造成较大的尾延迟。

　　以下案例中存在 7 个作业，由三台机器并发完成。一种合理的调度方式如下图所示。

　　代码的编写很简单，定义一个机器作业完成时间数组，按照作业顺序调度作业，每次选择机器完成时间最小的那个机器（最先空闲）。

#include <stdio.h>
#include <malloc.h>

/*
    n: 作业数量
    m：机器数量 
*/
int n = 7,m = 3;
int works[7] = {16,14,6,5,4,3,2},machines[3] = {0};

int distribute();

int main(void)
{
    printf("%d\n",distribute());
    return 0;
} 

int distribute()
{
    int minP = -1,minT = 0x8ffffff;
    int maxT = -1;
    int i=0,j=0;
    
    for(i = 0;i < n; i++)
    {
        minP = 0;
        minT = machines[0];
        for(j = 1;j < m; j++)
        {
            if(minT > machines[j])
            {
                minP = j;
                minT = machines[j];
            }
        } 
        machines[minP] += works[i]; 
        if(maxT < machines[minP])
        {
            maxT = machines[minP];
        }
    }
    return maxT;
}