一道+ / edao.plus
#10073

双工序加工·最短总工时

杂题六年级#约翰逊规则
题目

一批工件共 5 件（A、B、C、D、E），每件都要先在机床甲上加工，再到机床乙上加工（顺序不能颠倒；同一机床一次只能加工一件）。

各工件在两台机床上需要的时间（单位：小时）见下表。请合理安排 5 件工件在机床甲上的加工顺序，使全部完成的总工时最短。

最短总工时是多少？

解法

  1. 约翰逊规则：甲≤乙的A,C按甲升序(A→C)；甲>乙的B,D,E按乙降序(E→D→B)。总序A→C→E→D→B，乙在27小时完工。

    A：甲 0–3，乙 3–9
    =乙空等 3，做 6
    C：甲 3–7，乙 9–16
    =乙接着做 7
    E：甲 7–13，乙 16–20
    =乙接着做 4
    D：甲 13–18，乙 20–23
    =乙接着做 3
    B：甲 18–25，乙 25–27
    =乙等到甲做完 B 再做 2
    最短总工时
    =27 小时

练一练

4 件工件在甲、乙两台机床上先后加工，用时如下：A(2,5), B(6,3), C(4,6), D(5,2)。请排出甲上的顺序使总工时最短，最短总工时是多少小时？

相关题目

#10067 装信错排·欧拉问题
递推法 / 容斥原理 / 枚举法
杂题六年级
#10075 物资调运·最省运费
最优化 / 方程法
杂题六年级