批处理作业调度
class Flowshop {
friend Flow(int**, int, int[]);
private:
void Backtrack(int i);
int **M, *x, *bestx, *f2, f1, f, bestf, n;
};
void Flowshop::Backtrack(int i) {
if (i > n) {
for (int j = 1; j <= n; j++) {
bestx[j] = x[j];
}
bestf = f;
} else {
for (int j = i; j <= n; j++) {
f1 += M[x[j]][1];
f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + M[x[j]][2];
f += f2[i];
if (f < bestf) {
Swap(x[i], x[j]);
Backtrack(i + 1);
Swap(x[i], x[j]);
}
f1 -= M[x[j]][1];
f -= f2[i];
}
}
}
int Flow(int **M, int n, int bestx[]) {
int ub = INT_MAX;
Flowshop X;
X.x = new int[n + 1];
X.f2 = new int[n + 1];
X.M = M;
X.n = n;
X.bestx = bestx;
X.bestf = ub;
X.f1 = 0;
X.f = 0;
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;
}
最后更新:
2024年1月14日 18:59:58
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42