工学
单选题有n个独立的作业{1，2，..，n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（n>m）。对于多级调度问题，使用以下哪种贪心策略比较合适（）A 作业从小到大依次分配给空闲的机器B 作业从大到小依次分配给空闲的机器C 每个机器分配一样的作业数D 使用以上几种贪心策略都能找到最优解，所以都合适
题目
作业从小到大依次分配给空闲的机器
作业从大到小依次分配给空闲的机器
每个机器分配一样的作业数
使用以上几种贪心策略都能找到最优解，所以都合适
相似问题和答案
第1题：
若操作系统中有n个作业Ji(i=1，2，…，n)，分别需要Ti(i=1，2，…，n)的运行时间，采用(60)的作业调度算法可以使平均周转时间最短。
A．先来先服务
B．最短时间优先
C．响应比高者优先
D．优先级
解析：作业调度主要完成从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。常用的作业调度算法主要有以下几种。(1)先来先服务(FCFS)按作业到达的先后次序调度，它不利于短作业。作业平均周转时间=∑(作业完成时刻i-作业提交时刻i)/n个作业(2)最短作业优先(SJF)按作业的估计运行时间调度，估计运行时间短的作业优先调度。它不利于长作业，可能会使一个估计运行时间长的作业迟迟得不到服务。(3)响应比高者优先(HRN)综合上述两者，既考虑作业估计运行时间，又考虑作业等待时间，响应比HRN=(估计运行时间+等待时间)/估计运行时间。(4)定时轮转法(按时间片)适合作业不定的情况(5)优先数法根据作业的优先级别，优先级高者先调度。那么，怎样来衡量一个作业调度算法是否满足系统设计的要求呢?对于批处理系统，由于主要用于计算，因而对于作业的周转时间要求较高。从而作业的平均周转时间或平均带权周转时间被用来衡量调度程序的优劣。但对于分时系统和实时系统来说，平均响应时间又被用来衡量调度策略的优劣。(1)周转时间作业i的周转时间Ti为Ti=Tei-Tsi其中Tei为作业i的完成时间，Tsi为作业i的提交时间。对于被测定作业流所含有的n(n1)个作业来说，其平均周转时间为：一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分，分别为等待时间和执行时间，即Ti=Twi+Tri这里，Twi主要指作业i由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时间；Tri为作业的执行时间。(2)带权周转时间带权周转时间是作业周转时间与作业执行时间的比，即Wi=Ti/Tri对于被测定作业流所含有的n(n1)个作业来说，其平均带权周转时间为：根据以上分析，从直观上来说，采用最短作业优先的调度算法，可使得系统在同一时间内处理得作业个数最多，从而吞吐量也就大于其他调度方式。
第2题：
若操作系统中有n个作业Ji(i=1，2，…，，z)，分别需要Ti(i=1，2，…，n)的运行时间，采用______的作业调度算法可以使平均周转时间最短。
A．先来先服务
B．最短时间优先
C．响应比高者优先
D．优先级
A．
B．
C．
D．
解析：这是一道考查作业管理中作业调度算法性能衡量的试题。
先来先服务(FCFS)调度算法是指按照用户作业到达的先后顺序进行调度处理。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。
最短作业优先(SJF)调度算法是指对短作业优先调度的算法。作业调度程序每次是从后备作业队列中选择一个作业投入运行。该算法对于长作业可能会有一个较长的延迟时间。
响应比高者优先(HRN)调度算法是指调度时既考虑作业估计运行时间，又考虑作业等待时间，响应比是HRN=(估计运行时间+等待时间)/估计运行时问。
优先级调度是指根据作业的优先级别，优先级高者首先调度。
对于最短作业优先(SJF)调度算法可使系统在同一时问内处理的作业个数最多，即可以使平均周转时间最短。
第3题：
生产甲、乙、丙三种零件，需经L、M、N三个加工单元，加工单元L和M各有2台设备，加工单元N有1台设备，各设备月工作23天，每天作业8小时，开动率为90%，9月份各加工单元实际生产任务安排为：L——382小时，M——329小时，N——131小时。9月份三个加工单元的生产均衡状况是（ ）。
A．L加工单元能力富裕，N加工单元能力富裕，M加工单元能力不足
B．L加工单元能力不足，N加工单元能力不足，M加工单元能力富裕
C．N加工单元能力不足，L加工单元能力富裕，M加工单元基本满负荷
D．L加工单元能力不足，N加工单元能力富裕，M加工单元基本满负荷
第4题：
试题四（共15分）
阅读下列说明和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上处理。
【问题1)（9分）
(1)p[x][y][0]=1
(2)p[x][y][k]=p[x-a[k-1]][y][k-1]
(3)y- b[k-1]>=0
(4) p[x][y][n]==1或p[x][y][n]或p[x][y][n]!=0
(5)(x>=y)?x:y
【问题2】
(6) O(m2n)
【问题3】（4分）
(7)(1，1，2，2，1，1)
(8)15
第5题：
若操作系统中有n个作业Ji(i=1,2,…,n)，分别需要Ti(i=1,2,…,n)的运行时间，采用(23)的作业调度算法可以使平均周转时间最短。
A．先来先服务(FCFS)
B．最短作业优先(SJF)
C．响应比高者优先(HRN)
D．优先级
解析：这是一道考查作业管理中作业调度算法性能衡量的试题。先来先服务(FCFS)调度算法是指按照用户作业到达的先后顺序进行调度处理。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。最短作业优先(SJF)调度算法是指对短作业优先调度的算法。作业调度程序每次是从后备作业队列中选择一个作业投入运行。该算法对于长作业可能会有一个较长的延迟时间。响应比高者优先(HRN)调度算法是指调度时既考虑作业估计运行时间，又考虑作业等待时间，响应比是HRN=(估计运行时间+等待时间)/估计运行时间。优先级调度是指根据作业的优先级别，优先级高者首先调度。对于最短作业优先(SJF)调度算法可使系统在同一时间内处理的作业个数最多，即可以使平均周转时间最短。
第6题：
阅读下列算法说明和流程图，根据要求回答问题1～问题3。
[说明]
某机器上需要处理n个作业job1，job2，…，jobn，其中：
(1)每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值P[i]和最后期限值d[i]；
(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；
(3)job1～jobn的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；
(4)如果作业jobi在其期限之内完成，则获得收益p[i]；如果在其期限之后完成，则没有收益。
为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图3-25是基于贪心策略求解该问题的流程图。
(1)整型数组J[]有n个存储单元，变量k表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k)里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。
(2)为了便于在数组J中加入作业，增加一个虚拟作业job0，并令d[0]=0，J[0]=0。
(3)算法大致思想是：先将作业job1的编号1放入J[1]，然后，依次对每个作业jobi(2≤i≤n)进行判定，看其能否插入到数组J中。若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列；否则不插入。
jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。
(4)流程图中的主要变量说明如下。
i：循环控制变量，表示作业的编号；
k：表示在期限内完成的作业数；
r：若jobi能插入数组J，则其在数组J中的位置为r+1；
q：循环控制变量，用于移动数组J中的元素。
请将图3-25中的(1)～(3)空缺处的内容填写完整。
”。换言之数组J中的作业J[i](1≤i≤k)是在其期限之前完成的作业且
。由图3-25给出的算法流程图可知主循环内嵌套了两个循环第1个循环判断当前考虑的作业i应该插入到J中的什么位置用循环控制变量r表示当前考虑的J中的作业。使用虚拟作业J[0]允许作业较方便地插入到第1个位置。为了保证J中的作业期限按升序排序作业J[r]若比作业i的期限大则循环控制变量r要自减因此(2)空缺处所填写的内容是d[J[r]]＞d[i]。
d[J[r]]与r的关系只有两种：d[J[r]]＞r表示还可能在J[1]与J[r]之间插入作业“d[J[r]]=r表示不可以在J[1]～J[r]之间插入作业i。d[J[r]]r的情况不会存在因为J中若有r个作业那么最后一个作业的期限不可能小于r。当作业i大于等于作业J[r]的期限时此时找到了作业i插入的位置即r+1。第2个循环的作用是将作业J[r+1]……J[k]依次往后移动此处用插入排序算法的思想。最后把作业i插入到 J[r+1]处因此(3)空缺处所填写的内容是J[r+1]=i(或J[q+1]=i)。这是一道考查贪心算法的流程图分析的试题。(1)空缺处表示第2个作业到第n个作业的主循环的条件判断，由于i是循环控制变量，因此(1)空缺处所填写的内容是i=h。 注意到题干中给出的关键信息“J[1..k)存储所有能够在期限内完成的作业编号，数组J[1..k]里的作业按其最后期限非递减排序，即
”。换言之，数组J中的作业J[i](1≤i≤k)是在其期限之前完成的作业，且。由图3-25给出的算法流程图可知，主循环内嵌套了两个循环，第1个循环判断当前考虑的作业i应该插入到J中的什么位置，用循环控制变量r表示当前考虑的J中的作业。使用虚拟作业J[0]，允许作业较方便地插入到第1个位置。为了保证J中的作业期限按升序排序，作业J[r]若比作业i的期限大，则循环控制变量r要自减，因此(2)空缺处所填写的内容是d[J[r]]＞d[i]。
d[J[r]]与r的关系只有两种：d[J[r]]＞r，表示还可能在J[1]与J[r]之间插入作业“d[J[r]]=r，表示不可以在J[1]～J[r]之间插入作业i。d[J[r]]r的情况不会存在，因为J中若有r个作业，那么最后一个作业的期限不可能小于r。当作业i大于等于作业J[r]的期限时，此时找到了作业i插入的位置，即r+1。第2个循环的作用是将作业J[r+1]……J[k]依次往后移动，此处用插入排序算法的思想。最后把作业i插入到 J[r+1]处，因此(3)空缺处所填写的内容是J[r+1]=i(或J[q+1]=i)。
第7题：
阅读下列说明和图，回答问题1至问题3，将解答填入对应栏内。
【说明】
某机器上需要处理n个作业．job1，job2，…，jobn，其中：
(1)每个作jobi(1≤i≤n)的编号为i，jobi有一个收益值p[i]和最后期限值d[i]小
(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；
(3)job1～jobn的收益值呈非递增顺序排列，即p[1)≥P[2]≥…[n)：
(4)如果作业jobi在其期限之内完成，则获得收益9[i]；如果在其期限之后完成，则没有收益。
为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4*1是基于贪心策略求解该问题的流程图。
(1)整型数组J[]有n个存储单元，变量k众表示在期限之内完成的作业J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。
(2)为了便于在数组J中加入作业，增加一个虚拟作业Job0，并令d[0]=0，j[0]=0。
(3)算法大致思想：先将作业．job1的编号1放入J[1]，然后，依次对每个作业．jobi (2≤i≤n)进行判定，看其能否插入到数组J中。若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列；否则不插入。
jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。
(4)流程图中的主要变量院明如下。
i：循环控制变量，表示作业的编号；
k：表示在期限内完成的作业数：
r：若．jobi能插入数组J，则其在数组了中的位置为r+1：
q：循环控制变量，用于移动数组J中的元素。
请填充图4-1中的空缺(1)、(2)和(3)处。
(1)i<=n (2)d[J[r]]>d[i] (3)J[r+1]=i，或J[q+1]=i
第8题：
A作业数量，机器数量，目标函数，车间类型
B作业数量，机器数量，车间类型，目标函数
C机器数量，作业数量，目标函数，车间类型
D机器数量，作业数量，车间类型，目标函数
第9题：
试题四(共15 分)
阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。
【说明】
某机器上需要处理 n 个作业 job1, job2, …, jobn，其中：
(1) 每个作业jobi(1≤i≤n)的编号为 i， jobi有一个收益值 p[i]和最后期限值 d[i]；
(2) 机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，
一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；
(3) job1～jobn 的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；
(4) 如果作业jobi在其期限之内完成，则获得收益 p[i]；如果在其期限之后完成，
则没有收益。
为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图 4-1 是基于贪
心策略求解该问题的流程图。
(1) 整型数组 J[]有 n 个存储单元，变量 k 表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号， 数组 J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤ … ≤d[J[k]]。
(2) 为了方便于在数组 J 中加入作业，增加一个虚拟作业 job0，并令d[0] = 0， J[0] = 0。
(3) 算法大致思想：先将作业 job1 的编号 1 放入 J[1]，然后，依次对每个作业 jobi (2≤i≤n)进行判定，看其能否插入到数组 J 中，若能，则将其编号插入到数组 J 的适当位置，并保证 J 中作业按其最后期限非递减排列，否则不插入。 jobi能插入数组 J 的充要条件是：jobi 和数组 J 中已有作业均能在其期限之内完成。
(4) 流程图中的主要变量说明如下：
i：循环控制变量，表示作业的编号；
k：表示在期限内完成的作业数；
r：若jobi能插入数组 J，则其在数组 J 中的位置为 r+1；
q：循环控制变量，用于移动数组 J 中的元素。
【问题 1】 （9 分）
请填充图4-1 中的空缺(1)、(2)和(3)处。
【问题 2】(4 分)
假设有 6 个作业 job1, job2, …, job6；
完成作业的收益数组 p=(p[1],p[2],p[3],p[4],p[5],p[6]) = (90,80,50,30,20,10)；
每个作业的处理期限数组 d=(d[1],d[2],d[3],d[4],d[5],d[6]) = (1,2,1,3,4,3)。
请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列 (4)
（按作业处理的顺序给出） ，得到的总收益为 (5) 。
【问题 3】(2 分)
对于本题的作业处理问题， 用图 4-1的贪心算法策略， 能否求得最高收益？ (6) 。
用贪心算法求解任意给定问题时，是否一定能得到最优解？ (7) 。
第10题：
设Xi(i＝1，2，…，n)为n个相互独立的随机变量，则下列结论成立的是( )。
A．若Xi(i＝1，2，…，n)服从正态分布，且分布参数相同，则
服从正态分布
B．若Xi(i＝1，2，…，n)服从指数分布，且λ相同，则服从正态分布
C．若Xi(i＝1，2，…，n)服从[a，b]上的均匀分布，则服从正态分布
D．无论Xi(i＝1，2，…，n)服从何种相同的分布，其均值都服从正态分布
解析：中心极限定理指出，无论共同的分布是什么，只要随机变量的个数n相当大时，的分布总近似于正态分布。