制造业作业计划与控制.ppt

2021/4/9 * 二、两台机器排序问题 两个或更多的作业必须在两台机器上以相同的工序进行加工，要使加工周期最短，约翰逊于1954年提出了一个有效算法，那就是著名的Johnson算法。约翰逊算法包括以下几个步骤： （1）列出每个作业在两台机器上的加工时间。 （2）选择最短的加工时间，如果有两个相同的值，则任选一个。 （3）如果最短的加工时间来自第一台机器，那么先完成这个作业；如果来自第二台机器，那么这个作业就放在最后完成。然后从加工时间矩阵中划去已排序工件的加工时间。 （4）对于剩余的作业重复第二步和第三步，直到整个排序完成。 . 2021/4/9 * 【例】求如表所示的6/2/F/Fmax问题的最优解。 i 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4.5 将零件2排第1位 2 将零件3排第6位 2 3 将零件5排第2位 2 5 3 将零件6排第3位 2 5 6 3 将零件4排第5位 2 5 6 4 3 将零件1排第4位 2 5 6 1 4 3 . 2021/4/9 * 【例 题】 有5件任务都需要两步操作（先1后2）来完成，下表给出了相应的时间： （1）根据Johnson算法安排工作顺序； （2）计算加工周期。 任务 操作1所需时间（小时） 操作2所需时间（小时） A 3.0 1.2 B 2.0 2.5 C 1.0 1.6 D 3.0 3.0 E 3.5 1.5 . 2021/4/9 * 任务 操作1所需时间（小时） 操作2所需时间（小时） A 3.0 1.2 B 2.0 2.5 C 1.0 1.6 D 3.0 3.0 E 3.5 1.5 A,3.0 E,3.5 D,3 B,2 C,1 1.0 3.0 6.0 9.5 12.5 0 操作1 A, 1.2 E,1.5 D,3.0 B,2.5 C,1.6 2.6 5.5 9.0 11 13.7 操作2 . 2021/4/9 * A,3.0 E,3.5 D,3 B,2 C,1 1.0 3.0 6.0 9.5 12.5 0 操作1 A, 1.2 E,1.5 D,3.0 B,2.5 C,1.6 2.6 5.5 9.0 11 13.7 操作2 i C B D E A 操作1 操作2 . 2021/4/9 * 1. 将所有ai ≤ bi的工件按ai值不减的顺序排成一个序列A； 2. 将ai＞bi的工件按bi值不增的顺序排成一个序列B； 3. 将A放到B之前，就构成了一个最优加工顺序。 改进算法 . 2021/4/9 * 工件号 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4 工件最优顺序：2 5 6 1 4 3 1 3 4 5 5 8 2 7 4 7 4 2 4 8 13 18 26 3 11 15 22 26 28 ai bi 最优顺序下的加工周期为28 . 2021/4/9 * 练 习 某公司要生产4种产品，需要两台机器1和2。其中，有3种产品需要先在机器1上加工。下表给出了两台机器上加工各产品所需的时间。 （1）安排生产顺序，使得在最短时间内完成生产。 （2）机器1共需工作多长时间？ （3）机器2应该在机器1开始工作后多长时间开始运转？ 任务 在机器1上加工所需时间（小时） 在机器2上加工所需时间（小时） A 3.2 2.10 B 2.5 1.25 C 1.7 3.00 D 2.1 0 . 2021/4/9 * 任务 在机器1上加工所需时间（小时） 在机器2上加工所需时间（小时） A 3.2 2.10 B 2.5 1.25 C 1.7 3.00 D 2.1 0 9.5 B,1.25 A,2.10 C,3.00 D,2.1 B,2.5 A,3.2 C,1.7 1.7 4.9 7.4 4.7 6.8 8.6