双机流水作业调度问题——Johnson算法「建议收藏」

双机流水作业调度问题——Johnson算法「建议收藏」概述流水作业是并行处理技术领域的一项关键技术,它是以专业化为基础,将不同处理对象的同一施工工序交给专业处理部件执行,各处理部件在统一计划安排下,依次在各个作业面上完成指定的操作。流水作业调度问题是一个非常重要的问题,其直接关系到计算机处理器的工作效率。然而由于牵扯到数据相关、资源相关、控制相关等许多问题,最优流水作业调度问题处理起来非常复杂。已经证明,当机器数(或称工序数)大于等于3时,流水作业调度问题是一个NP-hard问题(e.g分布式任务调度)。粗糙地说,即该问题至少在目前基本上没有可能找到多项

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

概述

流水作业是并行处理技术领域的一项关键技术,它是以专业化为基础,将不同处理对象的同一施工工序交给专业处理部件执行,各处理部件在统一计划安排下,依次在各个作业面上完成指定的操作。
流水作业调度问题是一个非常重要的问题,其直接关系到计算机处理器的工作效率。然而由于牵扯到数据相关、资源相关、控制相关等许多问题,最优流水作业调度问题处理起来非常复杂。已经证明,当机器数(或称工序数)大于等于3时, 流水作业调度问题是一个NP-hard问题(e.g分布式任务调度)。粗糙地说,即该问题至少在目前基本上没有可能找到多项式时间的算法。只有当机器数为2时,该问题可有多项式时间的算法(机器数为1时该问题是平凡的)。

我们先给出流水作业调度的定义:

设有 n n n个作业,每一个作业 i i i均被分解为 m m m项任务: T i 1 , T i 2 , … , T i m \mathrm{T}_{\mathrm{i} 1}, \mathrm{T}_{\mathrm{i} 2}, \ldots, \mathrm{T}_{\mathrm{im}} Ti1,Ti2,,Tim( 1 ≤ i ≤ n 1 \leq i \leq n 1in,故共有 m ∗ n m * n mn个任务), 要把这些任务安排到m台机器上进行加工。 如果任务的安排满足下列3个条件, 则称该安排为流水作业调度:

  1. 每个作业 i 的第 j 项任务Tij ( 1 ⩽ i ⩽ n , 1 ⩽ j ⩽ m ) (1 \leqslant \mathrm{i} \leqslant \mathrm{n}, 1 \leqslant \mathrm{j} \leqslant \mathrm{m}) (1in,1jm) 只能安排在机器 P j \mathrm{P}_{\mathrm{j}} Pj 上进行加工
  2. 作业 i 的第 j 项任务 T i j ( 1 ≤ i ≤ n , 2 ≤ j ≤ m ) \mathrm{T}_{\mathrm{ij}}(1 \leq \mathrm{i} \leq \mathrm{n}, 2 \leq \mathrm{j} \leq \mathrm{m}) Tij(1in,2jm) 的开始加工时间均安排在第 j − 1 \mathrm{j}-1 j1 项任务 T i j − 1 \mathrm{T}_{\mathrm{ij}-1} Tij1 加工完毕之后,任何一个作业的任务必须依次完成,前一项任务完成之后才能开 始着手下一项任务:
  3. 任何一台机器在任何一个时刻最多只能承担一项任务。

最优流水作业调度是指:

设任务 τ i j \tau_{i j} τij在机器 P j P_{j} Pj上进行加工需要的时间为 t i j t_{i j} tij。 如果所有的 t i j ( 1 ⩽ i ⩽ n , 1 ⩽ j ⩽ m ) \mathrm{t}_{\mathrm{ij}}(1 \leqslant \mathrm{i} \leqslant \mathrm{n}, 1 \leqslant \mathrm{j} \leqslant \mathrm{m}) tij(1in,1jm)均已给出, 要找出一种安排任务的方法, 使得完成这 n n n个作业的加工时间为最少。 这个安排称之为最优流水作业调度。

前面已经说过,当 m ≥ 3 \mathrm{m} \geq 3 m3时该问题是NP问题,这里我们只给出 m = 2 m = 2 m=2时时间复杂度在多项式以内的Johnson算法。

求解流水作业调度问题的Johnson算法具体描述如下:

