流水线作业调度问题-动态规划(运用Johnson算法)

问题描述

n个作业{1，2，…，n},要在由机器M1和M2组成的流水线上完成加工。
每个作业加工的顺序都是先在M1上加工，然后在M2上加工。
M1和M2加工作业i所需的时间分别为ai和bi。

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

问题分析

直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。
在一般情况下，机器M2上会有机器空闲和作业积压两种情况
设全部作业的集合为N={1，2，…，n}。S $\subseteq$ N是N的作业子集。
通常，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。
将这种情况下完成S中作业所需的最短时间记为T(S, t)。
流水作业调度问题的最优值为T(N, 0)。

最优子结构性质

最优子结构性质：问题最优解，是否包含了子问题的最优解。

调度问题最优子结构性质：设π是所给n个流水作业（N={1，2，…，n}）的一个最优调度，最优调度序列是π(1) ，π(2)， π(3)，…，π(n) ，π是否是调度π(2)， π(3)，…， π(n)的一个最优调度？若是，最优子结构性质成立。证明如下：
在这里插入图片描述

把π调度n个作业所需的加工时间分成两部分： $a_{π(1)}$ (1) 和T’。其中，T’是机器M1和M2加工作业{π(2)，…，π(n)}所需的时间。因此，π调度n个流水作业需要的总时间为 $a_{π(1)}$ (1) 和T’
令作业子集S=N - {π(1)} ，即：S={π(2)， π(3)，…，π(n)}。
假设π不是实现加工作业子集S所需时间最短（最优）的调度，设π’是M1和M2加工作业子集S所需时间最短的一个最优调度, 则按π’加工作业子集S的最短时间为 T(S, $b_{π(1)}$ )

在这里插入图片描述

因此π(1)， π’(2)，…， π’(n)是完成N ={1，2，…，n}作业的一个调度，且该调度完成n个作业所需的时间 a_π(1)+T(S,b_π(1))
由于 π’是加工π(2)，…，π(n)的最优调度，则T(S,bπ(1))是最短时间，则T(S, $b_{π(1)}$ )≤ T’，因此， $a_{π(1)}$ +T(S, $b_{π(1)}$ ) ≤ $a_{π(1)}$ +T’.
由此，按照π(1)， π’(2)，…， π’(n)调度顺序完成n个作业所需的时间，小于按照π(1)， π(2) ，…， π(n) 调度完成n个作业所需时间aπ(1)+T’，这与π是N的最优调度矛盾，
因此，π’是完成π(2)，…，π(n)的最优调度假设不成立，因此，π是完成π(2)，…，π(n)作业的最优调度。即：作业调度问题最优子结构性质成立。

递归计算最优值

由流水作业调度问题的最优子结构性质可知:

T(N,0)=min{}

一般情况下：
在这里插入图片描述

在这里插入图片描述

流水作业调度的Johnson法则

对于流水作业调度问题，必存在最优调度π ，使得作业π(i)和π(i+1)满足Johnson不等式, 此时称π为满足Johnson法则的调度。
min{ $b_{π(i)}$ , $a_{π(i+1)}$ }≥min{ $b_{π(i+1)}$ , $a_{π(i)}$ } , 1≤i ≤n-1

所有满足Johnson法则的调度均为最优调度,且具有相同的加工时间。
从而，将流水作业调度问题转化为求满足Johnson法则的调度问题。

分析问题

当min{ $a_1$ , $a_2$ ,┅, $a_n$ , $b_1$ , $b_2$ ,┅, $b_n$ }= $a_k$ 时，则对任何i≠k，都有min{ $b_k$ , $a_i$ } ≥ min{ $b_i$ , $a_k$ }成立，故此时应将作业k安排在最前面，作为最优调度的第一个执行的作业；
当min{ $a_1$ , $a_2$ ,┅, $a_n$ , $b_1$ , $b_2$ ,┅, $b_n$ }= $b_k$ 时，则对任何i≠k，也都有min{ $b_i$ , $a_k$ } ≥ min{ $b_k$ , $a_i$ }成立，故此时应将作业k安排在最后面，作为最优调度的最后一个执行的作业。
n个作业中首先开工（或最后开工）的作业确定之后，对剩下的n-1个作业采用相同方法可再确定其中的一个作业,应作为n-1个作业中最先或最后执行的作业；反复使用这个方法直到最后只剩一个作业为止，最优调度就确定了。

