一个存在工序制约的排程例子

小王开了一家店，做汽车喷漆和维修业务。星期一有６辆车等着维修。有３辆来自一个汽车租赁公司，小王承诺按照这３辆车交货时间维修。有３辆车来自一个汽车零售店，有１辆车要先维修，因为有顾客等着要。这种工序先后制约关系可以用下表表示。



每辆车的维修时间和完成期限见下表。
工序 1 2 3 4 5 6
作业时间　　　 2 3 4 3 2 1
交货时间 3 6 9 7 11 7
　按照设法将最大延迟时间最小化的原则安排汽车的维修顺序。
　求解：
　１，第１，找到最后安排的汽车。候选工序是没有后续工序的。３，５和６是候选工序。总作业时间2+3+4+3+2+1=15.(这是当前作业时间t). 目标是最小化最大延迟时间,我们比较这些工作的延迟时间，并选择一个最小值. 我们计算min{15-9, 15-11, 15-7}=min{6, 4, 8}=4, 结果是工序 5. 因此工序５应该最后安排（位置６）。
　２，接下来我们寻找应该第５个安排的工序。候选工序是３和６。这时候总加工时间15-2=13. 因此min{13-9, 13-7}=min{4,6}=4, 对应工序3. 因此工序３应该是第５个安排.
　３，下面寻找应该第４个安排的. 因为工序3 已经安排完了, 工序 2 变成候选. 当前值t=13-4=9. 我们比较min{9-6,9-7}=min{3,2}=2, 对应工序6。工序６第４个安排.
　４，接下来寻找第３个安排的. 工序６已经安排完了，工序４变成候选，和工序２同为候选, t=9-1=8. 计算最小min{8-6, 8-7}=min{2, 1}=1, 对应工序4.
　５，接下来寻找第２个安排的。就剩下工序１和工序２，因为工序前后关系约束，必须为１－２。
　总结上面结果，优化顺序的维修是1-2-4-6-3-5。
　各工序作业时间，延迟时间等数据见下表。
工序　作业时间　完成时间　交货时间　延迟时间
1 2 2 3 0
2 3 5 6 0
4 3 8 7 1
6 1 9 7 2
3 4 13 9 4
5 2 15 11 4
因此，最大延迟时间４天