首页 / 算法 / 多机调度问题-贪心算法
多机调度问题-贪心算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了多机调度问题-贪心算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3717字,纯文字阅读大概需要6分钟。
内容图文
![多机调度问题-贪心算法](/upload/InfoBanner/zyjiaocheng/845/bfe170ee28244797a19cb8673677e984.jpg)
有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 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。