回溯算法求解：批处理作业调度（双机）问题要求确定这n个作业的最优作业调度方案使其MFT最小。这等价于求使得所有作业的完成时间之和最小的调度方案。现设有三个作业和两台设备，作业任务的处理时间为（a0,a1,a2）=(2,3,2)和（b0,b1,b2）=(1,1,3)
设有三个作业和两台设备，作业任务的处理时间为（a0,a1,a2）=(2,3,2)和（b0,b1,b2）=(1,1,3)。这三个作业有6种可能的调度方案：(0,1,2),(0,2,1),(1,0,2), (1,2,0),(2,0,1),(2,1,0),它们相应的完成时间之和分别是19,18,20,21,19,19。其中，最佳调度方案S=(0,2,1)。在这一调度方案下，f0(S)=3，f1(S)=7，f2(S)=8，FT=3+7+8=18。求解这一问题没有有效的约束函数，但可以使用最优解的上界值U进行剪枝。如果对于已经调度的作业子集的某种排列，所需的完成时间和已经大于迄今为止所记录下的关于最优调度方案的完成时间和的上界值U,则该分枝可以剪去。
举一反三
- 有三个作业A，B，C。它们的到达时间分别是0, 1, 3 ；要求服务时间分别是：4, 2, 1。若采用最高时间片轮转调度算法，时间片为2。作业A,作业B和作业C的完成时间是（ ） A: 4, 2, 6 B: 4， 6, 7 C: 6, 7, 4 D: 6, 4, 7
- 假设有五个作业其所需运行时间和截止时刻为：[tex=27.714x1.214]hEvo48Qy08XfNEYiQCHd1201T9qthZaH9hK3pIO96Qes1Op6K9W6kFLqFHF5BdCrWKxsGRyfzs1WA9OZGp2vQIIgV1gm6vYlTJ2pB07fP1mXEQft18KJVtMrOn+ysVwFxzkn3gbOP9y4MEG87UW9kg==[/tex]。当作业调度的顺序为作业3、作业1、作业4、作业2、作业5(从时刻0开始)时找出任一作业的最大拖延。对于调度顺序为作业5、作业3、作业3、作业1、作业2时回答同样的问题。
- 单道批处理系统中，下列三个作业采用先来先服务调度算法和最高响应比优先算法进行调度，哪一种算法性能较好？请完成下表： 作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 1 2 3 10 : 00 10 : 10 10 : 25 2 : 00 1 : 00 0 : 25 平均作业周转时间= 平均作业带权周转时间W =
- 有以下三个作业,分别采用先来先服务和短作业优先作业调度算法。分别计算它们的作业平均周转时间。 作业 到达时间 所需CPU时间(分) 1 0.0 8 2 0.4 4 3 1.0 1
- 【完型填空】作业调度是从处于( 1 )状态的队列中选取作业投入运行,( 2 ) )是指作业进入系统到作 业完成所经过的时间间隔,( 3 ) )算法不适合作业调度
内容
- 0
若某系统中的所有作业同时到达,那么()作业调度算法是使作业平均周转时间为最小的作业调度算法。
- 1
现有A、B、C、D 4个作业同时进入系统，预计它们的执行时间分别为10、6、2、4（单位：min）。 现采用 （1）采用先来先服务调度算法(按A、B、C、D)； （2）采用优先级调度算法，A、B、C、D 4个作业的优先级分别为3、4、2、1，其中4为最高优先级，1为最低优先级。 对于上述每种调度算法，写出执行序列，并计算每个作业的周转时间及其平均周转时间（不考虑作业切换开销）。
- 2
有5个批处理作业（A、B、C、D、E）几乎同时到达，估计的运行时间分别为2、4、6、8、10分钟，它们的优先级分别为1、2、3、4、5（1为最低优先级）。对下面的每种调度算法，分别计算作业的平均周转时间。（1）最高优先级优先。（2）时间片轮转（时间片为2分钟）。（3）FIFO（作业的到达顺序为C、D、B、E、A）（4）短作业优先。
- 3
假定一个系统中的所有作业同时到达,那么使作业平均周转时间为最小的作业调度算法是 ( )调度算法
- 4
有三个作业A，B，C。它们的到达时间分别是0, 1, 2 ；要求服务时间分别是：8, 4, 1。若采用最高响应比优先调度算法。当8时刻作业A运行结束时，作业B和作业C的响应比的值是（ ） A: 4, 1 B: 3.5， 6 C: 1.75, 7 D: 2.75, 7