多机调度问题-贪心算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了多机调度问题-贪心算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3717字，纯文字阅读大概需要6分钟。

内容图文

        有n个完成时间不同的独立任务，m台处理机，n个任务在任意一台处理机上完成及为完成，一台处理机在同一时间只能处理一个任务，要求给定任务时间和处理机数量时，完成所有任务的最短时间。

        多机调度问题是一个NP完全问题，目前没有有效解法，可以使用贪心算法获得近似最优解的答案。当n<=m时，所有任务可以单独占有一台处理机，所以任务完成时间最长的任务就决定了所有任务完成的最短时间；当n>m时，将所有任务按从大到小顺序排列，依次分别放入每次使用中最短时间的机器，就可以获得贪心算法下的近似最优解。

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * Created by saishangmingzhu on 2018/12/11.
 */
public class MultiMachineScheduling {
    public static void main(String[] arg) {
        new MultiMachineScheduling().greedyAlgorithm();
    }
    public void greedyAlgorithm(){
        List<Task> taskList=new ArrayList<>();
        taskList.add(new Task("J1",2));
        taskList.add(new Task("J2",14));
        taskList.add(new Task("J3",4));
        taskList.add(new Task("J4",16));
        taskList.add(new Task("J5",6));
        taskList.add(new Task("J6",5));
        taskList.add(new Task("J7",3));
        List<Machine> machineList=new ArrayList<>();
        machineList.add(new Machine("m1",0));
        machineList.add(new Machine("m2",0));
        machineList.add(new Machine("m3",0));
        Collections.sort(taskList, new Comparator<Task>() {
            @Override
            public int compare(Task o1, Task o2) {
                return o2.getTime()-o1.getTime();
            }
        });
        if (taskList.size()<=machineList.size()){
            System.out.println(taskList.get(0).getTime());
        }
        for (Task task:taskList){
            Collections.sort(machineList, new Comparator<Machine>() {
                @Override
                public int compare(Machine o1, Machine o2) {
                    return o1.getTime()-o2.getTime();
                }
            });
            Machine machine=machineList.get(0);
            machine.getTaskList().add(task);
            machine.setTime(machine.getTime()+task.getTime());
        }
        int minTime=machineList.get(machineList.size()-1).getTime();
        System.out.println(minTime);
        for (Machine machine:machineList){
            System.out.print(machine.getName()+":");
            for (Task task:machine.getTaskList()){
                System.out.print(task.getName()+",");
            }
            System.out.println();
        }
    }
    class Machine{
        private String name;
        private List<Task> taskList=new ArrayList<>();
        private int time;

        public Machine(String name, int time) {
            this.name = name;
            this.time = time;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public List<Task> getTaskList() {
            return taskList;
        }

        public void setTaskList(List<Task> taskList) {
            this.taskList = taskList;
        }

        public int getTime() {
            return time;
        }

        public void setTime(int time) {
            this.time = time;
        }
    }

    class Task{
        private String name;
        private int time;

        public Task(String name, int time) {
            this.name = name;
            this.time = time;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getTime() {
            return time;
        }

        public void setTime(int time) {
            this.time = time;
        }
    }
}

内容总结

以上是互联网集市为您收集整理的多机调度问题-贪心算法全部内容，希望文章能够帮你解决多机调度问题-贪心算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---