1、设 a[i]和 b[i] ( 0 ≤ i < n ) (0 \leq i<n) (0i<n)分别为作业 i 在两台设备上的处理时间。建立由三元组 (作业
号,处理时间,设备号)组成的三元组表 d。其中,处理时间是指每个作业所包含的两 个任务中时间较少的处理时间。

 设  n = 4 , ( a 0 , a 1 , a 2 , a 3 ) = ( 3 , 4 , 8 , 10 )  和  ( b 0 , b 1 , b 2 , b 3 ) = ( 6 , 2 , 9 , 15 )  的作业  0  的三元组为  ( 0 , 3 , 0 ) ,  作业  1  的三元组为  ( 1 , 2 , 1 )  。  如图  ( a )  所示。  \begin{array}{l} \text { 设 } \mathrm{n}=4,\left(\mathrm{a}_{0}, \mathrm{a}_{1}, \mathrm{a}_{2}, \mathrm{a}_{3}\right)=(3,4,8,10) \text { 和 }\left(\mathrm{b}_{0}, \mathrm{b}_{1}, \mathrm{b}_{2}, \mathrm{b}_{3}\right)=(6,2,9,15) \text { 的作业 } 0 \text { 的三元组为 } \\ (0,3,0), \text { 作业 } 1 \text { 的三元组为 }(1,2,1) \text { 。 } \text { 如图 }(\mathrm{a}) \text { 所示。 } \end{array}   n=4,(a0,a1,a2,a3)=(3,4,8,10)  (b0,b1,b2,b3)=(6,2,9,15) 的作业 0 的三元组为 (0,3,0), 作业 1 的三元组为 (1,2,1)   如图 (a) 所示。 

(a)三元组表
 作业号   处理时间   设备号  0 3 0 1 2 1 2 8 0 3 10 0 \begin{array}{|c|c|c|} \hline \text { 作业号 } & \text { 处理时间 } & \text { 设备号 } \\ \hline 0 & 3 & 0 \\ \hline 1 & 2 & 1 \\ \hline 2 & 8 & 0 \\ \hline 3 & 10 & 0 \\ \hline \end{array}  作业号 0123 处理时间 32810 设备号 0100

2、对三元组表按处理时间排序,得到排序后的三元组表 d。如图(b)所示。

(b)按处理时间排序
 作业号   处理时间   设备号  1 2 1 0 3 0 2 8 0 3 10 0 \begin{array}{|c|c|c|} \hline \text { 作业号 } & \text { 处理时间 } & \text { 设备号 } \\ \hline 1 & 2 & 1 \\ \hline 0 & 3 & 0 \\ \hline 2 & 8 & 0 \\ \hline 3 & 10 & 0 \\ \hline \end{array}  作业号 1023 处理时间 23810 设备号 1000

3、对三元组表的每一项 d [ i ] ( 0 ≤ i < n ) , \mathrm{d}[\mathrm{i}](0 \leq \mathrm{i}<n), d[i](0i<n), 从左右两端生成最优作业排列 c [ j ] ( 0 ≤ j < n ) , c [ j ] \mathrm{c}[\mathrm{j}](0 \leq \mathrm{j}<n), \mathrm{c}[\mathrm{j}] c[j](0j<n),c[j]是作业号。如果 d[i]设备号为 1,则将作业 i 置于 c 的左端末尾,否则置于 c 的右端 末尾。如图©所示,由两端向中间存放。

(c)最优作业排列
(0,2,3,1)

(d)最优调度方案

p 1 3 8 10 4 p 2 6 9 15 2 \begin{array}{|l|l|l|l|l|} \hline \mathrm{p} 1 & 3 & 8 & 10 & 4 \\ \hline \mathrm{p} 2 & 6 & 9 & 15 & 2 \\ \hline \end{array} p1p23689101542

例题:

下面是北大PKU POJ 第2751题Saving Endeavour

有2台机器,n件任务,必须先在S1上做,再在S2上做。任务之间先做后做任意。求最早的完工时间。

双机调度问题Johnson算法简析:
(1)把作业按工序加工时间分成两个子集,第一个集合中在S1上做的时间比在S2上少,其它的作业放到第二个集合。先完成第一个集合里面的作业,再完成第二个集合里的作业。

(2)对于第一个集合,其中的作业顺序是按在S1上的时间的不减排列;对于第二个集合,其中的作业顺序是按在S2上的时间的不增排列。

