计算机算法分析与设计（13）---贪心算法(多机调度问题)

一、问题概述

1.1 思路分析

 1. 设有 $n$ 个独立的作业 $1,2,\dots ,n$，由 $m$ 台相同的机器 $M_1,M_2,\dots ,M_m$ 进行加工处理，作业 $i$ 所需的处理时间为 $t_i(1\le i\le n)$，每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的 $n$ 个作业在尽可能短的时间内由 $m$ 台机器加工处理完成。

 2. 解决思路：（1）如果 $n<m$，这种情况很简单，将 $n$ 个作业分配给 $m$ 个机器中的 $n$ 个就可以了。（2）如果 $n>m$，则用贪心算法求解。

 3. 贪心算法求解多机调度问题的贪心策略是最长处理时间的作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。

1.2 实例分析

 设 $7$ 个独立作业 $1,2,3,4,5,6,7$ 由 $3$ 台机器 $M1,M2,M3$ 加工处理，各作业所需的处理时间分别为 $2,14,4,16,6,5,3$。贪心算法产生的作业调度如下图所示。所需要的加工时间为17。

二、代码编写

#include<bits/stdc++.h>
using namespace std;bool compare(int a,int b)
{return a>b;}int main(){int n,m; //作业个数为n, 机器个数为mcout<<"请输入作业和机器的个数："<<endl; cin>>n>>m;vector<int> time(n);//vector<vector<int> > machine(m); //理解成m×1二维数组 vector<int> sumTime(m,0); //0表示初始化值为0 cout<<"请输入每个作业的处理时间："<<endl; for(int i=0;i<n;i++){cin>>time[i];}sort(time.begin(),time.end(),compare); //对time进行排序，从大到小。for(int i=0;i<n;i++){int select=0;for(int j=0;j<m;j++){if(sumTime[j]<sumTime[select]){select=j;}}//machine[select].push_back(time[i]);sumTime[select]=sumTime[select]+time[i];	}int maxTime=sumTime[0];for(int j=0;j<m;j++){if(sumTime[j]>maxTime){maxTime=sumTime[j];}}for(int j=0;j<m;j++){cout<<"第"<<j+1<<"台机器所需处理总时间为: "<<sumTime[j]<<endl; }cout<<"处理所有作业时间共需: "<<maxTime;return 0;
}