122. 123. 124.
X.f1=0; X.f=0;
125. 126. 127. 128. 129. 130. 131. 132. 133.
for(int i=0;i<=n;i++) {
X.f2[i]=0,X.x[i]=i; } X.Backtrack(1); delete []X.x; delete []X.f2; return X.bestf;
38.
}
39.
cout<<"M(i,j)值如下："<<endl;
40.
41.
for(int i=0;i<=n;i++)
42.
{
43.
for(int j=0;j<3;j++)
44.
{
45.
M[i][j]=M1[i][j];
46.
}
} 47.
48. int bestx[4];
49. for(int i=1;i<=n;i++)
63.
}
64.
delete []M;
65.
66.
M=0;
67.
68.
cout<<endl<<"最优值是："<<bf<<endl;
69.
cout<<"最优调度是：";
70.
7Байду номын сангаас.
for(int i=1;i<=n;i++)
72.
{
73.
cout<<bestx[i]<<" ";
74.
}
cout<<endl; 75.
批处理作业调度问题要求对于给定的 n 个作业，制定最佳作业调度方案，使其完成时 间和达到最小。
例：设 n=3，考虑以下实例：
这 3 个作业的 6 种可能的调度方案是 1,2,3；1,3,2；2,1,3；2,3,1； 3,1,2；3,2,1；它们所相应的完成时间和分别是 19，18，20，21， 19，19。易见，最佳调度方案是 1,3,2，其完成时间和为 18。
111. {
112.
int ub=30000;
113.
114.
Flowshop X;
115. 116. 117.
X.n=n; X.x=new int[n+1]; X.f2=new int[n+1];
118. 119. 120. 121.
X.M=M; X.bestx=bestx; X.bestf=ub;
134. }
135. 136. template <class Type>
137. inline void Swap(Type &a, Type &b)
return 0; 76.
77. }
78. 79. void Flowshop::Backtrack(int i)
80. {
81. if (i>n)
82.
{
83.
for (int j=1; j<=n; j++)
84.
{
85.
bestx[j] = x[j];
86.
}
87.
bestf = f;
88.
}
89. else
98.
if (f < bestf)//剪枝
99.
{
100.
Swap(x[i], x[j]);
101.
Backtrack(i+1);
102.
Swap(x[i], x[j]);
103. 104. 105. 106. 107.
} f1-=M[x[j]][1]; f-=f2[i]; } }
108. }
109. 110. int Flow(int **M,int n,int bestx[])
50. {
51. cout<<"(";
52. for(int j=1;j<3;j++)
53. cout<<M[i][j]<<" ";
54. cout<<")";
55.
56. }
57.
58.
bf=Flow(M,n,bestx);
59.
60.
for(int i=0;i<=n;i++)
61.
{
62.
delete []M[i];
8.
private:
9.
void Backtrack(int i);
10.
11.
int **M, // 各作业所需的处理时间
12.
*x,
// 当前作业调度
13.
*bestx, // 当前最优作业调度
14.
15.
*f2, // 机器 2 完成处理时间
16.
f1, // 机器 1 完成处理时间
17.
f,
// 完成时间和
18.
19.
bestf, // 当前最优值
20.
n; // 作业数
21. };
22.
23. int Flow(int **M,int n,int bestx[]);
24.
25. template <class Type>
26. inline void Swap(Type &a, Type &b);
(2)算法设计
批处理作业调度问题要从 n 个作业的所有排列中找出具有最小完成 时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗 排列树。按照回溯法搜索排列树的算法框架，设开始时 x=[1,2,……n]是 所给的 n 个作业，则相应的排列树由 x[1:n]的所有排列构成。
算法具体代码如下：
[cpp] view plain copy
1. #include "stdafx.h"
2. #include <iostream>
3. using namespace std;
4. 5. class Flowshop
6. {
7.
friend int Flow(int **M,int n,int bestx[]);
90. {
91.
for (int j = i; j <= n; j++)
92.
{
93.
f1+=M[x[j]][1];
94.
//机器 2 执行的是机器 1 已完成的作业，所以是 i-1
95.
f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];
96.
97.
f+=f2[i];
1、批作业调度问题
(1)问题描述
给定 n 个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器 1 处 理，然后由机器 2 处理。作业 Ji 需要机器 j 的处理时间为 tji。对于一 个确定的作业调度，设 Fji 是作业 i 在机器 j 上完成处理的时间。所有 作业在机器 2 上完成处理的时间和称为该作业调度的完成时间和。
27.
28. int main()
29. {
30. int n=3,bf;
31.
int M1[4][3]={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};
32.
33.
int **M=new int*[n+1];
34.
35.
for(int i=0;i<=n;i++)
36.
{
37.
M[i]=new int[3];