多机调度问题 贪心算法

多机调度问题

要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业

要求：

分别采用以下两种贪心策略实现算法求解，对比实验结果，分析哪种贪心策略更适合应用于多机调度问题。

• 最长处理时间作业优先的贪心选择策略。
• 最短处理时间作业优先的贪心选择策略。

至少采用两组实验数据进行实验，请参考实验数据一，自己再设计一组实验数据。

实验数据一：7个独立的作业由3台机器加工处理，各作业所需的处理时间为：{2，14，4，6，16，5，3}。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
@SuppressWarnings("all")
public class Multi_machine_scheduling_problem {//贪心算法之多机调度问题

    static void Shell_Sort(int []a) {//希尔排序之升序
        int i,j,key,mid;
        for(mid = a.length / 2; mid > 0; mid /= 2){
            for(i = mid; i < a.length; i  ){
                j = i;
                key = a[j];
                if (a[j] < a[j - mid]) {
                    while(j - mid >= 0 && a[j - mid] > key){
                        a[j] = a[j - mid];
                        j = j - mid;
                    }
                    a[j] = key;
                }
            }
        }
    }

    static void Shell_Sort_contrary(int []a) {//希尔排序之降序
        int i,j,key,mid;
        for(mid = a.length / 2; mid > 0; mid /= 2){
            for(i = mid; i < a.length; i  ){
                j = i;
                key = a[j];
                if (a[j] > a[j - mid]) {
                    while(j - mid >= 0 && a[j - mid] < key){
                        a[j] = a[j - mid];
                        j = j - mid;
                    }
                    a[j] = key;
                }
            }
        }
    }

    private static int getMin(List<Integer> list){
        int min = list.get(0);
        for(int i = 0;i < list.size();i  ){
            if(list.get(i) < min){
                min = list.get(i);
            }
        }
        return list.indexOf(min);
    }

    private static int getMax(List<Integer> list){
        int max = list.get(0);
        for(int i = 0;i < list.size();i  ){
            if(list.get(i) > max){
                max = list.get(i);
            }
        }
        return list.indexOf(max);
    }

    private static void MachineDis(int []worksTime,int machineNum){//多机调度问题
        int runMinNum;
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0;i < worksTime.length;i  ){//存储现有的作业
            list.add(worksTime[i]);
        }
        List<Integer> listRun = new ArrayList<Integer>();
        for(int i = 0;i < machineNum;i  ) {//将作业放入机器
            listRun.add(list.get(i));
        }
        for(int i = 0;i < machineNum;i  ) {//移除已经放入机器的作业
            list.remove(0);
        }
        for(int i = 0;i < list.size();i  ) {//更新最先完成作业的机器
            runMinNum = getMin(listRun);
            listRun.set(runMinNum,(list.get(i)   listRun.get(runMinNum)));
        }
        System.out.println("最短时间为:"   listRun.get(getMax(listRun)));
    }

    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入作业数和机器数");
        int worksNum = scanner.nextInt();//工作数
        int machineNum = scanner.nextInt();//机器数
        System.out.println("请输入每个作业需要的时间");
        int []worksTime = new int[worksNum];//每个作业时间
        for(int i = 0;i < worksNum;i  ){
            worksTime[i] = scanner.nextInt();
        }
        System.out.print("最长处理时间作业优先贪心选择策略");
        Shell_Sort_contrary(worksTime);//降序
        MachineDis(worksTime,machineNum);
        System.out.print("最短处理时间作业优先贪心选择策略");
        Shell_Sort(worksTime);//升序
        MachineDis(worksTime,machineNum);
    }
}

这篇好文章是转载于：学新通技术网