网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
有n个独立的作业{1，2，..，n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（n>m）。对于多级调度问题，使用以下哪种贪心策略比较合适（）
- A、作业从小到大依次分配给空闲的机器
- B、作业从大到小依次分配给空闲的机器
- C、每个机器分配一样的作业数
- D、使用以上几种贪心策略都能找到最优解，所以都合适
参考答案
更多 “有n个独立的作业{1，2，..，n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（nm）。对于多级调度问题，使用以下哪种贪心策略比较合适（）A、作业从小到大依次分配给空闲的机器B、作业从大到小依次分配给空闲的机器C、每个机器分配一样的作业数D、使用以上几种贪心策略都能找到最优解，所以都合适” 相关考题
考题
在约翰逊算法中应被安排在最后完成的作业是哪种作业:()
A.两台机器上总的加工时间最长。B.两台机器上总的加工时间最短。C.第一台机器上的加工时间最长。D.第二台机器上的加工时间最长。E.第二台机器上的加工时间最短。
考题
Conway等人提出了车间排序问题的通用模型,即:n／m／A／B,其中,n表示________,m表示________,A表示________,B表示________。( )
A作业数量，机器数量，目标函数，车间类型B作业数量，机器数量，车间类型，目标函数C机器数量，作业数量，目标函数，车间类型D机器数量，作业数量，车间类型，目标函数
考题
阅读下列算法说明和流程图，根据要求回答问题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)空缺处的内容填写完整。
考题
一个有两个作业管理进程的批处理系统，作业调度采用最高响应比优先的算法，进程调度采用基于优先数(优先数大表示优先级别高)的算法。有以下作业序列：作业F的运行结束时间为(26)(假定在作业运行期间，除了有空闲的作业管理进程以外，系统不进行调度工作)。A．14：50B．15：30C．13：40D．13：10
考题
阅读下列说明和图，回答问题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)处。
考题
一个有两个作业管理进程的批处理系统，作业调度采用基于优先数(优先数大表示优先级别高)的算法，进程调度采用短作业优先的算法(按剩余运行时间计算作业的长短)。有以下作业序列：作业F的运行结束时间为(23)(假定在作业运行期间，除了有空闲的作业管理进程以外，系统不进行调度工作)A．14：50B．15：30C．13：40D．13：10
考题
若操作系统中有n个作业Ji(i=1,2,…,n)，分别需要Ti(i=1,2,…,n)的运行时间，采用(23)的作业调度算法可以使平均周转时间最短。A．先来先服务(FCFS)B．最短作业优先(SJF)C．响应比高者优先(HRN)D．优先级
考题
作业管理的主要任务包括作业输入、作业处理和作业输出，其中作业处理的工作是(15)。在操作系统中，对批处理作业的控制方式是(16)。若系统中有四个作业，它们的到达时间、运行时间、开始时间、完成时间和周转时间如下表所示，则该系统采用的作业调度算法是(17)。A．作业控制B．作业调度C．作业控制与作业调度D．作业控制，作业调度与作业后备
考题
试题四(共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) 。
考题
试题四（共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代码includestdio.hint 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；ym；y++）{（1）for（k=1；kn；k++）p[x][y][k]=0；}}for（k=1；kn；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上处理。
考题
按照事先的加工要求，由单个作业员在多台机器上完成多种产品的生产。但是，插单的前提是必须保证前一张订单已经完成。此类作业宜采用哪种作业方式（）A、全工序自理的作业方法B、多品种自理的作业方法C、单人多机的作业方法D、单一工序的单人操作
考题
若操作系统中有n个作业Ji（i=1，2，…，n），分别需要Ti（i=1，2，…，n）的运行时间，采用（）的作业调度算法可以使平局周转时间最短。A、先来先服务B、最短作业优先C、响应比高者优先D、优先级
考题
有关作业管理的下述描述中，（）是正确的。A、系统现有空闲资源能满足被选作业的资源要求是选择作业进人主存的一个必要条件B、作业与进程是一一对应的C、作业调度选中一个作业后，与作业相关的进程就处于运行状态D、在兼有批处理和分时的计算机系统中，往往把终端作业作为前台作业，把批处理作业作为后台作业E、批处理作业是在输人井中等待处理的
考题
若n=4，在机器M1和M2上加工作业i所需的时间分别为ai和bi，且（a1，a2，a3，a4）=（4，5，12，10），（b1，b2，b3，b4）=（8，2，15，9）求4个作业的最优调度方案，并计算最优值。
考题
检查工序活动的结果，一旦发现问题，应采取的措施（）A、继续作业活动，在作业过程中解决问题B、无视问题，继续作业活动C、停止作业活动进行处理，直到符合要求D、停止作业活动进行处理，不做任何处理
考题
问答题若n=4，在机器M1和M2上加工作业i所需的时间分别为ai和bi，且（a1，a2，a3，a4）=（4，5，12，10），（b1，b2，b3，b4）=（8，2，15，9）求4个作业的最优调度方案，并计算最优值。
考题
单选题按照事先的加工要求，由单个作业员在多台机器上完成多种产品的生产。但是，插单的前提是必须保证前一张订单已经完成。此类作业宜采用哪种作业方式（）A
全工序自理的作业方法B
多品种自理的作业方法C
单人多机的作业方法D
单一工序的单人操作
考题
单选题若操作系统中有n个作业Ji（i=1，2，…，n），分别需要Ti（i=1，2，…，n）的运行时间，采用（）的作业调度算法可以使平局周转时间最短。A
先来先服务B
最短作业优先C
响应比高者优先D
优先级
热门标签
最新试卷