论述题 4.  假设有一个中央调度机,有n个相同的任务需要调度到m台服务器上执行,由于每台服务器的配置不一样,因此,服务器执行一个任务所花费的时间也不同。现在假设第i个服务器执行一个任务需要的时间为t[i]。例如,有2个执行机a与b,执行一个任务分别需要7min和10min,有6个任务待调度。如果平分这6个任务,即a与b各3个任务,则最短需要30min执行完所有。如果a分4个任务,b分2个任务,则最短28min执行完。请设计调度算法,使得所有任务完成所需要的时间最短。输入m台服务器,每台机器处理一个任务的时间为t[i],完成n个任务,输出n个任务在m台服务器的分布。int estimate_process_time(int[] t,intm,int n)。
【正确答案】本题可以采用贪心法来解决,具体实现思路如下:
   申请一个数组来记录每台机器的执行时间,初始化为0。在调度任务的时候,对于每个任务,在选取机器的时候采用如下的贪心策略:对于每台机器,计算机器已经分配任务的执行时间+这个任务需要的时间,选用最短时间的机器进行处理。实现代码如下:
   public class Test
   {
   public static void main(String[]args)
   {
   int t[]={7,10};
   int n=6;
   int proTime[]=calculate_orocess_time(t,n);
   if(proTime==null)
   {
   System.out.println("分配失败");
   return;
   }
   int totalTime=proTime[0];
   for(int i=0;i<proTime.length;i++)
   {
   System.out.println("第"+(i+1)+"台服务器有"+proTime[i]/t[i]  +"个任务,执行总时间为:"+proTime[i]);
   if(proTime[i]>totalTime)
   totalTime=proTime[i];
   }
   System.out.println("执行完所有任务所需的时间为"+totalTime);
   }
   /**
   *@param t    每个服务器处理的时间
   *@param n    任务的个数
   *@return各个服务器执行完任务所需的时间
   */
   private static int[]calculate_process_time(int[]t,int n)
   {
   if(t==null||n<=0)
   return null;
   int m=t.length;
   int minlndex;
   int minTime;
   int[] proTime=new int[m];
   for(int i=0;i<n;i++)
   {
   minTime=proTime[0]+t[0];//把任务给第j个机器上后这个机器的执行时间
   minIndex=0;    //把任务给第minIndex个机器上
   for(int j=1;j<m;j++)
   {
   //分配到第j台机器上后执行时间更短
   if(minTime>proTime[j]+t[j])
   {
   minTime=proTime[j]+t[j];
   minIndex=j;
   }
   }
   proTime[minIndex]+=t[minIndex];
   }
   return proTime;
   }
   }
   程序的运行结果为:
   第1台服务器有4个任务,执行总时间为:28
   第2台服务器有2个任务,执行总时间为:20
   执行完所有任务所需的时间为28
【答案解析】