C++贪心算法处理多机调度问题详解

多机调度问题思路

1、把作业按加工所用的时间从大到小排序

2、如果作业数目比机器的数目少或相等，则直接把作业分配下去

3、 如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上 s 最小的链表加入新作业

可以考虑以下的贪心策略:

(1)最长处理时间作业优先的贪心选择策略。

(2)最短处理时间作业优先的贪心选择策略。

(3)作业到达时间优先的贪心选择策略。

*贪⼼策略：优先处理花费时间长的任务，这样可以减少短任务的等待时间.

问题描述

形式：有n个任务，m台机器，n>m，每个作业i可以选择⼀台设备进⾏加⼯，加⼯时间为ti，每台机器同时只能加⼯⼀个作业，且不可中断。实现作业调度，使得n个作业的等待时间最短。

假定有7个独立作业，所需处理时间分别为｛2，14，4，16，6，5，3｝，由三台机器M1,M2,M3加工。按照贪心算法产生的作业调度如下图所示，所需总加工时间为17.

代码实现【C++】

#include<iostream>
using namespace std;
#define N 7
#define M 3
int s[M] = { 0, 0, 0 };
//求出目前处理作业的时间和 最小的机器号
int min(int m){
int min = 0;
int i;
for (i = 1; i<m; i++){
if (s[min]>s[i]){
min = i;
}
}
return min;
}
//求最终结果（最长处理时间）
int max(int s[], int num){
int max = s[0];
for (int i = 1; i<num; i++){
if (max<s[i])
max = s[i];
}
return max;
}
//机器数大于待分配作业数
int setwork1(int t[], int n){
int i = 0;
for (; i<n; i++){
s[i] = t[i];
}
int ma = max(s, N);
return ma;
}
//机器数小于待分配作业数
int setwork2(int t[], int n){
int i;
int mi = 0;
for (i = 0; i<n; i++){
mi = min(M);
cout << "接下来由" << mi+1 << "号机器处理任务" << i + 1 << endl;
s[mi] = s[mi] + t[i];
}
int ma = max(s, M);
return ma;
}
void main()  //DEV中是int,vc++6.0中是void
{
	int time[N] = { 16, 14, 6, 5, 4, 3, 2 };//处理时间按从大到小排序
	int maxtime;
	if (M >= N)
		maxtime = setwork1(time, N);
	else
		maxtime = setwork2(time, N);
	cout << "最多耗费时间" << maxtime << endl;
}

结果

