没有合适的资源？快使用搜索试试~ 我知道了~

首页Johnson（流水作业调度的最优算法）

Johnson（流水作业调度的最优算法）

Johnson

4星 · 超过85%的资源需积分: 48 101 下载量 3 浏览量更新于2023-03-03 7 收藏 50KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

11页

Johnson（流水作业调度的最优算法），算法思想基于动态规划，里面包含了公式的推导与poj例题的简单实现的代码

资源详情

资源推荐

Johnson 法则——流水作业调度——动态规划

转载自：凌逸轩的百度 blog

Johnson 法则——流水作业调度——动态规划

流水作业调度问题（不能直接使用动态规划法的例子）

流水作业调度的定义：

设有 n 个作业，每一个作业 i 均被分解为 m 项任务:

Ti1, Ti2, ┅ , Tim(1≤i≤n，故共有 n×m 个任务)，

要把这些任务安排到 m 台机器上进行加工。

如果任务的安排满足下列 3 个条件，

则称该安排为流水作业调度：

1. 每个作业 i 的第 j 项任务 Tij (1≤i≤n, 1≤j≤m)

只能安排在机器 Pj 上进行加工；

2. 作业 i 的第 j 项任务 Tij(1≤i≤n, 2≤j≤m)的开始加工时间

均安排在第 j-1 项任务 Ti,j-1 加工完毕之后；

(任何一个作业的任务必须依次完成，前一项任务完成之后才能开始着手下一项任务)

3. 任何一台机器在任何一个时刻最多只能承担一项任务。

最优流水作业调度：

设任务 Tij 在机器 Pj 上进行加工需要的时间为 tij。

如果所有的 tij (1≤i≤n, 1≤j≤m)均已给出，

要找出一种安排任务的方法，

使得完成这 n 个作业的加工时间为最少。

这个安排称之为最优流水作业调度。

完成 n 个作业的加工时间：

从安排的第一个任务开始加工, 到最后一个任务加工完毕，

其间所需要的时间。

优先调度：

允许优先级较低的任务在执行过程中被中断，

转而去执行优先级较高的任务。

非优先调度：

任何任务一旦开始加工，就不允许被中断，

直到该任务被完成。

流水作业调度一般均指的是非优先调度。

非优先调度可看成是特殊的优先调度：

所有任务的优先级均相同。

7 5 8

e.g. （tij）= 2 2 6

0 7 4

注意：tij 为 0 表示作业 i 无须在机器 Pj 上进行加工、

即该道工序可以省略。

已经证明，当机器数(或称工序数)m≥3 时，

流水作业调度问题是一个 NP-hard 问题（e.g 分布式任务调度）。

（粗糙地说，即该问题至少在目前

基本上没有可能找到多项式时间的算法。）

∴ 只有当 m=2 时，该问题可有多项式时间的算法。

为方便起见，记 ti1 为 ai（作业 i 在 P1 上加工所需时间），

ti2 为 bi（作业 i 在 P2 上加工所需时间）。

当机器 P1 为空闲即未安排任何加工任务时，

则任何一个作业的第一个任务（第一道工序）

都可以立即在 P1 上执行，无须任何先决条件。

因此容易知道，

必有一个最优调度使得在 P1 上的加工是无间断的。

实际上，如某个最优调度 π 在 P1 上安排的加工是有间断的，

则我们可以把所有在 P1 上出现间断处的任务的

开始加工时间提前，使得在 P1 上的加工是无间断的；

而在 P2 上仍按 π 原先的安排。

把这样调整之后的调度记作为 π’。

由于在调度 π’下，任何一个任务在 P1 上加工的结束时间

不晚于在调度 π 下的结束时间，故调度 π’

不会影响在 P2 上进行加工的任何一个任务的开始时间。

由于调度 π’在 P1 上的结束时间早于调度 π，

在 P2 上的结束时间与调度 π 相同，而 π 又是最优调度，

所以 π’也是最优调度。由此我们得到：

一定有一个最优调度使得在 P1 上的加工是无间断的。

另外，也一定有一个最优调度使得在 P2 上的加工空闲时间

（从 0 时刻起算）为最小，

同时还满足在 P1 上的加工是无间断的。（证明留作作业）

因此，如果我们的目标是只需找出一个最优调度，

剩余10页未读，继续阅读

流水车间作业调度算法

文件夹包含一些流水车间作业调度算法，启发式算法有cds,johnson,neh,palmer,ra,neh,moore等，智能算法有遗传算法，还包含绘制甘特图、生成测试数据的代码等。

基于python的流水车间作业调度算法.zip

文件夹包含一些流水车间作业调度算法，有cds,johnson,neh,palmer,ra,neh,moore等，智能算法有遗传算法，还包含绘制甘特图、生成测试数据的代码等。

流水作业调度问题与Johnson法则

atopoxo

粉丝: 3
资源: 6

上传资源快速赚钱

我的内容管理收起

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

会员权益专享

Johnson（流水作业调度的最优算法）

流水车间作业调度算法

基于python的流水车间作业调度算法.zip

流水作业调度问题与Johnson法则

基于python的流水车间作业调度算法

动态规划之流水作业调度问题

文件夹包含一些流水车间作业调度算法,有cds,johnson,neh,palmer,ra,neh,moore等,

流水作业调度 动态规划 C++

贪心算法多机调度 结论

Johnson 全源最短路径算法

多机调度算法python

johnson-trotter算法1234

Edmonds-Johnson算法

详细介绍一下Johnson算法

约翰逊算法matlab

SPFA 算法和Bellman-Ford 算法与Dijkstra 算法、Floyd 算法有什么异同以及创新性改进或应用

经过多个点的最短路径算法

gilbert-johnson-keerthialgorithm

用c语言写出最短路径的几种算法

移动机器人路径规划算法有哪些

介绍最短路径算法的发展历程

会员权益专享

最新资源

流水作业调度动态规划 C++

贪心算法多机调度结论