5-3 批处理作业调度（回溯）

5-3 批处理作业调度（回溯）

一、问题描述

n个作业集合{1,2,…,n}。每个作业先由机器1处理，再由机器2处理。作业i需要机器j的处理时间为Mj。
对于一个确定的作业调度，设Fi是作业i在机器j上完成的具体时间。

所有作业在机器2上完成的具体时间(时刻)之和f称为该作业调度的完成时间和。
要求:对于给定的n个作业，制定最佳作业调度方案(一个排列),使其完成时间和达到最小。

二、分析

三、代码

//5-3 批处理作业调度  
#include 
#include
#define INF 0x3f3f3f3f
using namespace std;
int m[100][100];//各作业所需的处理时间
int x[100];//当前作业调度
int bestx[100];//当前最优作业调度
int f2[100]; //机器2完成处理时间 
int f1;  //机器1完成处理时间 
int f; //完成时间和 
int bestf=INF;//当前最优值
int n;//作业数 
void Init(){
	f1=0; f=0;
	for(int i=1;i<=n;i++){
		x[i] = i;
		f2[i] = 0;
	}
}
void Swap(int &a,int &b){
	int t=a;
	a=b;
	b=t;
} 
void Backtrack(int t){
	if(t>n){
		for(int i=1;i<=n;i++)
			bestx[i]=x[i];
	//	if(f
			bestf=f;
//		cout<<"bestf="<
	}
	else{
		for(int i=t;i<=n;i++){
//			cout<<"i="<+= m[x[i]][1];
			f2[t] = max(f2[t-1],f1) +m[x[i]][2];
			f += f2[t];
			if(f < bestf){
				Swap(x[i],x[t]);
				Backtrack(t+1);
				Swap(x[i],x[t]);
			}
			f1 -= m[x[i]][1];
			f -= f2[t];	
		}
	}
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m[i][1]>>m[i][2];
	}
	Init();
	Backtrack(1);
	cout<<"bestf="<<bestf<<endl;
	return 0;
}
/*
3
2 1
3 1
2 3
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65