Johnson算法的时间取决于对作业集合的排序,因此,在最怀情况下算法的时间复杂度为 0 (  nlogn  ) 0(\text { nlogn }) 0( nlogn ),所需的空间复杂度为 0 (  n  ) 0(\text { n }) 0( n )

c语言代码如下:

#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
const int MAXN=10005;
struct TNode
{ 

int s1,s2;
}ws[MAXN];
int topf,tops;
int n;
bool operator<(TNode x,TNode y)
{ 

if (x.s1<x.s2&&y.s1>=y.s2) return true;
if (x.s1<x.s2&&y.s1<y.s2) return x.s1<y.s1;
if (x.s1>=x.s2&&y.s1>=y.s2) return x.s2>y.s2;
return false;
}
int max(int x,int y)
{ 

return x>y?x:y;
}
void Work()
{ 

sort(ws,ws+n);
int i,t1=0,t2=0;
for (i=0;i<n;i++)
{ 

t1+=ws.s1;
t2=max(t1,t2)+ws.s2;
}
printf("%dn",t2);
}
void Read()
{ 

int i;
while (scanf("%d",&n)&&n)
{ 

for (i=0;i<n;i++)
scanf("%d%d",&ws.s1,&ws.s2);
Work();
}
}
int main()
{ 

Read();
return 1;
}

Jetbrains全家桶1年46,售后保障稳定

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

发布者:全栈程序员-用户IM,转载请注明出处:http://www.javaforall.cn/234876.html原文链接:http://www.javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ubuntu上安装gcc

    ubuntu上安装gcc首先我是直接根据别人博客来的:sudoaptupdatesudoaptinstallbuild-essential主要是说build-essential中包含了GNU编辑器集合

  • 音乐播放器之QQ音乐最新api,亲测可用「建议收藏」

    音乐播放器之QQ音乐最新api,亲测可用「建议收藏」大家好,前段时间重写了自己的音乐播放器,源码放在github上,源码地址和项目地址下面都有,如果喜欢记得star一下哈。由于之前给大家分享的api虽然可以用,但是版本太旧了,很多也没有了歌词,今天博主给大家分享一个最新的qq音乐api,亲测可用,话不多说直接上代码最新音乐leturl=’https://c.y.qq.com/v8/fcg-bin…

  • POJ 2914 Minimum Cut 最小割图论

    POJ 2914 Minimum Cut 最小割图论

  • bios刷写工具_蓝天P750/P751编程器刷BIOS「建议收藏」

    bios刷写工具_蓝天P750/P751编程器刷BIOS「建议收藏」神舟ZX8-SP7是蓝天P751DM2模具,今天在WIN下刷BIOS成功刷黑,开始使用编程器刷BIOS,笔记本BIOS芯片由于是焊在主板上必须用夹子或者脱焊后用烧录座刷写,所以需要买编程器夹子。工具:优硕EZP-XPROV2、优硕SOP8编程器夹子。目标:神舟ZX8-SP7(P751DM2模具)准备工作:去蓝天镜像站下载对应的模具的BIOS蓝天镜像站:https://repo.palkeo.co…

  • pycharm怎么装第三方库jieba_pycharm安装配置教程

    pycharm怎么装第三方库jieba_pycharm安装配置教程一、测试环境测试机型:window10pycharm版本:2020.1.1专业版二、安装步骤1.打开pycharm,点击最上方菜单项中的File,并找到Setings如图:2.点击Setings,在Project中找到自己的项目(1),随后右边的显示框中会显示如图页面,点击ProjectInterpreter(2):3.点击之后就会出现如下图页面,中间表格中的Package表示你已经添加的包,Version表示当前版本,latestversion表示最新的版本。添加新.

  • Java多线程——基本概念「建议收藏」

    Java多线程——基本概念「建议收藏」线程和多线程程序:是一段静态的代码,是应用软件执行的蓝本进程:是程序的一次动态执行过程,它对应了从代码加载、执行至执行完毕的一个完整过程,这个过程也是进程本身从产生、发展至消亡的过程线程:是比进程更小的执行单位。进程在其执行过程中,可以产生多个线程,形成多条执行线索,每条线索,即每个线程也有它自身的产生、存在和消亡的过程,也是一个动态的概念主线程:(每个Java程序都有一个…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号