플로우 샵 스케줄링은 생산 및 제조 시스템에서 다수의 작업(job)들이 동일한 순서로 배열된 여러 작업장(machine 또는 작업 단계)을 연속적으로 통과하도록 배정되는 일정 계획 문제를 가리키는 용어이다. 영어 원어는 flow shop scheduling이며, 한국어로는 흔히 “플로우샵 일정” 또는 “플로우 샵 스케줄링”이라고 번역된다.
정의
플로우 샵 스케줄링은 다음과 같은 기본 가정을 전제로 한다.
- 작업 집합 $J = {J_1, J_2, \dots , J_n}$ 가 존재한다. 각 작업은 고정된 순서로 $m$개의 작업장을 통과한다.
- 작업장 집합 $M = {M_1, M_2, \dots , M_m}$ 가 존재한다. 모든 작업은 동일한 순서 $(M_1 \rightarrow M_2 \rightarrow \dots \rightarrow M_m)$ 로 진행한다.
- 각 작업 $J_i$ 가 작업장 $M_k$ 에서 수행되는 처리 시간 $p_{ik}$ 가 미리 알려져 있다.
- 작업장은 한 번에 하나의 작업만 처리할 수 있으며, 작업은 작업장에 도착하면 즉시 시작하거나 대기할 수 있다.
- 작업의 선행 관계는 없으며, 모든 작업은 동일한 순서를 따라야 한다(‘퍼뮤테이션' 플로우샵) 또는 순서를 달리 할 수 있는 경우(‘비퍼뮤테이션' 플로우샵)도 존재한다.
주요 목적 함수
플로우 샵 스케줄링에서는 일반적으로 다음과 같은 목적 함수 중 하나를 최소화한다.
- 전체 완료 시간 (makespan, $C_{\max}$): 마지막 작업이 마지막 작업장을 떠나는 시점.
- 총 지연 시간 (total tardiness), 총 흐름 시간 (total flow time), 총 가동 중단시간 (total idle time) 등.
대표적 알고리즘 및 이론적 성질
- Johnson’s Rule (존슨 알고리즘)
두 작업장($m=2$)인 경우, Johnson’s Rule은 $C_{\max}$을 최적화하는 다항식 시간 알고리즘으로 알려져 있다. 작업을 두 그룹으로 나누어 순서를 정한다. - NP‑Hardness
작업장이 세 개 이상($m \ge 3$)인 경우, 일반적인 플로우 샵 스케줄링 문제는 NP‑hard임이 증명되어 있다. 따라서 정확한 최적 해를 찾기 위해서는 완전 탐색, 분할정복, 정수선형계획(ILP) 등 복잡도 높은 방법이 필요하다. - 휴리스틱 및 메타휴리스틱
실제 제조 현장에서는 근사해를 구하기 위해 다음과 같은 방법이 널리 사용된다.- NEH 알고리즘 (Nawaz, Enscore, Ham) : 작업 순서를 점진적으로 구성하는 휴리스틱.
- 시뮬레이티드 어닐링, 유전 알고리즘, 입자 군집 최적화 등 메타휴리스틱.
- 퍼뮤테이션 vs. 비퍼뮤테이션
퍼뮤테이션 플로우샵에서는 모든 작업이 동일한 순서로 작업장을 통과한다. 비퍼뮤테이션에서는 작업마다 순서가 달라질 수 있어 해 공간이 훨씬 넓다.
응용 분야
플로우 샵 스케줄링은 다음과 같은 분야에서 적용된다.
- 자동차 조립 라인, 전자제품 제조, 식품 가공 등 다단계 생산 시스템.
- 반도체 제조 공정에서의 웨이퍼 처리 순서 최적화.
- 물류센터에서의 픽킹 및 포장 작업 배정.
관련 연구 및 학술 자료
플로우 샵 스케줄링은 운영관리(Operations Management), 생산공학(Production Engineering), 그리고 컴퓨터 과학(특히 조합 최적화) 분야에서 활발히 연구되고 있다. 주요 학술지로는 European Journal of Operational Research, Computers & Operations Research, International Journal of Production Research 등이 있다. 또한, 국제 학술대회인 International Conference on Production Research (ICPR) 및 Conference on the Practice and Theory of Automated Timetabling (PATAT)에서도 관련 논문이 정기적으로 발표된다.
한계 및 현재 이슈
- 실시간 스케줄링: 변동성이 큰 주문량이나 설비 고장에 대응하기 위한 동적 스케줄링 기법 개발이 진행 중이다.
- 다목적 최적화: 단일 목표(예: makespan) 외에도 에너지 소비, 작업자 피로도, 설비 유지보수 등을 동시에 고려하는 연구가 증가하고 있다.
- 데이터 기반 접근: 머신러닝을 활용한 처리시간 예측 및 스케줄링 정책 자동 생성 연구가 초기 단계에서 활발히 진행 중이다.
이 항목은 현재까지 확보된 공신력 있는 자료에 기반하여 작성되었으며, 최신 연구 동향은 지속적으로 업데이트될 수 있다.
