5개 작업이 동일한 순서(기계1 → 기계2)로 두 대의 기계에서 처리되… | [가맹거래사 1차] 23년 1회차 기출문제 상세 페이지

존슨의 규칙을 적용한 최적 작업순서는 A - E - D - C - B이다.
존슨의 규칙은 두 기계의 작업시간을 모두 놓고 가장 짧은 값을 찾아, 그 값이 기계1에 있으면 순서의 맨 앞에, 기계2에 있으면 맨 뒤에 배치한 뒤 해당 작업을 제외하고 같은 절차를 반복하는 방법이다.
주어진 시간은 A(3, 5), B(4, 2), C(6, 4), D(6, 6), E(5, 7)이다. 전체 최소값 2는 B의 기계2 시간이므로 B를 맨 뒤에 두고, 다음 최소값 3은 A의 기계1 시간이므로 A를 맨 앞에 둔다.
남은 C·D·E 중 최소값 4는 C의 기계2 시간이라 C를 뒤에서 두 번째에 두고, 이어 최소값 5는 E의 기계1 시간이라 E를 앞에서 두 번째에 두면 D가 가운데에 남는다.
이 순서의 총완료시간(makespan)은 27로, 나머지 보기의 순서들(A-B-C-D-E는 32, A-B-E-C-D는 30, B-A-C-E-D는 31, B-C-A-D-E는 32)보다 짧다.