现有五个工件需在设备M1、M2上加工,加工顺序相同,即先在设备M1上加工,后在设备M2上加工,所需工时列于下表。请用约翰逊算法确定最优加工顺序,并说明应用约翰逊算法进行排序的步骤。(时间单位:分钟)
   
【正确答案】(1)按约翰逊算法可得最优加工顺序为:
   B→C→E→D→A。
   (2)应用约翰逊法则进行排序的步骤:
   ①从工件在两台设备上的加工时间中,找出最小值,若同时有两个或几个相同的最小值,则任选一个。
   ②若最小值出现在前一台设备上,则该工件应最先加工,若出现在后一台设备上,则该工件应最后加工。
   ③将已排加工顺序的工件除去,再重复①、②,照此思路,直到把所有工件排完。
【答案解析】