批处理作业调度

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
回到页面顶部