计算作业加工顺序的步骤

将{ $a_1$ , $a_2$ ,┅, $a_n$ , $b_1$ , $b_2$ ,┅, $b_n$ }排成非递减序列；
依次从序列中抽出最小元素m，如果m ＝ $a_j$ 且作业j还没有排入调度表，则把作业 j 安排在调度表可达的最左边一项空位上（设n个作业的调度表有n项，开始全部为空）。
如果m = bj且作业j还没有排入调度表，则把作业j安排在调度表可达的最右边一项空位上。
如果作业j已排在调度表中，则取序列的下一个最小元素m，继续按上述方法调度，直到元素取完为止。
最后得到的调度表中的作业的顺序就是各作业的加工顺序。

例子

设 n ＝ 4，
（ $a_1$ , $a_2$ ， $a_3$ , $a_4$ ）＝（3，4，8，10）
（ $b_1$ , $b_2$ ， $b_3$ , $b_4$ ）＝（6，2，9，15）

解:
经排序后为
（ $b_2$ ， $a_1$ ， $a_2$ ， $b_1$ ， $a_3$ ， $b_3$ ， $a_4$ ， $b_4$ ）＝（2，3，4，6，8，9，10，15）

设σ1，σ2，σ3，σ4是最优调度。
因为最小数是b2，故置σ4= 2。下一个次小的数是a1，置σ1= 1。接下去是a2，作业2已经被调度。再其次是b1作业1也已经被调度。下一个是a3，置σ2= 3，依次置σ3= 4。

流水作业调度问题的Johnson算法

令 $N_1$ = { i | $a_i$ < $b_i$ }， $N_2$ = { i | $a_i$ ＞ $b_i$ }
将 $N_1$ 中作业依ai的非减序排序；将 $N_2$ 中作业依 $b_i$ 的非增序排序；
$N_1$ 中作业接 $N_2$ 中作业构成满足Johnson法则的最优调度π。

红线左侧满足 $a_{π(i)}$ ≤ $b_{π(i)}$ 和 $a_{π(i)}$ ≤ $a_{π(i+1)}$ ，符合johnson不等式: min{ $b_{π(i)}$ , $a_{π(i+1)}$ }≥min{ $b_{π(i+1)}$ , $a_{π(i)}$ } ，N1中作业调度顺序最优；
红线右侧满足 $b_{π(i+1)}$ ≤ $a_{π(i+1)}$ 和 $b_{π(i+1)}$ ≤ $b_{π(i)}$ ，符合johnson不等式: min{ $b_{π(i)}$ , $a_{π(i+1)}$ }≥min{ $b_{π(i+1)}$ , $a_{π(i)}$ } ，N2中作业调度顺序最优；
中间过渡部分横向比较，左侧 $a_{π(i)}$ ≤ $b_{π(i)}$ ,右侧 $b_{π(i+1)}$ ≤ $a_{π(i+1)}$ ，符合johnson不等式: min{ $b_{π(i)}$ , $a_{π(i+1)}$ }≥min{ $b_{π(i+1)}$ , $a_{π(i)}$ } ，其作业调度顺序最优；
若 $a_{π(i)}$ ≤ $b_{π(i+1)}$ , 则 $a_{π(i)}$ ≤ $b_{π(i+1)}$ ≤ $a_{π(i+1)}$ ，又 $a_{π(i)}$ ≤ $b_{π(i)}$ ，成立。
若 $a_{π(i)}$ ≥ $b_{π(i+1)}$ , 则 $b_{π(i+1)}$ ≤ $a_{π(i)}$ ≤ $b_{π(i)}$ ，又 $b_{π(i+1)}$ ≤ $a_{π(i+1)}$ ，成立。

