18. 时序规划问题原则:
(1) 最紧迫的优先
实例 1:
6种部件作为一批等待一台机器加工。每一部件的平均周需求量、当前的存货水平以及加工一批所需时间如下表,你将如何安排各种部件的生产次序?
部 件 A B C D E F
平均需求量 10 4 26 34 7 3
当前存货量 72 21 48 92 28 23
加工时间 2.0 1.5 0.5 0.5 1.0 1.5
19. 时序规划问题
20. 时序规划问题
21. 时序规划问题以“加工时间最短者优先”为原则
22. 时序规划问题以“加工时间最短者优先”为原则
23. 时序规划问题(3) 到期日最近者原则
24. 时序规划问题(3) 到期日最近者原则
25. 时序规划问题(4) 延误的工作项目最少
第1步:运用先到期者优先的原则排出工作的初始次序。如果已经没有工作被延误,这便是最优解,否则,则进行第2步。
第2步:在安排的时序中找到1项延误的工作。
第3步:找出第2步所找工作之前(包括这一工作本身)加工时间最长的工作。
第4步:将这一工作从时序安排中抽出来,并更新相应的时间。如果仍然有被延误的工作,再转向第2步,否则转向第5步。
第5步:将第4步抽出的工作放到时序的末尾。
实例 3:沿用上述实例的8项工作,求解工作延误项数最少的时序。
为此我们采用上述五个步骤。
工 作 A B C D E F G H
加工时间 2 5 3 8 4 7 2 3
到期时间 13 7 8 30 14 20 2 36
26. 时序规划问题第1步:将工作按到期时间排序。
工 作 G B C A E F D H
到期时间 2 7 8 13 14 20 30 36
开始加工时间 0 2 7 10 12 16 23 31
加工时间 2 5 3 2 4 7 8 3
完成加工时间 2 7 10 12 16 23 31 34
延误工作 * * * *
第2步:在上述时序中,第1项被延误的工作是C。
第3步:到C之前,包括C在内,加工时间最长的工作是B,加工时间为5。
27. 时序规划问题第4步:抽出工作B,更新相关的时间:
工 作 G C A E F D H
到期时间 2 8 13 14 20 30 36
开始加工时间 0 2 5 7 11 18 26
加工时间 2 3 2 4 7 8 3
完成加工时间 2 5 7 11 18 26 29
第5步:现在已经没有工作被延误了,所以我们将工作B加到时序的最后。
工 作 G C A E F D H B
到期时间 2 8 13 14 20 30 36 7
开始加工时间 0 2 5 7 11 18 26 29
加工时间 2 3 2 4 7 8 3 5
完成加工时间 2 5 7 11 18 26 29 34
现在只有一项工作被延误,平均排队时间为98/8=12.25,平均延误时间为27/8=3.375天。
28. 时序规划问题(5) Johnson’s rule(约翰逊原则)
步骤1:列出各项工作及它们在每台机器上的加工时间。
步骤2:找出下一个在各台机器上加工时间最短的工作。
步骤3:如果这是在机器1上,尽量将这一工作安排在前面;如果这是在机器2上,尽量将这一工作安排在后面。在重复做这些的时候,总是从时序的两端向内进行,新安排的工作离时序的中间更近。
步骤4:不必再考虑这一工作,回到步骤2。如果再找不到这样的任务,这就是最优解。
实例 4:
有7项工作要顺序经过机器1和机器2加工。每项工作在每台机器上所需的加工时间如下,如何安排时序才能使机器利用率最高。
工作 A B C D E F G
机器1 2 5 10 8 4 12 9
机器2 14 7 3 10 5 6 6