![](https://lstatic.shangxueba.com/sxbzda/h5/images/m_q_title.png)
问题描述:用两台处理机A和B处理n个作业.设第i个作业交给机器A处理时需要时间ai,若由机器B来处
![问题描述:用两台处理机A和B处理n个作业.设第i个作业交给机器A处理时需要时间ai,若由机器B来处理](https://img2.soutiyun.com/ask/2021-01-04/978631227850724.png)
算法设计:对于给定的两台处理机A和B处理n个作业,找出一个最优调度方案,使2台机器处理完这n个作业的时间最短.
数据输入:由文件input.txt提供输入数据.文件的第1行是1个正整数n,表示要处理n个作业.在接下来的2行中,每行有n个正整数,分别表示处理机A和B处理第i个作业需要的处理时间.
结果输出:将计算出的最短处理时间输出到文件output.txt.
![](https://lstatic.shangxueba.com/sxbzda/h5/images/tips_org.png)
算法设计:对于给定的两台处理机A和B处理n个作业,找出一个最优调度方案,使2台机器处理完这n个作业的时间最短.
数据输入:由文件input.txt提供输入数据.文件的第1行是1个正整数n,表示要处理n个作业.在接下来的2行中,每行有n个正整数,分别表示处理机A和B处理第i个作业需要的处理时间.
结果输出:将计算出的最短处理时间输出到文件output.txt.
第1题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业,而且作业处理是不可中断的,每个作业只能被处理一次。现要找出一个最优调度方案,使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
算法步骤:
(1)确定候选解上界为R短的单台处理机处理所有作业的完成时间m,
(2)用p(x,y,k)=1表示前k个作业可以在A用时不超过x且在B用时不超过y时间 内处理完成,则p(x,y,k)=p(x-ak,y,k-1)||p(x,y-bk,k-1)(||表示逻辑或操作)。
(3)得到最短处理时问为min(max(x,y))。
【C代码】
下面是该算法的C语言实现。
(1)常量和变量说明
n: 作业数
m: 候选解上界
a: 数组,长度为n,记录n个作业在A上的处理时间,下标从0开始
b: 数组,长度为n,记录n个作业在B上的处理时间,下标从0开始
k: 循环变量
p: 三维数组,长度为(m+1)*(m+1)*(n+1)
temp: 临时变量
max: 最短处理时间
(2)C代码
include<stdio.h>
int n, m;
int a[60], b[60], p[100][100][60];
void read(){ /*输入n、a、b,求出m,代码略*/}
void schedule(){ /*求解过程*/
int x,y,k;
for(x=0;x<=m;x++){
for(y=0;y<m;y++){
(1)
for(k=1;k<n;k++)
p[x][y][k]=0;
}
}
for(k=1;k<n;k++){
for(x=0;x<=m;x++){
for(y=0;y<=m;y++){
if(x - a[k-1]>=0) (2) ;
if( (3) )p[x][y][k]=(p[x][y][k] ||p[x][y-b[k-1]][k-1]);
}
}
}
}
void write(){ /*确定最优解并输出*/
int x,y,temp,max=m;
for(x=0;x<=m;x++){
for(y=0;y<=m;y++){
if( (4) ){
temp=(5) ;
if(temp< max)max = temp;
}
}
}
printf("\n%d\n",max),
}
void main(){read();schedule();write();}
【问题1】 (9分)
根据以上说明和C代码,填充C代码中的空(1)~(5)。
【问题2】(2分)
根据以上C代码,算法的时间复杂度为(6)(用O符号表示)。
【问题3】(4分)
考虑6个作业的实例,各个作业在两台处理机上的处理时间如表4-1所示。该实例的最优解为(7),最优解的值(即最短处理时间)为(8)。最优解用(x1,x2,x3,x4,x5,x6)表示,其中若第i个作业在A上赴理,则xi=l,否则xi=2。如(1,1,1,1,2,2)表示作业1,2,3和4在A上处理,作业5和6在B上处理。
第2题
作业P1:I/O2(30毫秒) CPU(10毫秒) I/O1(30毫秒) CPU(10毫秒)
作业P2:I/O1(20毫秒) CPU(20毫秒) I/O2(40毫秒)
作业P3:CPU(30毫秒) I/O1(20毫秒)
在对于其他辅助操作时间可以忽略不计的假设下,作业P1,P2,P3从投入到完成所用的时间分别是 (21题)毫秒, (22题)毫秒和 (23题)毫秒。三个作业从投入运行到全部完成,CPU的利用率约为 (24题)%,:U01的利用率约为 (25题)%。
假定在系统中仅有这三个作业投入运行,各设备的利用率指该设备的使用时间同作业进程全部完成所占用最长时间的比率。
A.60
B.67
C.70
D.78
E.80
第5题
作业P1:IO2(30毫秒)CPU(10毫秒)IO1(30毫秒)CPU(10毫秒)
作业P2:IO1(20毫秒)CPU(20毫秒)IO2(40毫秒)
作业P3:CPU(30毫秒)IO1(20毫秒)
在对于其他辅助操作时间可以忽略不计的假设下,作业P1,P2,P3从投入到完成所用的时间分别是(55)毫秒,(56)毫秒和(57)毫秒。三个作业从投入运行到全部完成,CPU的利用率约为(58)%,IO1的利用率约为(59)%。
假定在系统中仅有这三个作业投入运行,各设备的利用率是指该设备的使用时间同作业进程全部完成所占用最长时间的比率。
A.60
B.67
C.70
D.78
E.80
第7题
A.一次开挖到设计标高
B.可避免汽车在坑下装运作业
C.不必设专用垫道
D.挖掘宽度可不受机械最大挖掘半径的限制
E.机身稳定性好
第10题
作业台班数不足4h按( )收取机械租赁费。(单选题)
A.0.5台班
B.1个台班
C.不收取
D.实际台班数
根据租赁合同范本条款,租赁期间机械的维修保养费用应由( )承担。(单 选题)A.承租方
B.出租方
C.双方共同
D.第三方
项目经理部必须建立的机械租赁管理的台账,有( )。(多选题)A.机械租赁台账
B.租赁机械结算台账
C.租赁机械使用月报表
D.租赁合同台账
E.单机核算台账
F.租赁网络台账
机械租赁合同范本中,合同条款第一条包含了( )等内容。(多选题)A.租赁机械用途
B.规格型号
C.数量
D.租赁形式
E.租赁单价
设备租用期间,因不可预见的自然灾害所造成的经济损失由承租方负责。( ) (判断题)
请帮忙给出每个问题的正确答案和分析,谢谢!
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!