Johnson算法实现流水作业最优调度

全栈程序员-站长 • 2026年3月17日上午9:45 • 未分类 • 阅读 1

Johnson算法实现流水作业最优调度Johnson 算法实现流水作业的最优调度

1. 算法描述

令 $N_1 = \{i | a_i < b_i \}$ , $N_2 = \{ i| a_i \geq b_i\}$ ;
将 $N_1$ 中的作业按照 $a_i$ 的非降序排列，将 $N_2$ 中的作业按照 $b_i$ 的非升序排列；
$N_1$ 中的作业拼接 $N_2$ 中的作业构成 $J o h n s o n$ 算法的最优作业调度。

2. C/C++代码实现

/ *Johnson算法实现流水作业最优调度 */ #include 
     #include 
     using namespace std; const int maxn = 1000; class JobType { 
    public: int key; int index; bool job; bool operator < (const JobType& j)const { 
    return key < j.key;//重载运算符<,以键值key为关键字排序 } }; int FlowShop(int n, int a[], int b[], int c[]) { 
    JobType* d = new JobType[n]; for (int i = 0; i < n; i++) { 
    d[i].key = a[i] < b[i] ? a[i] : b[i];//记录ai bi中最小值为key d[i].job = a[i] < b[i]; //ai < bi N1 = {i | ai < bi} N2 = {i | ai >= bi} d[i].index = i; } sort(d, d + n);//并不是简单的快速排序 可能还有堆排序等排序算法 根据数据的规模进行选择 int j = 0; int k = n - 1; for (int i = 0; i < n; i++) //因为最后的调度序列是 排序之后的{N1,N2} //前面排序之后N1是非降序 N2也是非降序  //因此在排序之后序列中遍历时 遇到job == 0的下标 主要从c[]最后下标开始 依次递减 if (d[i].job) // N1 i按照ai的非降序排列 c[j++] = d[i].index; else //N2 i按照bi的非升序排列  c[k--] = d[i].index; //输出调度序列 cout << "流水作业调度序列为:"; for (int i = 0; i < n; i++) cout << c[i] << " "; cout << endl; //计算最短的流水作业调度时间 j = a[c[0]]; //j记录工序ai完成的时间 k = j + b[c[0]]; //k记录工序bi完成的时间 for (int i = 1; i < n; i++) { 
    j += a[c[i]]; //工序a进行到目前用的时间 k = j < k ? k + b[c[i]] : j + b[c[i]]; //工序a进行到i用的时间j 和 工序b进行到i-1用的时间k 作比较 /*若j > k, i-1作业的b工序已经结束了 但是i作业的a工序还没结束 此时b需要等待其结束 那么i作业的b工序完成时间为 k = j + bi*/ /*否则j <= k, i-1作业的b工序还没结束 i作业的a工序就已经结束 此时i作业的b工序则不需要等待直接进行即可 那么i作业的b工序完成时间为k = k + bi*/ } delete[]d; return k; } int main() { 
    int n; cin >> n; int a[maxn], b[maxn], c[maxn]; for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; int t = FlowShop(n, a, b, c); cout << "流水作业调度最短完成时间是:" << t << endl; return 0; } /* 5 2 5 4 2 3 3 6 1 1 7 */

3. 运行结果

4. 具体动态规划推导过程

具体推导过程

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/225242.html原文链接：https://javaforall.net

赞 (0)

0 0

关于作者

全栈程序员-站长

133.5K 文章

3 粉丝

本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”

【电容】关于电容，这篇说得太详细了

上一篇 2026年3月17日上午9:45

因接外包坐牢456天，我都经历了什么？

下一篇 2026年3月17日上午9:45

export方法_import怎么用

export方法_import怎么用基础命令学习目录首页export的基本作用就是将父shell中的局部变量设置为环境变量，使得该变量可以在子shell中使用。下面设置两种情景对export进行原理解析。情景1.有一个名为myexport.sh的脚本，内容如下：#!/bin/shexportMY_PATH=/usr/local12在linux环境中打开终端运行该shell$shmy…

全栈程序员-站长
2025年9月28日
7
思科路由器配置命令（一）

思科路由器配置命令（一）一路由器基本配置命令 R1 gt enable 进入特权模式 R1 disable 退出特权模式 R1 gt R1 configureter 进入全局配置命令 R1 config noipdomain lookup 关闭域名解析 R1 config hostnameSW1 更改主机名为 SW1R1 config enablepasswo 配置进入特权模式的密码 R1 config interfa

全栈程序员-站长
2025年7月3日
8
websocket大文件发送（分片传送思想）

websocket大文件发送（分片传送思想）目前的项目是在做一款带桌面共享的代码编辑器，其中需要一个发送大文件的功能，传统的node.js处理大文件就是用Buffer.slice(0.offset)的思路把文件分割开，然后通过tcp或udp分开发送。前端中处理二进制的有Blob,它也有slice的方法，也可以将文件拆分开。然后借助websocket发开发送，然后在客户端（注意不是服务端）将文件合并。有人说websocket可以直接发，但是他的大小受到限制，比如发200M的东西，就会出问题。而我的方案就不会存在问题.最主要的是在发送文件的同时也不会影响

全栈程序员-站长
2022年7月11日
82
人人网登录界面[通俗易懂]

人人网登录界面[通俗易懂]<!DOCTYPEhtml><html> <head><metacharset="UTF-8"><title

全栈程序员-站长
2022年8月2日
12
数据库分区表[通俗易懂]

数据库分区表[通俗易懂]数据库分区表（一）什么情况下需要分区，准备需要分区的数据　什么数据库需要进行分区？首先看一下我们的案例：2010年6月我们六期IT开发团队接到一个XX全国连锁店的餐饮系统，经过一周的敏捷开发之后，XX餐饮系统正式上线了，由于该软件的功能强大，操作简单，功能灵活等特性，很快在全国各地铺展开来。XX餐饮店的美食也颇受顾客的喜爱，有的店每天的收入高达1W元人民币，每天这么多的收入，那么每天要

全栈程序员-站长
2022年5月3日
44
uniapp 瀑布流布局

uniapp 瀑布流布局瀑布流组件 template viewclass waterfall layout style margin columnGap px viewclass water flow column style margin right columnGap px v for col c incolunmList key c viewclass water flow column style margin right columnGap px v for col c incolunmList key c viewclass waterfall layout style margin columnGap px template

全栈程序员-站长
2026年3月17日
2

发表回复

关注全栈程序员社区公众号