컨티스 툴킷

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

작업별 기계1·기계2(조건부 기계3) 처리시간을 입력하면 Johnson 알고리즘으로 총 완료시간(makespan)을 최소화하는 최적 작업 순서를 찾아, 입력 순서 대비 완료시간·기계 유휴를 간트 차트로 비교합니다.

계산 근거

Johnson(1954) 2기계 흐름공정 규칙으로 makespan 최소 순서를 구합니다. 3기계는 min M1 ≥ max M2 또는 min M3 ≥ max M2일 때 (M1+M2, M2+M3) 2기계로 바꿔 같은 규칙을 쓰고, 조건을 충족하지 않으면 작업 8개 이하는 모든 순서를 비교, 9개 이상은 근사해로 표시합니다. 이론 하한 = 기계별 (앞 기계 최소 합 + 총 가공 + 뒤 기계 최소 합)의 최댓값.

검증
기본 예시 손 검산: 순서 B→D→C→E→A, 완료시간 30분(입력 순서 34분, 11.8% 단축)
최종 검토
2026-10-22 · CONTIS 툴킷 편집팀
함께 쓰는 양식

자주 묻는 질문 (FAQ)

Johnson 규칙(Johnson's Rule)이란 무엇인가요?
S.M. Johnson이 1954년 제시한, 여러 작업(job)을 2대(또는 조건부 3대)의 기계에 같은 순서로 흘려보내는 흐름공정(flow shop)에서 총 완료시간(makespan)을 최소화하는 작업 순서 결정 규칙입니다. 모든 작업이 기계1 → 기계2 순으로 처리될 때, 단순 규칙만으로 최적해를 보장하는 몇 안 되는 스케줄링 알고리즘입니다.
2대 기계 Johnson 알고리즘은 어떻게 동작하나요?
① 모든 작업의 기계1·기계2 처리시간 중 가장 짧은 값을 찾습니다. ② 그 값이 기계1에 있으면 그 작업을 순서의 맨 앞에, 기계2에 있으면 맨 뒤에 배치합니다. ③ 배치한 작업을 제거하고 남은 작업으로 반복합니다. 앞은 왼쪽부터, 뒤는 오른쪽부터 채워 가운데에서 만납니다. 본 도구가 이 과정을 자동 수행하고 간트로 보여줍니다.
makespan(총 완료시간)은 무엇을 의미하나요?
첫 작업이 기계1에 투입된 순간부터 마지막 작업이 기계2에서 완료되는 순간까지의 총 소요시간입니다. 흐름공정에서는 작업 순서에 따라 기계2의 대기(유휴)가 달라져 makespan이 크게 변합니다. Johnson 순서는 기계2의 초기 유휴를 최소화해 전체 완료를 앞당깁니다.
3대 기계에도 적용할 수 있나요?
조건부로 가능합니다. 기계1의 최소시간 ≥ 기계2의 최대시간 또는 기계3의 최소시간 ≥ 기계2의 최대시간 중 하나가 성립하면, 기계1+기계2를 가상기계 G1, 기계2+기계3을 가상기계 G2로 합쳐 2대 문제로 변환해 Johnson 규칙을 적용합니다. 본 도구는 3대 입력 시 이 조건을 검사하고, 성립하지 않으면 작업 8개 이하는 모든 순서를 비교해 최적을 찾고 9개 이상은 근사 순서임을 안내합니다.
왜 가장 짧은 작업을 앞뒤로 나눠 배치하나요?
기계1에서 짧게 끝나는 작업을 먼저 처리하면 기계2가 일찍 일을 시작할 수 있어 초기 유휴가 줄어듭니다. 반대로 기계2에서 짧게 끝나는 작업을 맨 뒤로 보내면 마지막 마무리가 빨라집니다. 이 두 원리가 결합해 전체 흐름의 병목 대기를 최소화합니다.
어떤 현장에 적용하기 좋은가요?
전처리→가공, 도장→건조, 인쇄→코팅, 세척→검사처럼 모든 품목이 동일한 2단계를 같은 순서로 거치는 라인에 적합합니다. 다품종을 어떤 순서로 투입하느냐만으로 설비 증설 없이 완료시간을 줄일 수 있어, 준비교체 순서 최적화(교체순서 최적화)와 함께 쓰면 효과가 큽니다.
작업 순서를 바꾸는 것만으로 정말 시간이 줄어드나요?
네. 총 처리시간(각 작업시간의 합)은 순서와 무관하지만, 기계2가 기계1을 기다리며 노는 유휴시간은 순서에 따라 달라집니다. Johnson 순서는 이 유휴를 최소화하므로 makespan이 짧아집니다. 본 도구는 입력 순서 대비 최적 순서의 makespan과 기계별 유휴를 나란히 비교하고, 목표 완료시간을 넣으면 순서만으로 맞출 수 있는지(이론 하한 비교)까지 판정합니다.
Johnson 규칙의 한계는 무엇인가요?
① 2대(또는 조건부 3대) 흐름공정 전용이며 4대 이상 일반 문제는 최적을 보장하지 못합니다. ② 모든 작업이 같은 경로·순서를 따른다는 가정이 필요합니다(잡샵에는 부적합). ③ 작업 간 선후관계·납기·준비시간 의존성은 반영하지 않습니다. 병목이 있는 라인이라면 병목 분석으로 제약을 먼저 파악한 뒤 적용하는 것이 좋습니다.

공정을 다시 설계하다

병목·가치흐름·생산성을 근본부터 개선하는 프로세스 혁신 컨설팅으로 현장을 바꿉니다.

프로세스 혁신 컨설팅 보기 상담 문의

함께 보면 좋은 아티클

다른 도구 보기

실무 도구·자료 업데이트 받기

새 계산기·체크리스트와 스마트팩토리·제조혁신 실무 자료를 이메일로 보내드립니다. 언제든 수신거부할 수 있습니다.