0018算法笔记——【动态规划】流水作业调度问题与Johnson法则

流水线作业排序问题/productioncontrol/200908091604.html流水作业排序问题的基本特征是每个工件的加工路线都一致。

在流水生产线上制造不同的零件，遇到的就是流水作业排序问题。

我们说加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。

如果某些工件不经某些机器加工，则设相应的加工时间为零。

一般说来，对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。

但本节要讨论的是一种特殊情况，即所有工件在各台机器上的加工顺序都相同的情况。

这就是排列排序问题。

流水作业排列排序问题常被称作“同顺序”排序问题。

对于一般情形，排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解；对于仅有2台和3台机器的特殊情况，可以证明，排列排序问题下的最优解一定是相应流水作业排序问题的最优解。

这里只讨论排列排序问题。

但对于2台机器的排序问题，实际上不限于排列排序问题。

一、最长流程时间Fmax的计算这里所讨论的是n／m／P /Fmax，问题，其中n为工件数，m为机器数，P表示流水线作业排列排序问题，Fmax为目标函数。

目标函数是使最长流程时间最短，最长流程时间又称作加工周期，它是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。

由于假设所有工件的到达时间都为零(ri=0，i= 1，2，…，n)，所以Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最长完工时间Cmax。

设n个工件的加工顺序为S＝(S1，S2，S3，…，Sn)，其中Si为第i位加工的工件的代号。

以表示工件Si在机器M k上的完工时间, 表示工件Si在Mk上的加工时间，k= 1，2，…，m；i=1，2，…，n，则可按以下公式计算：在熟悉以上计算公式之后，可直接在加工时间矩阵上从左向右计算完工时间。

下面以一例说明。

例9．4 有一个6／4／p／F max问题，其加工时间如表9—6所示。

一、 问题描述给定n 个作业，每个作业有两道工序，分别在两台机器上处理。

一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。

一个作业只有在机器1上的处理完成以后才能由机器2处理。

假设已知作业i 在机器j 上需要的处理时间为t[i,j]。

流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。

二、 算法分析n 个作业{1,2,…,n}要在由2台机器1M 和2M 组成的流水线上完成加工。

每个作业加工的顺序都是先在1M 上加工，然后在2M 上加工。

1M 和2M 加工作业i 所需要的时间分别为t[i,1]和t[i,2], n i ≤≤1.流水作业调度问题要求确定这n 个作业的最优加工顺序，使得从第一个作业在机器1M 上开始加工，到最后一个作业在机器2M 上加工完成所需的时间最少。

从直观上我们可以看到，一个最优调度应使机器1M 没有空闲时间，且机器2M 的空闲时间是最少。

在一般情况下，机器2M 上会有机器空闲和作业积压两种情况。

