D（π（i），j）表示工件π（i）在机器j上完成后释放的时间。D（π（i），0）表示工件i在第一台工件上的开始加工时间。计算公式如2-1至2-5所示：

D(π(1),0)=0;                                                      (2-1)

D(π(1),j)=P(π(1),1)+ P(π(1),2)+…+ P(π(1),j), j=1,2,。。m-1;         (2-2)

D(π(i),0)=D(π(i-1),1),i=2,3,…n;                                   (2-3)

D(π(i),j)=max{ D(π(i),j-1)+ P(π(i),j) , D(π(i-1),j+1)},

           i=2,3,…n , j=1,2,…m-1 ;       (2-4)

D(π(i),m)= D(π(i),m-1)+ P(π(i),m),i=1,2,…n;                      （2-5）

公式2-1：在第一台机器上的开始加工时间。

公式2-2：机器j上完成后释放π（1）的时间等于工件π（1）在前几台机器上的加工时间之和。

公式2-3：π（i）在第一台机器开始加工时间等于工件π（i-1）在第一台的结束时间，（前一台结束，后一台进去）。

公式2-4：π（i）在机器j上完成后释放π（i）的时间等于工件π（i）在机器j-1上完成后释放的时间加上工件π（i）在机器j上的加工时间与工件π（i-1）在第j+1台机器上的完成时间的最大值。

公式2-5：π（i）在第m台机器上的完成后释放时间等于工件π（i）在第m-1台机器上完成后释放时间加上π（i）在m上的加工时间+。

测试模型实例：

以四个工件，三台机器为例，在每台机器上的加工时间如表2-1所示：

表 2-1 测试数据

工 机  器

件      1 2 3

1 1 3 1

2 1 2 2

3 1 1 2

4 1 3 1

计算时间如下表2-2所示，默认加工顺序为{1,2,3,4}

表2-2 计算时间

工 机  器

件      1 2 3 4

D（π（1）） 0 1 4 5

D（π（2）） 1 4 6 8

D（π（3）） 4 6 8 10

D（π（4）） 6 8 11 12

由上表可知，最后一个工件离开最后一台机器的加工时间点为12，因此在该序列下的最小完工时间即为12。甘特图如图2-1所示： 群体智能算法求解阻塞流水车间调度问题研究(5):http://www.youerw.com/jisuanji/lunwen_125530.html