算法设计与分析课程大作业

题

学院名称：专业名称：计算机科学与技术

计算机与信息工程学院

目作业调度问题及算法分析

算法分析课程设计

目录

《算法设计与分析》课程大作业 ................................................................. 错误！未定义书签。 一．动态规划算法解决流水作业调度 ........................................................................................... 3

1、问题描述 ............................................................................................................................. 3 2、算法分析 ............................................................................................................................. 3 3. 算法的描述 ......................................................................................................................... 4 4、部分算法实现 ..................................................................................................................... 5 5. 运行结果 ............................................................................................................................. 6 6、时空效率分析 ..................................................................................................................... 6 二．贪心算法解多机调度问题 ....................................................................................................... 6

1、问题描述 ............................................................................................................................. 6 2、算法分析 ............................................................................................................................. 6 3.部分算法实现 ....................................................................................................................... 7 4.计算复杂性分析 .................................................................................................................... 8 5. 运行结果 ............................................................................................................................. 8 三．回溯法解决批作业调度问题 ................................................................................................... 9

1.问题描述 ............................................................................................................................... 9 2.算法思想 ................................................................................................................................ 9 3. 部分算法实现 ................................................................................................................... 10 4.运行结果 .............................................................................................................................. 11 5.时间复杂性分析 .................................................................................................................. 11 四．作业调度算法比较 ................................................................................................................. 12 五．课程学习总结 ......................................................................................................................... 12

算法分析课程设计

摘要：

在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。 关键词：作业调度；动态规划；贪心算法；回溯法；

一．动态规划算法解决流水作业调度

1、问题描述

给定n个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i在机器j上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n个作业。

2、算法分析

直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。

在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最

算法分析课程设计

短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 由流水作业调度问题的最优子结构性质可知，

T(N,0)?min{ai?T(N?{i},bi)}1?i?n（1）

T(S,t)?min{ai?T(S?{i},bi?max{t?ai,0})}i?S（2）

从公式（1）可以看出，该问题类似一个排列问题，求N个作业的最优调度问题，利用其子结构性质，对集合中的每一个作业进行试调度，在所有的试调度中，取其中加工时间最短的作业做为选择方案。将问题规模缩小。

公式（2）说明一般情况下，对作业集S进行调度，在M2机器上的等待时间，除了需要等该部件在M1机器上完成时间，还要冲抵一部分原来的等待时间，如果冲抵已成负值，自然仍需等待M1将作业做完，所以公式取max{t-ai,0}。

3.算法的描述

从分析可知，流水作业调度问题一定存在满足Johnson法则的最优调度，且容易由下面的算法确定。 流水作业调度问题的Johnson算法： （1）令N1?{i|t[i,1]?t[i,2]},N2?{i|t[i,1]?t[i,2]}；

（2）将中作业依的非减序排列；将中作业依的非增序排列； 作业接种作业构成满足Johnson法则的最优调度。