(LBFSP)中间存储有限流水车间的最大完工时间Cmax的2种计算方法(含c++源代码)

    查阅文献时，发现中间存储有限的流水车间在计算最大完工时间时，常出现两种计算方式，一种用开始时间计算，另一种用完工时间计算：

(1) 用开始时间计算

(代表工件在机器上的加工时间，代表机器与之间的缓冲区容量)

()

 (2) 用完工时间计算

(代表工件在机器上的加工时间，代表机器与之间的缓冲区容量)

    两种方式计算出来的结果是一样的，但要注意的是，第1种方式求出来的矩阵指的是各工序的最早可以开始加工的时间点， 而第2种方式求出来的矩阵指的是各工序的最晚可以结束加工的时间点，因此两者画出来的甘特图略有差别，如下图所示： 

    从图中可以看出，按第1种方式求解画出的甘特图，相当于对所有的存在空闲的加工时间块进行了左移操作，而第2种方式则是进行了右移操作；对于不存在空闲的加工时间块，两种求解方式的甘特图是一致的，这也是它们求解出来的一致的原因。

    同样的原理可以应用到一般的置换流水车间调度问题(PFSP)的求解当中。

附：

(1) 用开始时间计算LBFSP的源代码

/* 中间存储有限Cmax计算(使用开始时间计算) */
// solution -- 可行解(排列)，如 π = {1,2,...,n}
// T -- 加工时间矩阵，T[π(i) - 1][j - 1]即P[π(i)][j]
// buffer -- buffer[i] (0 ≤ i ≤ n-1) 为机器i+1与机器i+2间的缓冲区容量
vector<vector<double>> calculate_makespan_start_time(const vector<int>& solution, const vector<vector<double>>& T, const vector<int>& buffer) {int n = solution.size(), m = T[0].size();vector<vector<double>> S(n, vector<double>(m, 0));  //调度（完工时间）矩阵，size = (n, m)，存放各机器上的调度结果// 1. S(π1,1) = 0//S[0][0] = 0;// 2. S(π1,j) = S(π1,j - 1) + P(π1,j - 1)  j = 2, 3, ... , mfor (int j = 1; j < m; j++){S[0][j] = S[0][j - 1] + T[solution[0] - 1][j - 1];}for (int i = 1; i < n; i++) {// j = 0 时// 3. S(πi,1) = S(π(i - 1),1) + P(π(i - 1),1)  i ≤ B1 + 1if (i < buffer[0] + 1) S[i][0] = S[i - 1][0] + T[solution[i - 1] - 1][0];// 4. S(πi,1) = max( S(π(i - 1),1) + P(π(i - 1),1), S[i - B1 - 1][2] )  i ＞ B1 + 1else S[i][0] = max(S[i - 1][0] + T[solution[i - 1] - 1][0], S[i - buffer[0] - 1][1]);for (int j = 1; j < m - 1; j++) {// 5. S(πi,j) = max( S(π(i - 1),j) + P(π(i - 1),j), S(π(i),j - 1) + P(π(i),j - 1) )  i ≤ Bj + 1, 2 ≤ j ≤ m - 1if (i < buffer[j] + 1) S[i][j] = max(S[i - 1][j] + T[solution[i - 1] - 1][j], S[i][j - 1] + T[solution[i] - 1][j - 1]);/* 6. S(πi,j) = max( S(π(i - 1),j) + P(π(i - 1),j), S(π(i),j - 1) + P(π(i),j - 1), S(π(i - Bj - 1), j + 1) )i ＞ Bj + 1, 2 ≤ j ≤ m - 1  */else S[i][j] = max(max(S[i - 1][j] + T[solution[i - 1] - 1][j], S[i][j - 1] + T[solution[i] - 1][j - 1]), S[i - buffer[j] - 1][j + 1]);}// j = m - 1 时// 7. S(πi,m) = max( S(π(i - 1),m) + P(π(i - 1),m), S(π(i),m - 1) + P(π(i),m - 1) )S[i][m - 1] = max(S[i - 1][m - 1] + T[solution[i - 1] - 1][m - 1], S[i][m - 2] + T[solution[i] - 1][m - 2]);}// 如果只求Cmax，返回 S[n - 1][m - 1] + T[solution[i] - 1][j] 即可// 这里求的是开始时间矩阵S(πi,j)，用于画调度结果的甘特图return S;
}

(2) 用完工时间计算LBFSP的源代码

/* 中间存储有限Cmax计算(使用完工时间计算) */
// solution -- 可行解(排列)，如 π = {1,2,...,n}
// T -- 加工时间矩阵，T[π(i) - 1][j - 1]即P[π(i)][j]
// buffer -- buffer[i] (0 ≤ i ≤ n-1) 为机器i+1与机器i+2间的缓冲区容量
vector<vector<double>> calculate_makespan(const vector<int>& solution, const vector<vector<double>>& T, const vector<int>& buffer) {int n = solution.size(), m = T[0].size();vector<vector<double>> C(n, vector<double>(m, 0));  //调度（完工时间）矩阵，size = (n, m)，存放各机器上的调度结果// 1. C(π1,1) = P(π1,1)C[0][0] = T[solution[0] - 1][0];// 2. C(π1,j) = C(π1,j - 1) + P(π1,j)  2 ≤ j ≤ mfor (int j = 1; j < m; j++){C[0][j] = C[0][j - 1] + T[solution[0] - 1][j];}for (int i = 1; i < n; i++) {// j = 0 时// 3. C(πi,1) = C(π(i - 1), 1) + P(πi, 1)  i ≤ B1 + 1if (i < buffer[0] + 1) C[i][0] = C[i - 1][0] + T[solution[i] - 1][0];// 4. C(πi,1) = max( C(π(i - 1), 1) + P(πi, 1), C(π(i - B1 - 1), 2) )  i ＞ B1 + 1else C[i][0] = max(C[i - 1][0] + T[solution[i] - 1][0], C[i - buffer[0] - 1][1]);for (int j = 1; j < m - 1; j++) {// 5. C(πi,j) = max{C(π(i - 1), j), C(πi, j - 1)} + P(πi, j)  i ≤ Bj + 1, 2 ≤ j ≤ m - 1if (i < buffer[j] + 1) C[i][j] = max(C[i - 1][j], C[i][j - 1]) + T[solution[i] - 1][j];/* 6. C(πi,j) = max(max( C(π(i - 1), j), C(πi, j - 1) ) + P(πi, j), C(π(i - Bj - 1), j + 1) )i ＞ Bj + 1, 2 ≤ j ≤ m - 1  */else C[i][j] = max(max(C[i - 1][j], C[i][j - 1]) + T[solution[i] - 1][j], C[i - buffer[j] - 1][j + 1]);}// j = m - 1 时// 7. C(πi,m) = max( C(π(i - 1), m), C(πi, m - 1) ) + P(πi, m)C[i][m - 1] = max(C[i - 1][m - 1], C[i][m - 2]) + T[solution[i] - 1][m - 1];}// 如果只求Cmax，返回 C[n - 1][m - 1] 即可// 这里求的是完工时间矩阵C(πi,j)，用于画调度结果的甘特图return C;
}

参考文献：

[1]    WANG L, ZHANG L, ZHENG D. An effective hybrid genetic algorithm for flow shop scheduling with limited buffers[J]. Computers & Operations Research, 2006,33(10): 2960-2971.

[2]    王鹏飞. 群智能优化算法及在流水车间调度问题中的应用研究[D]. 吉林大学, 2019.