算法制造

1. 约翰逊算法的公式

为了便于阐述约翰逊法的具体做法，下面结合一个例子来进行说明：
约翰逊法
约翰逊法
例：有五个工件在二台设备上加工，加工顺序相同，先在设备1上加工，再在设备2上加工，工时列于下表1中，用约翰逊法排序。
表1 加工工时表
具体步骤为：
第一步，取出最小工时t12=2。如该工时为第一工序的，则最先加工；反之，则放在最后加工。此例是A工件第二工序时间，按规则排在最后加工。
第二步，将该已排序工作划去。
第三步，对余下的工作重复上述排序步骤，直至完毕。此时t21=t42=3，B工件第一工序时间最短，最先加工；D工件第二工序时间最短，排在余下的工件中最后加工。最后得到的排序为：B-C-E-D-A。整批工件的停留时间为27分钟。
更一般的情况是工件加工顺序不同，称为随机性排序。由杰克逊对约翰逊法稍加改进后得到求解方法，称为杰克逊算法。