到此这篇关于C++贪心算法处理多机调度问题详解的文章就介绍到这了,更多相关C++多机调度内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++算法学习之贪心算法的应用

    C++算法学习之贪心算法的应用

    目录 贪心1 实验题目:减肥的小K1 实验题目:最小跳数 实验题目:排队接水 贪心-堂练 实验题目: 区间问题1 实验题目:种树 实验题目:智力大冲 实验题目:删除数字II 贪心1 实验题目:减肥的小K1 题目描述: 小K没事干,他要搬砖头,为了达到较好的减肥效果,教练规定的方式很特别:每一次,小K可以把两堆砖头合并到一起,消耗的体力等于两堆砖头的重量之和.经过 n-1次合并后, 就只剩下一堆了.小K在搬砖头时总共消耗的体力等于每次合并所耗体力之和.小K为了偷懒,希望耗费的体力最小.例如有 3堆

  • C++ 算法精讲之贪心算法

    C++ 算法精讲之贪心算法

    目录 选择排序 平衡字符串 买股票的最佳时机 跳跃游戏 钱币找零 多机调度问题 活动选择 无重叠区间 选择排序 我们熟知的选择排序,其采用的就是贪心策略. 它所采用的贪心策略即为每次从未排序的数据中选取最小值,并把最小值放在未排序数据的起始位置,直到未排序的数据为0,则结束排序. void swap(int* arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } void selectSort(int* a

  • C++ 搬水果贪心算法实现代码

    C++ 搬水果贪心算法实现代码 (1)题目描述: 在一个果园里,小明已经将所有的水果打了下来,并按水果的不同种类分成了若干堆,小明决定把所有的水果合成一堆.每一次合并,小明可以把两堆水果合并到一起,消耗的体力等于两堆水果的重量之和.当然经过 n‐1 次合并之后,就变成一堆了.小明在合并水果时总共消耗的体力等于每次合并所耗体力之和. 假定每个水果重量都为 1,并且已知水果的种类数和每种水果的数目,你的任务是设计出合并的次序方案,使小明耗费的体力最少,并输出这个最小的体力耗费值.例如有 3 种水果,

  • C++贪心算法实现活动安排问题(实例代码)

    贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关. 具体代码如下所示: #include <cstdio> #include <iostream> #include <ctime> #include <

  • C++贪心算法实现马踏棋盘

    C++贪心算法实现马踏棋盘

    本文实例为大家分享了C++贪心算法实现马踏棋盘的具体代码,供大家参考,具体内容如下 算法实现流程: 步骤1:初始化马的位置(结构体horse {x, y}) 步骤2:确定马从当前点出发,可跳跃的附近8个点,以结构体Jump数组给出,但需判断当前给出的附近8个点是否曾经访问过,或者是否这8个点超出棋盘尺寸. 步骤3:跟据步骤2确定跳跃的点,分别计算可跳跃点的下下一步,可跳跃点的个数.并选出下下步可跳跃点数最少的点作为马下一步跳跃的点.(举例说明:马当前所在点坐标(4,4),下一步可跳跃点有(5,2

  • 采用C++实现区间图着色问题（贪心算法）实例详解

    本文所述算法即假设要用很多个教室对一组活动进行调度.我们希望使用尽可能少的教室来调度所有活动.采用C++的贪心算法,来确定哪一个活动使用哪一间教室. 对于这个问题也常被称为区间图着色问题,即相容的活动着同色,不相容的着不同颜色,使得所用颜色数最少. 具体实现代码如下: //贪心算法 #include "stdafx.h" #include<iostream> #define N 100 using namespace std; struct Activity { int n

  • C++贪心算法处理多机调度问题详解

    多机调度问题思路 1.把作业按加工所用的时间从大到小排序 2.如果作业数目比机器的数目少或相等,则直接把作业分配下去 3. 如果作业数目比机器的数目多,则每台机器上先分配一个作业,如下的作业分配时,是选那个表头上 s 最小的链表加入新作业 可以考虑以下的贪心策略: (1)最长处理时间作业优先的贪心选择策略. (2)最短处理时间作业优先的贪心选择策略. (3)作业到达时间优先的贪心选择策略. *贪⼼策略:优先处理花费时间长的任务,这样可以减少短任务的等待时间. 问题描述 形式:有n个任务,m台机器

  • matlab鸟群算法求解车间调度问题详解及实现源码

    matlab鸟群算法求解车间调度问题详解及实现源码

    目录 一.车间调度简介 1 车间调度定义 2 传统作业车间调度 3 柔性作业车间调度 二.蝴蝶优化算法(MBO)简介 1 介绍 2 香味 3 具体算法 三.部分源代码 五.matlab版本及参考文献 一.车间调度简介 1 车间调度定义 车间调度是指根据产品制造的合理需求分配加工车间顺序,从而达到合理利用产品制造资源.提高企业经济效益的目的.车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加工.问题需要满足的条件包括每个零件的各道工序使用每台机器不多于1次,每个零件都按照一定的顺序进

  • 基数排序算法的原理与实现详解(Java/Go/Python/JS/C)

    目录 说明 实现过程 示意图 性能分析 代码 Java Python Go JS TS C C++ 链接 说明 基数排序(RadixSort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较.由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数.基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机(Tabulation Machine)上的 基数排序的方式可以采用LSD(Least significant di

  • 数据结构与算法中二叉树子结构的详解

    数据结构与算法中二叉树子结构的详解 需求 输入两棵二叉树A,B,判断B是不是A的子结构.(ps:我们约定空树不是任意一个树的子结构) 树的描述: class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } 解决思路 使用了栈将元素入栈,并不断的弹出元素,弹出一个元素的时候,拼接成字符串,并用特殊符号进行区分,该方法

  • C++实现算法两个数字相加详解

    Add Two Numbers 两个数字相加 You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers

  • python机器学习算法与数据降维分析详解

    python机器学习算法与数据降维分析详解

    目录 一.数据降维 1.特征选择 2.主成分分析(PCA) 3.降维方法使用流程 二.机器学习开发流程 1.机器学习算法分类 2.机器学习开发流程 三.转换器与估计器 1.转换器 2.估计器 一.数据降维 机器学习中的维度就是特征的数量,降维即减少特征数量.降维方式有:特征选择.主成分分析. 1.特征选择 当出现以下情况时,可选择该方式降维: ①冗余:部分特征的相关度高,容易消耗计算性能 ②噪声:部分特征对预测结果有影响 特征选择主要方法:过滤式(VarianceThreshold).嵌入式(正

  • python目标检测SSD算法预测部分源码详解

    python目标检测SSD算法预测部分源码详解

    目录 学习前言 什么是SSD算法 ssd_vgg_300主体的源码 学习前言 ……学习了很多有关目标检测的概念呀,咕噜咕噜,可是要怎么才能进行预测呢,我看了好久的SSD源码,将其中的预测部分提取了出来,训练部分我还没看懂 什么是SSD算法 SSD是一种非常优秀的one-stage方法,one-stage算法就是目标检测和分类是同时完成的,其主要思路是均匀地在图片的不同位置进行密集抽样,抽样时可以采用不同尺度和长宽比,然后利用CNN提取特征后直接进行分类与回归,整个过程只需要一步,所以其优势是速度

  • python目标检测SSD算法训练部分源码详解

    python目标检测SSD算法训练部分源码详解

    目录 学习前言 讲解构架 模型训练的流程 1.设置参数 2.读取数据集 3.建立ssd网络. 4.预处理数据集 5.框的编码 6.计算loss值 7.训练模型并保存 开始训练 学习前言 ……又看了很久的SSD算法,今天讲解一下训练部分的代码.预测部分的代码可以参照https://blog.csdn.net/weixin_44791964/article/details/102496765 讲解构架 本次教程的讲解主要是对训练部分的代码进行讲解,该部分讲解主要是对训练函数的执行过程与执行思路进行详

  • Java中Prime算法的原理与实现详解

    Java中Prime算法的原理与实现详解

    目录 Prim算法介绍 1.点睛 2.算法介绍 3. 算法步骤 4.图解 Prime 算法实现 1.构建后的图 2.代码 3.测试 Prim算法介绍 1.点睛 在生成树的过程中,把已经在生成树中的节点看作一个集合,把剩下的节点看作另外一个集合,从连接两个集合的边中选择一条权值最小的边即可. 2.算法介绍 首先任选一个节点,例如节点1,把它放在集合 U 中,U={1},那么剩下的节点为 V-U={2,3,4,5,6,7},集合 V 是图的所有节点集合. 现在只需要看看连接两个集合(U 和 V-U)

  • Go Java算法之交错字符串示例详解

    目录 交错字符串 方法一:动态规划(Java) 方法一:动态规划(GO) 交错字符串 给定三个字符串 s1.s2.s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的. 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 +

随机推荐