존슨규칙 (Johnson's Rule)

한 줄 정의: 두 대의 기계를 거치는 여러 작업의 총 완료시간(메이크스팬)을 최소화하기 위한 작업 순서를 구하는 대표적인 2단계 플로우숍 스케줄링 알고리즘입니다.

쉽게 풀면

여러 개의 작업이 순서대로 기계1과 기계2를 거쳐야 하는 상황을 떠올려 보세요. 존슨규칙은 각 작업의 첫 번째 기계 작업시간과 두 번째 기계 작업시간을 비교해서, 첫 번째 기계 시간이 더 짧은 작업은 앞쪽에, 두 번째 기계 시간이 더 짧은 작업은 뒤쪽에 배치하는 간단한 규칙입니다. 이렇게 배치하면 기계가 노는 시간(유휴시간)을 줄여서 모든 작업이 끝나는 시점을 최대한 앞당길 수 있습니다. 마치 세탁기와 건조기를 순서대로 써야 할 때, 세탁이 빨리 끝나는 옷을 먼저 넣는 것과 비슷한 원리입니다.

왜 중요한가

존슨규칙은 2기계 플로우숍 문제에서 최적해를 다항시간 안에 구할 수 있는 몇 안 되는 방법 중 하나로, 스케줄링 이론의 기초로 자주 인용됩니다. 실제 생산현장의 복잡한 스케줄링 문제를 풀기 위한 휴리스틱이나 메타휴리스틱을 개발할 때도 비교 기준(벤치마크)으로 널리 활용됩니다.

논문에서는 이렇게 쓰입니다

"2기계 플로우숍 환경에서 존슨규칙을 적용하여 최적 작업순서를 도출하고, 이를 초기해로 사용하는 유전 알고리즘을 제안하였다."

존슨규칙으로 구한 해를 메타휴리스틱 알고리즘의 초기 시작점으로 활용하는 연구 흐름을 설명합니다.

"기계 대수가 3대 이상으로 확장된 문제에서는 존슨규칙을 직접 적용할 수 없어, 이를 근사적으로 확장한 휴리스틱을 설계하였다."

존슨규칙이 2기계 환경에 한정된 한계를 보완하기 위한 후속 연구 배경을 설명합니다.

조금 더 깊게 보면

존슨규칙의 절차는 모든 작업 중 가장 짧은 처리시간을 찾아, 그것이 기계1의 시간이면 순서의 맨 앞에, 기계2의 시간이면 순서의 맨 뒤에 배정하고 해당 작업을 목록에서 제외한 뒤 이 과정을 반복하는 방식으로 이루어집니다. 이 절차는 정확히 최적해를 보장하는 것으로 알려져 있으며, 이후 3기계 이상 또는 병렬기계 환경으로 확장하려는 다양한 변형 연구가 이루어져 왔습니다.

주의할 점

존슨규칙은 기본적으로 기계가 2대이고 모든 작업이 같은 순서(기계1 다음 기계2)로 처리되는 순수 플로우숍 상황에만 최적성이 보장됩니다. 기계 대수가 늘어나거나 작업 순서가 작업마다 다르면 이 규칙을 그대로 적용할 수 없습니다.