批作业处理问题

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
66
67
68
public class seriesOfWork {
static int n = 5;//作业数量,其实用不到。。。
static int[] x = {1, 2, 3, 4, 5};//初始作业调度顺序
static int[] bestx = new int[x.length+1];//最优的作业调度顺序
static int f1;//机器1完成时间
static int[] f2 = new int[x.length+1];//机器2完成时间
static int f;//当前完成所有作业的时间
static int bestf=9999;//最优的时间

static int[][] chart = {

{0, 0, 0},
{0, 3, 5},
{0, 6, 1},
{0, 5, 2},
{0, 4, 4},
{0, 3, 2}};//调度方案


public static void main(String[] args) {
//int[] x = {1, 2, 3,4,5};
int[] temp=new int[x.length+1];
boolean isVisit[] = new boolean[x.length];
work( 0, x, temp, isVisit);
System.out.println("最优的作业调度方案:");
for(int i =1;i<temp.length;i++){
System.out.print(" "+temp[i]+" ");
}
System.out.println();
System.out.println("最优值为:");
System.out.println(bestf);
}

/**
* @param x 需要进行全排列的作业调度顺序
* @param index 指向“固定”的位置的指针,值为0时,指向第一个固定位置,也就是temp[0]
* @param temp 临时数组,用于存放被“固定”的作业
* @param isVisit 用来标记该作业是否已经被选择“固定”
*/
public static void work( int index, int[] x, int[] temp, boolean[] isVisit) {
if (index == x.length) {//结束递归条件
//System.out.println(Arrays.toString(temp));
for(int i=1;i<x.length+1;i++){//----------------------------------------核心代码
f1+=chart[temp[i]][1];
f2[i]=(Math.max(f2[i - 1], f1))+chart[temp[i]][2];
f+=f2[i];
}
if(f<bestf){
bestf=f;
for(int j=1;j<=x.length;j++){
bestx[j]=temp[j];
}
}
}

for (int i = 0; i < x.length; i++) {//遍历数组的每个数(作业)
if (!isVisit[i]) {//判断数是否被使用,如果未使用则继续后面的操作
temp[index+1] = x[i];//将该作业插入temp数组
isVisit[i] = true;//将该数标记为已使用
work( index + 1, x, temp, isVisit);//开始递归,插入下一个数
isVisit[i] = false;//执行到这一步的时候,说明有一个作业排列已经打印出来了,这时从后往前将每个作业重置为未访问使用
f1=0;
f=0;
}
}
}
}