當前位置:網站首頁>流水調度作業問題【回溯】

流水調度作業問題【回溯】

2022-01-27 03:58:46 咩咩_10538769

首先需要明確,流水調度作業問題最佳算法應該是用貪心,這裏先介紹回溯,貪心見下文

【問題描述】

有n個作業(編號為1~n)要在由兩臺機器M1和M2組成的流水線上完成加工。每個作業加工的順序都是先在M1上加工,然後在M2 上加工。M1和M2加工作業i所需的時間分別為ai和bi (1≤i≤n) 。
流水作業調度問題要求確定這n個作業的最優加工順序,使得從第一個作業在機器M1上開始加工,到最後一個作業在機器M2上加工完成所需的時間最少。可以假定任何作業一旦開始加工,就不允許被中斷,直到該作業被完成,即非優先調度。

【輸入格式】

輸入第一行是作業數n,接下來的n行,第一個數字是在M1上加工的時間,第二個是在M2上的加工時間,最後輸入n=0結束

4
5 6
12 2
4 14
8 7
0

樣例輸出

33

實際上就是所有的方案進行全排列,然後選出執行時間最少的一種方案即為最優

首先我們需要4個數組,一個x【】存放解向量即調度方案,一個bestx【】存放最佳調度方案,最優調度時間用best_time錶示,一個f1【】數組錶示在M1上完成作業 i 用的時間,一個f2【】錶示在M2上完成作業 i 所用的時間

由於每個作業都是現在M1上執行,然後才可以在M2上執行,所以f2【n】實際上就是執行全部作業的總時間

假設現在有下面的三個作業

作業編號 1 2 3
M1時間a 2 3 2
M2時間b 1 1 3

假如現在的調用方案為x= (1, 2, 3),即按作業1、2、3的順序執行。首先將f1和f2數組所有元素
初始化為0。該調度方案的總時間計算如下:
 

也就是說,不需要等待的話就直接加在M1所用時間上

假如現在使用調度方案x=(3,1,2),即按作業3、1、2的順序執行

 注意這種和上一種略有不同,需要等待

 

需要等待的話就要等你前一個作業工作完你才可以在M2上開始,所以加在f2[I]上,再加上當前這個作業它需要在M2上花的時間b

注意: X中的解向量Xi並不是第幾個作業,而是第i步執行的作業編號

 

總結: 

f2[i-1] > f1:   需要等待---->f2[i] = f2[i-1] + b[x[i]] 
f2[i-1] ≤ f1:   不需等待---->f2[i] = f1 + b[x[i]] 

現在將兩個式子合並:

M1上的作業都是可以直接開始的,所以直接加a即可,而M2要考慮其他

因為最後都是要加b[x[i]],所以只需在f2[i-1] 和 fi 中取最大值

理一下總體思路(排列+剪枝):

排列: 樹遞歸回溯框架,在求一個方案的同時求其f2[n]的時間 
剪枝:   求出第i層的f2[i]即執行作業x[i]後的總時間,若f2[i]≥bestf(bestf為當前求出的執行全部作業的最優總時間),就沒有必要從該結點向下擴展了,讓其成為死結點,也就是說僅僅擴展滿足f2[i]<bestf的結點。

代碼如下:

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f   //易錯,最優值應該初始化為無窮大
#define MAX 1001   
int n=4;
int a[MAX]={0,5,12,4,8};
int b[MAX]={0,6,2,14,7};
int bestf;
int f1;
int f2[MAX];
int x[MAX];
int bestx[MAX];
int max(int a,int b){
	return a>b?a:b;
}
void swap(int &x,int &y){
	int temp=x;
	x=y;
	y=temp;
}
void dfs(int i){
	if(i>n){
		if(f2[n]<bestf){   //找到更優 
			bestf=f2[n];
			for(int j=1;j<=n;j++){
				bestx[j]=x[j];    //把更優的解向量複制過來 
			}
		}
	}else{   //沒有找到更優,從其他作業中找 
		for(int j=i;j<=n;j++){  //全排列 
			swap(x[i],x[j]);  
			//如果選擇第i的作業x[i] 
			f1+=a[x[i]];     //在M1所用時間 
			f2[i]=max(f1,f2[i-1])+b[x[i]];  //在M2所用時間
			if(f2[i]<bestf){  //如果符合剪枝條件 
				dfs(i+1);    //進入下一輪 
			}
			//回溯
			f1-=a[x[i]];
			swap(x[i],x[j]); 
		}
	}
}
int main(){
	f1=0;
	bestf=INF;
	memset(f2,0,sizeof(f2));
	for(int k=1;k<=n;k++){  //設置初始調度作業的順序1,2,3..... 
		x[k]=k;
	}
	dfs(1);
	printf("最少時間:%d\n最優調度方案:" , bestf);
	for(int j=1;j<=n;j++){       //輸出最優調度方案 
		printf("%d ",bestx[j]);
	}
}

優化剪枝:

當我們選擇第i層的某個結點時,就說明i之前的所有結點都已經遍曆過,所以x[1]-x[i]的作業都被選擇了,我們可以把這些作業的b時間都加起來,記和為sum,記全部這n個作業一共的b時間為tot,那麼tot-sum的值就是剩餘沒有被選擇的作業的b時間總和,而可以肯定的是,這些所有從該結點到任何一個葉子節點作業的調度方案的時間和一定是≥ f2[i] + tot -sum,因此我們可以將這個 f2[i] + tot -sum設為下界值,用bound(i)錶示,所以超過下界值的就沒必要研究了,僅僅擴展bound(i) < bestf的結點即可,流程圖如下:

 優化後的代碼如下:


//下界函數 
int bound(int i){
	int sum=0,tot=0;
	for(int i=1;i<=n;i++){
		tot+=b[x[i]];
	} 
	for(int j=1;j<=i;j++){
		sum+=b[x[i]];
	}
	return f2[i]+tot-sum;
}
void dfs(int i){
	if(i>n){
		if(f2[n]<bestf){
			bestf=f2[n];
			for(int j=1;j<=n;j++){
				bestx[j]=x[j];
			}
		}
	}else{
		for(int j=i;j<=n;j++){
			swap(x[i],x[j]);
			f1+=a[x[i]];
			f2[i]=max(f1,f2[i-1])+b[x[i]];
			if(bound(i)<bestf){
				dfs(i+1);
			}
			f1-=a[x[i]];
			swap(x[i],x[j]);
		}
	}
}

版權聲明
本文為[咩咩_10538769]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201270358456847.html

隨機推薦