Johnson 규칙 작업순서 (Flow Shop Scheduling)

S.M. Johnson이 1954년 제시한, 여러 작업(job)을 2대(또는 조건부 3대)의 기계에 같은 순서로 흘려보내는 흐름공정(flow shop)에서 총 완료시간(makespan)을 최소화하는 작업 순서 결정 규칙입니다. 모든 작업이 기계1 → 기계2 순으로 처리될 때, 단순 규칙만으로 최적해를 보장하는 몇 안 되는 스케줄링 알고리즘입니다.

① 모든 작업의 기계1·기계2 처리시간 중 가장 짧은 값을 찾습니다. ② 그 값이 기계1에 있으면 그 작업을 순서의 맨 앞에, 기계2에 있으면 맨 뒤에 배치합니다. ③ 배치한 작업을 제거하고 남은 작업으로 반복합니다. 앞은 왼쪽부터, 뒤는 오른쪽부터 채워 가운데에서 만납니다. 본 도구가 이 과정을 자동 수행하고 간트로 보여줍니다.

첫 작업이 기계1에 투입된 순간부터 마지막 작업이 기계2에서 완료되는 순간까지의 총 소요시간입니다. 흐름공정에서는 작업 순서에 따라 기계2의 대기(유휴)가 달라져 makespan이 크게 변합니다. Johnson 순서는 기계2의 초기 유휴를 최소화해 전체 완료를 앞당깁니다.

조건부로 가능합니다. 기계1의 최소시간 ≥ 기계2의 최대시간 또는 기계3의 최소시간 ≥ 기계2의 최대시간 중 하나가 성립하면, 기계1+기계2를 가상기계 G1, 기계2+기계3을 가상기계 G2로 합쳐 2대 문제로 변환해 Johnson 규칙을 적용합니다. 본 도구는 3대 입력 시 이 조건을 검사하고, 성립하지 않으면 근사 순서임을 안내합니다.

기계1에서 짧게 끝나는 작업을 먼저 처리하면 기계2가 일찍 일을 시작할 수 있어 초기 유휴가 줄어듭니다. 반대로 기계2에서 짧게 끝나는 작업을 맨 뒤로 보내면 마지막 마무리가 빨라집니다. 이 두 원리가 결합해 전체 흐름의 병목 대기를 최소화합니다.

전처리→가공, 도장→건조, 인쇄→코팅, 세척→검사처럼 모든 품목이 동일한 2단계를 같은 순서로 거치는 라인에 적합합니다. 다품종을 어떤 순서로 투입하느냐만으로 설비 증설 없이 완료시간을 줄일 수 있어, 준비교체 순서 최적화(교체순서 최적화)와 함께 쓰면 효과가 큽니다.

네. 총 처리시간(각 작업시간의 합)은 순서와 무관하지만, 기계2가 기계1을 기다리며 노는 유휴시간은 순서에 따라 달라집니다. Johnson 순서는 이 유휴를 최소화하므로 makespan이 짧아집니다. 본 도구는 입력 순서 대비 최적 순서의 makespan과 기계별 유휴를 나란히 비교해 절감 효과를 정량으로 보여줍니다.

① 2대(또는 조건부 3대) 흐름공정 전용이며 4대 이상 일반 문제는 최적을 보장하지 못합니다. ② 모든 작업이 같은 경로·순서를 따른다는 가정이 필요합니다(잡샵에는 부적합). ③ 작업 간 선후관계·납기·준비시간 의존성은 반영하지 않습니다. 병목이 있는 라인이라면 병목 분석으로 제약을 먼저 파악한 뒤 적용하는 것이 좋습니다.