江苏龙网

  1. 首页 > 人文 > >

产业气象站 算法园地|南京大学陈道蓄教授：调度问题中的算法


产业气象站 算法园地|南京大学陈道蓄教授：调度问题中的算法
文章图片
产业气象站 算法园地|南京大学陈道蓄教授：调度问题中的算法
文章图片
陈道蓄
南京大学教授、博士生导师
曾任南京大学计算机系主任 。 近年来积极投入计算机专业基础课改革以及计算思维普及 ， 因此获得中国计算机学会杰出教育奖与南京大学教学终身成就奖 。
说到“调度” ， 人们往往会想到交通运输部门的运行安排 ， 也会想到企业中复杂的生产任务安排 。 其实 ， 日常生活中也经常面临着多个事项需要合理安排；只不过任务数不大 ， 也不涉及明显的经济指标限制 ， 人们凭经验就足以应付 ， 很少会联想到“算法” 。 当需要解决的任务数增加 ， 且包含相互依赖关系时 ， 算法可以帮助我们顺利有效地完成任务 。
单纯依赖关系约束下的任务调度
我们从仅考虑任务间的依赖约束开始 。 如果任务X只能在另外某个任务Y完成后才能开始 ， 我们就说X依赖Y 。 下面来看一个简单的例子 。
同学们打算在教室里组织一场联欢活动 ， 还准备自己动手包饺子 。 他们拟定了一张准备工作任务表 ， 包含所有任务事项、每项任务耗时、任务间依赖关系（注意：只需列出直接依赖关系 ， 而间接依赖关系自然地隐含在其中） 。 管理上通常将这些任务的集合称为一个“项目” 。 任务列表见表1 。
产业气象站 算法园地|南京大学陈道蓄教授：调度问题中的算法
文章图片
表1为准备一个联欢活动涉及的各项任务及其关系示例
有些任务之间没有依赖关系 ， 执行顺序无关紧要 ， 如果有多个执行者 ， 这样的任务就可以并行 。 这里说的“调度” ， 就是要给每项任务分配一个不同的序号 ， 表示它们执行的顺序 ， 满足：如果任务X依赖任务Y ， 则X的序号就要大于Y的序号；如果两个任务之间没有依赖关系 ， 则对它们的序号关系没有要求 。 从数学上看 ， 原来所有任务间的依赖关系确定了一个“偏序” ， 即并非任意两个任务都必须“有先后”（称为“可比”） 。 调度就是要在此基础上生成一个“全序” ， 即任何两个任务皆“可比” ， 对任意两个原来就“可比”的任务 ， 新关系与原关系保持一致 。 换句话说 ， 如果按照这个序号串行执行 ， 一定满足原来要求的依赖关系 。 这个问题被称为“拓扑排序”问题 。 读者应该注意到 ， 如果只要解决拓扑排序问题 ， 我们并不需要考虑上述例子中每项子任务的耗时 。
我们可以建立一个有向图模型 。 图中每个节点表示一个任务 ， 节点X和Y之间存在从X到Y的有向边（X→Y）当且仅当对应的任务X直接依赖于任务Y 。 上述例子的图模型如图1所示 。 图中节点名称采用表1中的任务名称 。 我们暂时不考虑任务的耗时 。
在这个模型上解决拓扑排序问题的思路非常简单 。 我们要给每个节点分配一个序号 ， 这需要遍历所有节点 。 根据问题要求 ， 如果任务X依赖任务Y（无论是直接还是间接） ， 分配给节点X的序号必须大于Y的序号 。 在图模型中存在的任意一个简单有向通路表明任务i-1依赖任务i（1＜i≤k） 。 这条通路可以看作一条“依赖链” ， 显然通路中的节点被分配的序号是严格递减的 。
产业气象站 算法园地|南京大学陈道蓄教授：调度问题中的算法
文章图片
图1与表1示例数据对应的有向图
图节点遍历常用算法有两种：深度优先与广度优先 。 我们在本系列文章中前面讨论走迷宫算法时介绍过深度优先算法（DFS） 。 它的基本步骤如下（这里假设从起始点一定可通达所有节点）：①选择一个起始点 ， 并将其作为第一个“当前节点” ， 设置状态为“已访问” 。 ②如果当前节点所有的相邻节点都是“已访问”状态 ， 结束从当前节点开始的遍历子过程 ， 退出（回溯） 。 如果当前节点就是起始点 ， 则整个遍历完成 。 ③取当前节点相邻节点中的一个尚未访问过的节点w作为新的“当前节点” ， 设置状态为“已访问” ， 从w开始递归执行本过程（即上述第2步） 。


推荐阅读


上一篇：问董秘|公...，投资者提问：请问新能源汽车动力电池系统和热管理系统会使用哪些精细化学品

下一篇：晨财经|除了关店，还有哪些大招？，ZARA等快时尚品牌遇“寒流”