设全部作业的集合为},....,2,1{n N =。

N S ⊆是N 的作业子集。

在一般情况下，机器1M 开始加工S 中作业时，机器2M 还在加工其他作业，要等时间t 后才能利用。

将这种情况下完成S 中作业所需的最短时间计为),(t S T 。

流水作业调度问题的最优解为)0,(N T 。

1. 证明流水作业调度问题具有最优子结构设a 是所给n 个流水作业的一个最优调度，它所需要的加工时间为']1),1([T a t +。

其中，'T 是在机器2M 的等待时间为]2),1([a t 时，安排作业)(),......,3(),2(n a a a 所需的时间。

记)}1({a N S -=，则我们可以得到])2),1([,('a t S T T =。

事实上，有T 的定义可知])2),1([,('a t S T T ≥.若])2),1([,('a t S T T >，设'a 是作业集S 在机器2M 的等待时间为]2),1([a t 情况下的一个最优调度。

流水作业调度一、 可行性分析与项目开发计划ｎ个作业}{n ,...2,1要在由2台机器M1和M2组成的流水线上完成加工。

每个作业的顺序都是现在M1上加工，然后再M2上加工。

M1和M2加工作业i 所需的时间分别是i a 和i b ，1<=i<=n.流水作业调度问题要求确定这n 个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需要的时间最少。

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

设全部作业的集合为N={1,2，…n}。

N S ⊆是N 的作业子集，在一般情况下，机器M1开始加工作业S 中作业时，机器M2还在加工其他作业，要等时间t 后才可以利用。

将这种情况下完成S 中作业所需要的最短时间记做T(S,t),则流水作业调度问题的最优值就是T(N,0).我们通过分析可以知道流水作业调度问题具有最优子结构的性质，因此考虑用动态规划算法自后向前来解决其最优问题。

这就需要通过建模来得出最优子结构的递归式子，从而设计算法求解最优值。

二、 需求分析1、 用户可以根据自己的需要输入想要进入流水线的作业数。

2、 用户可以输入这几个作业在机器M1和M2上的加工时间。

3、 由主函数调用流水作业调度的Johnson 算法来实现对流水作业的安排。

4、 输出经过Johnson 算法安排后的作业序列，这就是最终的一个最优调度。

三、 概要设计 总体设计：假定这n 个作业在机器M1上加工时间为i a ,在机器M2上加工时间为i b ，1<=i<=n. 由流水作业调度问题具有最优子结构性质可知，)}},{(min{)0,(i i b i N T a N T =+= 1<=i<=n 推广到一般情况下，})}0,m a x {},{({),(i a t b i S T a t S T i i -+-+= S i ∈ 式子中，}0,max{i a t -这一项是由于在机器M2上，作业i 必须在},max{i a t 时间之后才能开工，因此，在机器M1上完成作业加工i 之后，在机器还需要}0,max{},max{i i i i i a t b a a t b -+=-+时间完成对作业i 的加工。

约翰逊法则例题及解答摘要：一、约翰逊法则简介二、约翰逊法则的应用1.单一资源约束问题2.多个资源约束问题3.资源分配策略三、约翰逊法则的实际案例四、约翰逊法则在项目管理中的应用五、总结与启示正文：【一、约翰逊法则简介】约翰逊法则（Johnson"s Rule）是一种解决资源约束问题的方法，适用于项目管理和生产调度等领域。

该法则是由英国管理学家Johnson提出的，其主要思想是根据任务的优先级和资源的可用性来安排任务执行顺序，以实现资源的高效利用。

【二、约翰逊法则的应用】【1.单一资源约束问题】在单一资源约束的情况下，约翰逊法则可以通过以下步骤进行求解：（1）对任务进行排序，根据任务的优先级从高到低排列；（2）计算每个任务在不同资源约束下的完成时间；（3）选择最小完成时间的任务作为第一个执行的任务；（4）在第一个任务执行过程中，依次安排其他任务加入执行，直到所有任务完成。

【2.多个资源约束问题】在多个资源约束的情况下，约翰逊法则可以采用类似的方法进行求解。

首先，对任务进行排序，然后针对每个资源，分别应用单一资源约束下的约翰逊法则，得到每个资源的最小完成时间。

最后，选择所有资源的最小完成时间作为项目的总完成时间。

【3.资源分配策略】约翰逊法则还提供了一种有效的资源分配策略，即“贪心算法”。

在任务执行过程中，根据当前可用资源的状况，选择下一个优先级最高的任务执行。

这种策略可以最大限度地利用现有资源，降低项目的总体完成时间。

【三、约翰逊法则的实际案例】以一家工厂的生产调度为例，该工厂有三个任务A、B、C，分别需要10、8、6个单位的资源。

现有资源为单位1。

根据约翰逊法则，我们可以按照以下步骤进行生产调度：1.任务排序：A > B > C2.分配资源：首先分配单位1的资源给任务A，此时任务A需要10个单位，剩余2个单位；3.调整任务B的资源需求为2个单位，任务C的资源需求为4个单位；4.任务A完成，释放1个单位资源；5.分配单位1的资源给任务B，任务B需要8个单位，剩余3个单位；6.分配单位1的剩余资源给任务C，任务C需要4个单位，全部完成。

双机流⽔作业调度问题（Johnson算法）问题定义:双机流⽔作业调度：总共有n个作业，作业i分为两个内容，需要按顺序先后在机器A和机器B上完成，分别需要时间a i,b i来完成，⼀台机器只能同时进⾏⼀项作业，问完成所有作业所需的最⼩时间。

多机流⽔作业调度：⼀个作业需要在⼤于两台机器上先后完成，是NP-hard问题。

解法：问题就是求最佳作业序列。

设前i项作业所需的时间为C i，可以得出以下式⼦c i=a1+b1,i=1 max c i−1,∑i j=1a j+b i,2≤i≤n可以证明，对于相邻两项i和j，如果min(a i,b j)<min(a j,b i)则i项放前⾯更优。

将a i和b i的关系分为<,=,>三类，可以得到如下排列顺序:1.当a i<b i,a j<b j时，a i≤a j,应该按a升序排序2.当a i=b i,a j=b j时，随意排列。

3.当a i>b i,a j>b j时，b i≥b j,应该按b降序排序。

同样可以证明，a i<b i的项应该排在最前，然后是a i=b i的项，最后是a i>b i的项。

代码:{{}//P1248，给定n，ai,bi，求最⼩⽤时和对应序列#include <bits/stdc++.h>using namespace std;const int maxn=1e5+5;typedef long long ll;struct node{int a,b,d,id;bool operator<(const node &v)const {if(d!=v.d)return d<v.d;else if(d==-1){return a<v.a;}else{return b>v.b;}}}p[maxn];int main () {int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&p[i].a);for(int i=1;i<=n;i++){scanf("%d",&p[i].b);p[i].id=i;int cha=p[i].a-p[i].b;if(cha==0)p[i].d=0;else p[i].d=cha<0?-1:1;}sort(p+1,p+1+n);ll ans=0,dt=0;for(int i=1;i<=n;i++){ans+=p[i].a;dt=max(0ll,dt-p[i].a);dt+=p[i].b;}ans+=dt;printf("%lld\n",ans);for(int i=1;i<=n;i++){if(i>1)printf(" ");printf("%d",p[i].id);}puts("");}Processing math: 100%。

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。

2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。

3.某一问题可用动态规划算法求解的显著特征是____________________________________。

4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。

5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。

6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。

7.以深度优先方式系统搜索问题解的算法称为_____________。

8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。

9.动态规划算法的两个基本要素是___________和___________。

10.二分搜索算法是利用_______________实现的算法。

二、综合题（50分）1.写出设计动态规划算法的主要步骤。

2.流水作业调度问题的johnson算法的思想。

3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。

4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。

1、问题描述：n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi。

流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

2、问题分析直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。

在一般情况下，机器M2上会有机器空闲和作业积压2种情况。

设全部作业的集合为N={1，2，…，n}。

S是N的作业子集。

在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。

将这种情况下完成S中作业所需的最短时间记为T(S,t)。

流水作业调度问题的最优值为T(N,0)。

设π是所给n个流水作业的一个最优调度，它所需的加工时间为aπ(1)+T’。

其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所需的时间。

记S=N-{π(1)}，则有T’=T(S,bπ(1))。

证明：事实上，由T的定义知T’>=T(S,bπ(1))。

若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。

则π(1)，π'(2)，…，π'(n)是N的一个调度，且该调度所需的时间为aπ(1)+T(S,bπ(1))<aπ(1)+T’。

这与π是N的最优调度矛盾。

故T’<=T(S,bπ(1))。

从而T’=T(S,bπ(1))。

这就证明了流水作业调度问题具有最优子结构的性质。

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

将问题规模缩小。

最优流水作业调度问题摘要本文给出了双机流水作业调度的Johnson算法，并结合POJ上的一道题目详述了该算法的具体编程实现和应用。

关键词：双机流水作业调度 Johnson算法正文流水作业是并行处理技术领域的一项关键技术，它是以专业化为基础,将不同处理对象的同一施工工序交给专业处理部件执行,各处理部件在统一计划安排下,依次在各个作业面上完成指定的操作。

流水作业调度问题是一个非常重要的问题，其直接关系到计算机处理器的工作效率。

然而由于牵扯到数据相关、资源相关、控制相关等许多问题，最优流水作业调度问题处理起来非常复杂。

已经证明，当机器数(或称工序数)大于等于3时，流水作业调度问题是一个NP-hard问题（e.g分布式任务调度）。

粗糙地说，即该问题至少在目前基本上没有可能找到多项式时间的算法。

只有当机器数为2时，该问题可有多项式时间的算法（机器数为1时该问题是平凡的）。

我们先给出流水作业调度的定义：设有 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 个作业的加工时间为最少。

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

前面已经说过，当m≥3时该问题是NP问题，这里我们只给出m=2时时间复杂度在多项式以内的Johnson算法。

流⽔作业调度（贪⼼）Johnson算法某⼯⼚收到了 n个产品的订单，这 n个产品分别在 A、B 两个车间加⼯，并且必须先在 A 车间加⼯后才可以到 B 车间加⼯。

某个产品 i在 A，B 两车间加⼯的时间分别为Ai,Bi 。

怎样安排这 n个产品的加⼯顺序，才能使总的加⼯时间最短。

这⾥所说的加⼯时间是指：从开始加⼯第⼀个产品到最后所有的产品都已在 A，B 两车间加⼯完毕的时间。

边上代码边说开始让第⼆台机器等的时间缩⼩最后让第⼀台机器等的时间更⼩#include<bits/stdc++.h>#define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template<typename T>inline void rd(T&x){char c;bool f=0;while((c=getchar())<'0'||c>'9')if(c=='-')f=1;x=c^48;while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);if(f)x=-x;}int n,pos[1005];struct node{int id,atime,btime,mintime;bool operator<(node a)const{re mintime<a.mintime;}}pro[1005];int main(){// freopen("in.txt","r",stdin);rd(n);inc(i,1,n){rd(pro[i].atime);pro[i].id=i; //加编号，第⼆问}inc(i,1,n){rd(pro[i].btime);pro[i].mintime=min(pro[i].atime,pro[i].btime);//取ai和bi中较⼩值mi}sort(pro+1,pro+n+1);//通过mi由⼩到⼤排序int l=1,r=n;inc(i,1,n){if(pro[i].mintime==pro[i].atime)pos[l++]=i;//ai⼩的放在前⾯else pos[r--]=i;//bi⼩的放在后⾯}//模拟int now=0,last=0;inc(i,1,n){now+=pro[pos[i]].atime;last=max(last,now)+pro[pos[i]].btime;}printf("%d\n",last);inc(i,1,n-1)printf("%d ",pro[pos[i]].id);printf("%d",pro[pos[n]].id);re 0;}。

动态规划-流水作业调度报告C1 问题描述和分析N个作业{1,2,………,n}要在由两台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi，1≤i≤n。

流水作业高度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

设全部作业的集合为N={1,2,…,n}, S⊆N,,一般情况下,机器M1开始加工作业S时,机器M2还在加工其他作业,要等时间t后才可利用.将这种情况下完成S中作业所需的最短时间记为T(S,t).流水作业调度的最优值为T(N,0)即,设π是所给n个流水作业的一个最优调度,它所需的加工时间为a(π1)+T’.其中T’是在此机器M2的等待时间为b(π1)时,安排作业π1, π2,…πn所需时间.所以S=N-{π1},有T’=T(S,b(π1)).由T的定义知T’≥T(S,b(π1)).若T’＞T(S,b(π1)),设π’是作业集S在机器M2的等待时间为b(π1)情况下的一个最优调度.则π1, π’2,…, π’n是N的一个调度,且该调度所需的时间为a(π1)+T(S,b(π1))＜a(π1)+T’.这与π是N的最优调度矛盾.故T’≤T(S,b(π1).从而T’=T(S,b(π1).即当机器M1为空闲即未安排任何加工任务时，则任何一个作业的第一个任务（第一道工序）都可以立即在M1上执行，无须任何先决条件。

因此容易知道，必有一个最优调度使得在M1上的加工是无间断的。

实际上，如某个最优调度π在M1上安排的加工是有间断的，则我们可以把所有在M1上出现间断处的任务的开始加工时间提前，使得在M1上的加工是无间断的；而在M2上仍按π原先的安排。

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

由于在调度π’下，任何一个任务在M1上加工的结束时间不晚于在调度π下的结束时间，故调度π’不会影响在M2上进行加工的任何一个任务的开始时间。

1.题目：流水作业调度的Johnson法则2.程序清单：#include<iostream>using namespace std;#define MAXSIZE 1000typedef struct{int key,index;bool job;}Jobtype;typedef struct{Jobtype r[MAXSIZE];int length;}Sjob;//顺序表类型void sort(Sjob &L,int n){L.length=n;int i,j;Jobtype t;for(i=0;i<n-1;i++)for(j=i+1;j<n;j++)if(L.r[i].key>L.r[j].key){t=L.r[i];L.r[i]=L.r[j];L.r[j]=t;}}int Flowshop(int n,int a[],int b[],int c[]) {int i;Sjob d;for(i=0;i<n;i++){d.r[i].key=a[i]>b[i]?b[i]:a[i];d.r[i].job=a[i]<=b[i];d.r[i].index=i;}sort(d,n);int j=0,k=n-1;for(i=0;i<n;i++){if(d.r[i].job)c[j++]=d.r[i].index;else c[k--]=d.r[i].index;}j=a[c[0]];k=j+b[c[0]];for(i=1;i<n;i++){j+=a[c[i]];k=j<k?k+b[c[i]]:j+b[c[i]];}return k;}void main(){int n,i;int a[MAXSIZE],b[MAXSIZE],c[MAXSIZE];cout<<"作业个数：";cin>>n;cout<<"在M1上的加工时间分别为：";for(i=0;i<n;i++)cin>>a[i];cout<<"在M2上的加工时间分别为：";for(i=0;i<n;i++)cin>>b[i];int m=Flowshop(n,a,b,c);for(i=0;i<n;i++)cout<<c[i]<<" ";cout<<endl<<"最短加工完成时间是:"<<m<<endl;}3.实验截图：。

动态规划——流⽔作业调度问题问题：n个作业 N={1，2，…，n}要在2台机器M1和M2组成的流⽔线上完成加⼯。

每个作业须先在M1上加⼯，然后在M2上加⼯。

M1和M2加⼯作业i 所需的时间分别为 ai 和bi，每台机器同⼀时间最多只能执⾏⼀个作业。

流⽔作业调度问题要求确定这n个作业的最优加⼯顺序，使得所有作业在两台机器上都加⼯完成所需最少时间。

最优调度应该是：1. 使M1上的加⼯是⽆间断的。

即M1上的加⼯时间是所有ai之和，但M2上不⼀定是bi之和。

2. 使作业在两台机器上的加⼯次序是完全相同的。

则得结论：仅需考虑在两台机上加⼯次序完全相同的调度。

为了得到最优⼦解结构（⽐较重要~~~~ ⽼师说期末考试会考到这个）：—>机器M1开始加⼯S中作业时，机器M2还在加⼯其他作业，要等时间 t 后才可利⽤,则： 1. 则完成S中作业所需的最短时间记为T(S,t) 2. 完成所有作业所需的最短时间为T(N,0) 3. T(N,0)=min{ai + T(N-{i}, bi)}, i∈N。

ai：选⼀个作业i先加⼯，在M1的加⼯时间。

T(N-{i},bi}：剩下的作业要等bi时间后才能在M2上加⼯。

注意这⾥函数的定义，因为⼀开始⼯作i是随机取的，M1加⼯完了ai之后，要开始加⼯bi了，这⾥M1是空闲的可以开始加⼯剩下的N-i个作业了，但此时M2开始加⼯bi，所以要等bi时间之后才能重新利⽤，对应到上⾯函数T(s,t)的定义的话，这⾥就应该表⽰成T(N-{i},bi), 所以最优解可表⽰为T(N,0)=min{ai + T(N-{i}, bi)}, i∈N，即我们要枚举所有的⼯作i，使这个式⼦取到最⼩值。

这⾥顺便吐槽⼀句：算法中会利⽤很多数学知识，⼀定要搞清楚函数的意义以及每个数学符号所代表的含义，这样不⾄于各种懵⽐。

继续分析T(S,t)可得： T(S,t)={ai + T(S-{i}, bi+max{t-ai,0})}, i∈S 其中：T(S-{i}, bi+max{t-ai,0})：剩下的作业等bi+max{t-ai,0}才能在M2加⼯，⾄于这⾥是怎么推导出来的呢？见下⾯推导：最优⼦结构的证明（问题最优解包括⼦问题最优解）：最优⼦结构：设π是N的⼀个最优调度，其加⼯顺序为π1,…, πn，其所需的加⼯时间为 aπ1+T’(即第⼀个作业π1在M1上加⼯的时间和其它的加⼯时间)。

约翰逊法则例题及解答
约翰逊法则（Johnson's Rule）是一种用来调度作业顺序的方法。

它基于以下两个原则：1）最早开始时间（Earliest Start Time）尽可能早，以最早完成作业。

2）最晚开始时间（Latest Start Time）尽可能晚，以最小化在后面作业上的影响。

下面是一个例题及解答，演示如何使用约翰逊法则调度作业顺序。

例题：
假设有4个作业A、B、C和D，每个作业的任务时间如下：A：3
B：6
C：2
D：5
解答：
1）计算每个作业的处理时间（Processing Time = 加工时间）：A：3
B：6
C：2
D：5
2）计算每个作业的最早开始时间（Earliest Start Time = EST）：A：0
B：0
C：0
D：0
3）计算每个作业的最晚开始时间（Latest Start Time = LST）：A：14（加工时间总和）
B：14
C：14
D：14
4）计算每个作业的提前完成时间（Slack Time）：
A：14 - 3 = 11
B：14 - 6 = 8
C：14 - 2 = 12
D：14 - 5 = 9
5）根据提前完成时间排序作业顺序：
先安排C（最早完成时间为2）
然后安排D（最早完成时间为6）
接着安排B（最早完成时间为12）
最后安排A（最早完成时间为14）
因此，按照约翰逊法则，作业顺序为：C、D、B、A。

请注意，这只是一个示例，实际应用中可以根据具体情况进行计算和调度。

流水作业调度问题-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII流水作业调度问题描述:N个作业{1,2,………,n}要在由两台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi，1≤i≤n。

流水作业高度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

可以假定任何任务一旦开始加工，就不允许被中断，直到该任务被完成，即非优先调度。

输入:输入包含若干个用例,第一行为一个正整数K(1<=K<=1000),表示用例个数,接下来K个用例,每个用例第一个为作业数N(1<=N<=1000)，接下来N行，每行两个非负整数，分别表示在第一台机器和第二台机器上加工时间。

输出:每个用例用一行输出采用最优调度所用的总时间，即从第一台机器开始到第二台机器结束的时间。

样例输入:145 612 24 148 7样例输出:33假定直接按顺序进行完成，则机器1可以不用考虑，因为作业1完成后就可以完成作业2,直到作业n，需要的时间为所有作业在机器1上的时间总和。

但是，机器2上完成的时间呢？机器2上完成的时间显示除了作业在机器2上完成的时间总和，还要加上等待时间，即要求先在机器1上完成后，才能在机器2上开始。

例如5 612 2两个作业，顺序如下：按顺序，则在机器1上进行作业1需要5小时，后进行作业2,需要12小时，和为17小时；机器2上，作业1只能从第5小时开始，第11小时完成，等待了5小时，等到作业2在机器1上完成后（已经是第17时），再完成2小时，共19小时。

机器2的等待时间总计为11小时。

逆序，在机器1上进行作业2需要12小时，后进行作业1需要5小时，和为17小时，和前面一样；机器2上，作业2完成后开始，等待了12小时，然后再等3小时开始作业1的6小时，共计21小时，共等待了15小时。

流⽔作业调度问题———Johnson算法问题描述：N个作业1，2，…，n要在由2台机器A和B组成的流⽔线上完成加⼯。

每个作业加⼯的顺序都是先在A上加⼯，然后在B上加⼯。

A和B加⼯作业i所需的时间分别为a[i]和b[i]。

你可以安排每个作业的执⾏顺序，使得从第⼀个作业在机器A上开始加⼯，到最后⼀个作业在机器B上加⼯完成所需的时间最少。

求这个最少的时间。

⼤概思路：求⼀个加⼯顺序使得加⼯时间最短，就是让机器空闲时间最短，当A开始⼯作便会⼀直运作，关键是B会等待A，很明显A加⼯第⼀个作业时B得等待，同理B加⼯最后⼀个作业A 得等待Johnson算法此算法是⼀种贪⼼策略：把在A机器上加⼯最快的作业先加⼯，把B机器上加⼯最快的作业放在最后具体实现：设M i=min{a i,b i}将数组M由⼩到⼤排序，然后从第⼀个开始处理，若M i=a i则按顺序排在作业加⼯顺序的前⾯，若M i=b i则按顺序排在后⾯最后排出来的顺序就是最优解算法证明设S={J1,J2,J3····J n}为待加⼯作业排序，T(S,t)为A开始加⼯S中作业，B需t时刻后才能加⼯A加⼯完的作业，这种情况下加⼯完S中作业所需最⼩的时间T(S,t)=min{a i+T(S−{J i},b i+max{t−a i,0})}, J i∈S假设最佳⽅案是先加⼯J i,然后加⼯J j，则有T(S,t)=a i+T(S−{J i},b i+max{t−a i,0})=a i+a j+T(S−{J i,J j},b i+bj+T ij)T ij=b j+max{b i+max{t−a i,0}−a j,0},0}=b i+b j−a i−a j+max{t,a i,a i+a j−b i}若J i和J j调换顺序则：T′(S,t)=a i+a j+T(S−{J i,J j},T ji)T ji=b i+b j−a i−a j+max{t,a j,a i+a j−b j}所以T(S,t)<=T′(S,t),所以有max{t,a i,a i+a j−b i}<=max{t,a j,a i+a j−b j}a i+a j+max{−b i,−a j}<=a i+a j+max{−b j,−a i}（其实2步转化我不太清楚，只是意会了⼀下，如有理解的⿇烦告诉我，感谢）即min{b j,a i}<=min{b i,a j}也就是说J i在J j之前加⼯最优得满⾜上式条件，则a i<=b i,a j或者b j<=b i,a j即在A机器上加⼯时间短的任务优先，⽽在B机器上加⼯时间短的排在后⾯，与具体实现的步骤相符Processing math: 100%。

0018算法笔记——【动态规划】流水作业调度问题与Johnson 法则1、问题描述：n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi。

流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

2、问题分析直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。

在一般情况下，机器M2上会有机器空闲和作业积压2种情况。

设全部作业的集合为N={1，2，…，n}。

S是N的作业子集。

在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。

将这种情况下完成S中作业所需的最短时间记为T(S,t)。

流水作业调度问题的最优值为T(N,0)。

设π是所给n个流水作业的一个最优调度，它所需的加工时间为aπ(1)+T’。

其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所需的时间。

记S=N-{π(1)}，则有T’=T(S,bπ(1))。

证明：事实上，由T的定义知T’>=T(S,bπ(1))。

若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。

则π(1)，π'(2)，…，π'(n)是N的一个调度，且该调度所需的时间为aπ(1)+T(S,bπ(1))<aπ(1)+T’。

这与π是N的最优调度矛盾。

故T’<=T(S,bπ(1))。

从而T’=T(S,bπ(1))。

这就证明了流水作业调度问题具有最优子结构的性质。

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

johnson算法是一种求解双机调度问题的算法，它可以将作业分配到两个不同的机器上，使得所有作业的总完成时间最小。

假设有5个作业，其加工时间分别为40、50、100、60和20，如果两个机器并行工作，那么可以采用johnson 算法求解最佳调度方案。

根据johnson算法，首先将作业按照加工时间从大到小排序，得到一个序列为50、60、40、100和20。

然后根据两个机器的加工时间，将作业分配到两个机器上。

机器M1的加工时间为30，机器M2的加工时间为50，所以按照johnson算法，将加工时间超过30的作业分配给机器M1，将加工时间小于或等于30的作业分配给机器M2。

根据上述排序后的作业序列，作业50和60的加工时间都超过30，所以应该分配给机器M1；作业40和100的加工时间超过30，所以应该分配给机器M1；作业20的加工时间为20，小于30，所以应该分配给机器M2。

因此，最佳调度方案为：机器M1完成作业50、60、40和100，总加工时间为280；机器M2完成作业20，总加工时间为20。

总完成时间为300，是最小的总完成时间。