调整方案对比及最佳路线分析

每个零件都要经过车、铣、刨三道一定顺序的工艺过程。A、B、C、D四个零件原计划分别在四台车床、四台铣床、四台刨床上平行地进行加工。但到临加工时，只有一台车床、一台铣床、一台刨床可用。在保证车、铣、刨这三道加工顺序不变的基础上，每台机器各应当先加工哪个零件，可以使总工期推迟最小？

画出CPM网络图，给出每个节点的时间参数以及各个工序的工期（图6-10）。

图6-10　工程施工网络图

第1道工序调整为A1→B1→C1→D1时：

（1）新增路线有，，，，，，其中EFA1B1＞ESB1，EFA1B1C1＞ESC1，EFA1B1C1D1＞ESD1，由连续链定理可知，＞，＞＞，则只需要计算

最大值为49。

（2）若TA2＜TB1，TB2＜TC1+TD1，则第2道工序调整为A2→B2→C2→D2，新增路线有，，，，，，，，，，需要计算=42，=42，=44，=48，=50，=49，最大值为50。

（3）若TB2＜TA3＜TB2+TC2，TB3＞[TC2-（TA3-TB2）]+TD2，则第3道工序调整为A3→B3→C3→D3或A3→B3→D3→C3。(www.xing528.com)

1）当第3道工序调整为A3→B3→C3→D3时，按以上方式，找到新增路线并计算出路长最大值为63。

2）当第3道工序调整为A3→B3→D3→C3时，路长最大值为61。

最终可得两套可行方案如下。

1）A1→B1→C1→D1，A2→B2→C2→D2，A3→B3→C3→D3。最大路长为63，推迟总工期为63-37=26。

2）A1→B1→C1→D1，A2→B2→C2→D2，A3→B3→D3→C3。最大路长为61，推迟总工期为61-37=24。

由此可得最佳调整方案为第二套。其中第二套调整方案的网络图如图6-11所示，计算时间参数，所得关键路线路长为61，本算法得证。

同理可以得到其他调整方案中的最佳方案。

图6-11　第二套调整方案网络图