您现在的位置是:首页 > 正文

贪心法求解多机调度问题

2024-02-01 03:12:51阅读 3

问题描述

设有n个独立的作业{1,2,…,n},由m台相同的机器{1,2, …,m}进行加工处理,作业i所需的处理时间为ti(1≤i≤n),每个作业均可在任何一台机器上加工处理,但未完工前不允许中断,任何作业也不能拆分成更小的子作业。
多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

问题求解

贪心法求解多机调度问题的贪心策略是最长处理时间作业优先,即把处理时间最长的作业分配给最先空闲的机器,这样可以保证处理时间长的作业优先处理,从而在整体上获得尽可能短的处理时间。
按照最长处理时间作业优先的贪心策略,当m≥n时,只要将机器i的[0,ti)时间区间分配给作业i即可;
当m<n时,首先将n个作业依其所需的处理时间从大到小排序,然后依此顺序将作业分配给空闲的处理机。

代码

int n = 7;
int m = 3;
struct NodeType
{
	int no;
	int t;
	int mno;//机器序号
	bool operator<(const NodeType &s)const//按照处理时间递减排序
	{
		return t > s.t;
	}
};

struct NodeType A[] = { {1,2},{2,14},{3,4},{4,16},{5,6},{6,5},{7,3} };

void solve()
{
	NodeType e;
	if (n <= m)
		return;
	sort(A, A + n);
	priority_queue<NodeType> qu;
	for (int i = 0; i < m; i++)//给每个机器分配一个作业
	{
		A[i].mno = i + 1;
		qu.push(A[i]);
	}
	for (int j = m; j < n; j++)//分配余下的作业
	{
		e = qu.top();
		qu.pop();
		e.t += A[j].t;
		qu.push(e);
	}
}

算法分析

排序的时间复杂度为O(nlog2n),两次for循环的时间合起来为O(n),所以本算法的时间复杂度为O(nlog2n)。

网站文章

  • DNDC 模型建模方法及在土壤碳储量、温室气体排放、农田减排、土地变化、气候变化中的实践

    碳循环的精确模拟是实现“双碳”行动的关键。DNDC(Denitrification-Decomposition,反硝化-分解模型)是目前国际上最为成功的模拟生物地球化学循环的模型之一,自开发以来,经过...

    2024-02-01 03:12:43
  • 美团外卖美食知识图谱的迭代及应用

    美团外卖美食知识图谱的迭代及应用

    总第451篇2021年 第021篇菜品是外卖交易过程的核心要素,对菜品的理解也是实现外卖供需匹配的重点。今天我们将一次推送三篇文章,系统地介绍了美团外卖美食知识图谱的构建和应用。《美团外卖...

    2024-02-01 03:12:14
  • Vue-Threejs学习

    Vue-Threejs学习

    Threejs学习 最近在学习threejs,探索3D开发,主要记录一下学习的过程及遇到的问题,以后续查看,目前主要涉及的也就几个知识点,纹理贴图、2D标签、挖洞、简单动画(开关门)、引入Ethart...

    2024-02-01 03:12:08
  • PHP安装Mcrypt扩展

    在使用PHP开发的过程中,为了提供数据传输的安全性,避免不了使用加密函数,除了使用php本身自带的几个函数,php还提供Mhash和Mcrypt2个扩展库。Mcrypt扩展库支撑的加密算法可以看http://mcrypt.sourceforge.net/,这里有对这个接口的详细介绍。 这里介绍2种安装Mcrypt扩展库的方法,算是对自己安装过程中遇到问题的一个总结。 1. 安装Mcrypt

    2024-02-01 03:12:04
  • 计算机二级C语言公共基础知识,以及习题总结(六)数据模型

    计算机二级C语言公共基础知识,以及习题总结(六)数据模型

    数据模型的基本概念 1、数据模型是数据特征的抽象 数据模型描述的内容 (1)数据结构 (2)数据操作 (3)数据约束 数据模型按不同的应用层次分成三种类型 概念数据模型(Conceptual Data...

    2024-02-01 03:11:33
  • selenium 页面加载慢,超时的解决方案

    开发环境:win10-64 python2.7.16 chrome77from selenium import webdriverdriver = webdriver.Chrome(executable_path='chromedriver.exe')driver.get('http://全部加载完成超级慢的网站')user = 'abc...

    2024-02-01 03:11:27
  • Python智力问答小游戏

    Python智力问答小游戏

    在这个Python智力问答小游戏中,我们将提供一系列问题,并编写代码来实现一个简单的问答游戏。玩家将被要求回答一些与Python编程相关的问题,并根据他们的回答来获得得分。接下来,我们需要编写代码来显...

    2024-02-01 03:10:53
  • [EXP公开] CVE-2020-13935: Tomcat WebSocket 拒绝服务漏洞通告

    [EXP公开] CVE-2020-13935: Tomcat WebSocket 拒绝服务漏洞通告

    原创 360CERT [三六零CERT](javascript:void(0)???? 今天 报告编号:B6-2020-110601 报告来源:360CERT 报告作者:360CERT 更新日期:20...

    2024-02-01 03:10:45
  • 常见的语法错误

    1、有缩进 :IndentationError: unexpected indent2、解释器会明确指出错误原因是无法识别的字符“:invalid character ’

    2024-02-01 03:10:37
  • class 文件方法表集合

    class 文件方法表集合

    一点睛 methods:指向常量池索引集合,它完整描述了每个方法的签名。 在字节码文件中,每一个 method_info 项都对应着一个类或者接口中的方法信息。比如方法的访问修饰符(public、pr...

    2024-02-01 03:10:30