算法复杂度分析

算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。

作业调度的最短时间计算

两个作业调度

在这里插入图片描述

三个作业调度

在这里插入图片描述

核心代码

👉 参照上面的计算步骤进行分析,有些许不同。

class Jobtype 
{ 
public:int key, index;  // key保存ai和bi二者较小的值； index保存作业号i    bool job;   ///将满足条件ai<bi的放入N1集合的作业标记为trueint operator <=(Jobtype a) const { return(key<=a.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]? b[i]:a[i]; //分别取b[i]和a[i]值较小的作为关键字 d[i].job = a[i]<=b[i]; //将满足a[i]<b[i]的放入N1集合的作业i标记为true d[i].index = i;     //将当前作业号i赋值给index}Sort(d, n);//对数组d按关键字key升序进行排序int j = 0,  k = n-1; //指向数组c的两个指针，j指向最前面，k指向最后面for(int i=0; i<n; i++){  if(d[i].job)c[j++] = d[i].index; //将排过序的数组d，取N1中作业号,放到数组c的前面 elsec[k--] = d[i].index;//将d中属于N2的作业号, 放到数组c的后面，从而实现N1的非减序排序，N2的非增序排序}j = a[c[0]];   //第一个作业a完成的时间k = j+b[c[0]];  //第一个作业a+b完成的时间for(int i=1; i<n; i++){ j += a[c[i]]; //M1在执行c[i]作业的同时，M2在执行c[i-1]号作业，最短执行时间取决于M1与M2谁后执行完k = j<k? k+b[c[i]] : j+b[c[i]]; //计算最优加工时间}delete d;return k;
}

完整代码

把在M1上工作的时间看做是先行工序时间，M2上的工作时间看成后行工序时间。
　　如果某个作业的M1时间>M2时间，它就是后行工序；反之，就是先行工序时间。


#include<stdio.h>
#include<iostream>
#include<algorithm>
#define n 6     //6个作业
using namespace std;int M1[n]={2,7,6,4,6,8};
int M2[n]={5,3,2,7,9,2};
int c[n]={0};    //存放次序，注意：c[m]=k,意思是第m+1个执行的作业是kclass Node{
public:int time;    //时间int index;   //来自第几个作业int position;  //是先行工序还是后行工序};bool cmp(Node a,Node b){return a.time<b.time;
}int main(){Node* node=new Node[n];   //设置n个Node型结构体，盛放n个作业int first=0,end=n-1;int time1=0,time2=0; //分别记录在机器1 和 机器2 上的时间for(int i=0;i<n;i++){  // 数组打底工作node[i].index=i;    //记录一下当前这个node节点放的是哪个作业if(M1[i]>M2[i]){node[i].time=M2[i];node[i].position=2;    //后行工序}else{node[i].time=M1[i];node[i].position=1;    //先行工序}}//虽然把n个作业都赋值到了Node型结构体中，//但是大小交错，没有顺序，//所以需要排序sort(node,node+n,cmp);//排完序后，把原本顺序都乱了，先行、后行工作虽然交错，但都已经从小到大排列了//需要用c数组记录执行顺序，先行工序从前往后放，后行工序从后往前放for(int i=0;i<n;i++){if(node[i].position==1){   //先序c[first]=node[i].index;first++;}if(node[i].position==2){    //后序c[end]=node[i].index;end --;}}time1=M1[c[0]];time2=time1+M2[c[0]];for(int i=1;i<n;i++){time1+=M1[c[i]];time2=time1>time2?time1+M2[c[i]]:time2+M2[c[i]];}cout<<"次序："<<endl;for(int i=0;i<n;i++){cout<<c[i]+1<<"  ";}cout<<endl;cout<<time2<<endl;return 0;
}