작업장스케줄링 (Job Shop Scheduling)
쉽게 풀면
여러 손님이 각각 다른 순서로 병원의 여러 검사실을 돌아야 한다고 생각해보면 됩니다. 어떤 손님은 엑스레이부터 찍고 혈액검사를 받아야 하고, 다른 손님은 반대 순서로 진행해야 할 수도 있습니다.
작업장스케줄링은 이렇게 각 작업(손님)마다 거쳐야 할 기계(검사실)의 순서가 서로 다를 때, 전체적으로 가장 효율적으로 순서를 짜는 문제를 다룹니다. 순서가 제각각이라 흐름작업스케줄링보다 훨씬 복잡합니다.
잡샵스케줄링은 여러 작업들이 저마다 다른 순서로 여러 기계를 거쳐가야 하는 생산 환경에서, 각 기계에 작업을 어떤 순서로 배정할지를 정하는 문제입니다.
왜 중요한가
다품종 소량 생산이나 주문형 제조 환경에서는 제품마다 필요한 공정 순서가 다르기 때문에 작업장스케줄링 문제가 빈번하게 발생합니다. 산업공학에서는 이 문제를 잘 풀수록 납기 준수율과 설비 가동률을 높이고 전체 생산시간(메이크스팬)을 줄일 수 있어 생산성 향상에 직결됩니다.
작업마다 필요한 기계와 경로가 제각각인 다품종 소량생산 환경을 대표하는 문제로, 조합의 경우의 수가 작업과 기계 수에 따라 폭발적으로 늘어나는 대표적인 NP-난해 문제로 다뤄집니다.
핵심 정리
- 고전적 작업장스케줄링에서는 n개의 작업이 각각 정해진 기계 순서(경로)대로 m대의 기계를 거치고, 한 기계는 한 번에 한 작업만 처리하며, 한 작업은 한 번에 한 기계에서만 처리됩니다. 정할 것은 각 기계에서의 작업 순서(그리고 그에 따른 시작 시각)입니다.
- 표준 표기로는 J||Cmax(작업장, 목적함수 메이크스팬 최소화)처럼 쓰며(Graham 외 1979), 목적함수로 납기 지연, 평균 완료시간 등도 쓰입니다.
- 모든 작업의 기계 순서가 같은 흐름작업스케줄링과 달리 경로가 제각각이어서 구조가 더 복잡합니다. 일반 문제는 NP-난해로 알려져 있습니다(Garey, Johnson & Sethi 1976).
- 크기가 커지면 가능한 순서의 수가 폭발합니다. 기계마다 작업 순서를 정하는 경우의 수는 (n!)m이고(실행 불가능한 조합 포함), 6×6이면 약 1.4×1017, 10×10이면 약 4.0×1065입니다. 그래서 정확한 해법은 분기한정 같은 방법으로 작은 문제에 쓰고, 큰 문제는 디스패칭규칙이나 메타휴리스틱으로 근사합니다.
예시로 보기
작은 예 (가상의 예, 코드로 전수 탐색). 3개 작업, 3대 기계(M1~M3), 괄호는 처리시간입니다.
| 작업 | 기계 순서(처리시간) |
|---|---|
| J1 | M1(3) → M2(2) → M3(2) |
| J2 | M1(2) → M3(1) → M2(4) |
| J3 | M2(4) → M3(3) |
기계별 작업 순서의 조합은 2×6×6 = 72가지이고, 이 중 순환이 생기지 않아 실행 가능한 44가지의 메이크스팬은 11에서 21 사이입니다. 기계 M2의 총 처리시간이 10이므로 메이크스팬은 10 아래로 내려갈 수 없는데(하한), 최적해는 하한보다 1 큰 11입니다. 간단한 규칙(시작 가능 시각이 가장 이른 작업부터, 같으면 처리시간이 짧은 쪽 먼저)은 12, 같은 규칙에서 동률일 때 작업 번호가 빠른 쪽을 먼저 배정하면 14를 얻어, 같은 자료에서도 규칙에 따라 결과가 달라지는 것을 볼 수 있습니다. 이 규모는 전수 탐색이 가능하지만, Fisher와 Thompson(1963)이 제시한 10×10 사례(ft10)는 최적해가 1989년에야 증명되었습니다(Carlier & Pinson 1989).
자주 하는 오해
| 오해 | 바로잡기 |
|---|---|
| 작업장스케줄링과 흐름작업스케줄링은 크기만 다르다. | 경로가 작업마다 다르면 문제의 구조와 난이도가 달라집니다. |
| NP-난해이므로 항상 풀 수 없다. | 작은 사례는 정확히 풀 수 있고, 큰 사례는 근사해의 질로 평가합니다. 난해하다는 것은 최악의 경우 계산량이 급증한다는 뜻입니다. |
| 메이크스팬이 곧 문제의 목적이다. | 메이크스팬은 대표 목적함수일 뿐이며 납기·지연·재공품 재고 등도 쓰입니다. |
| 고전 모형이 현실 공정과 그대로 같다. | 기계 고장, 준비 시간, 신규 주문 도착 같은 요소를 더한 변형(동적·유연 작업장 등)이 연구됩니다. |
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
여러 작업의 순서를 최적화 알고리즘으로 결정해 전체 생산 완료 시간을 줄이는 방법을 다루었다는 뜻입니다.
새로운 작업이 계속 들어오는 현실적인 상황에서 여러 배정 규칙 중 어떤 것이 더 효율적인지 비교했다는 의미입니다.
조금 더 깊게 보면
작업장스케줄링은 조합이 매우 많아지는 특성 때문에 대표적인 NP-hard 문제로 알려져 있으며, 최적해를 정확히 구하기 어려운 대규모 문제에는 디스패칭규칙이나 메타휴리스틱 같은 근사적 방법이 자주 사용됩니다. 목적함수로는 메이크스팬 외에도 납기 지연, 평균 완료시간 등이 활용됩니다.
모든 작업이 동일한 기계 순서를 따르는 흐름생산 환경을 다루는 플로우샵스케줄링과 달리, 잡샵스케줄링은 작업마다 기계를 거치는 경로 자체가 다르다는 점에서 문제의 구조와 난이도가 다릅니다.
주의할 점
작업장스케줄링과 흐름작업스케줄링은 자주 혼동되지만, 흐름작업스케줄링은 모든 작업이 동일한 순서로 기계를 거친다는 점에서 다릅니다.
헷갈리기 쉬운 용어
스케줄링 문제는 작업의 기계 경로로 구분합니다.
| 용어 | 작업의 기계 경로 | 대표 환경 |
|---|---|---|
| 작업장(잡샵) 스케줄링 | 작업마다 다른 순서 | 다품종 소량, 주문형 생산 |
| 흐름작업(플로숍) 스케줄링 | 모든 작업이 같은 순서 | 소품종 대량 생산 |
| 메이크스팬 | 목적함수(모든 작업의 완료 시각) | 경로와 별개의 평가 기준 |
참고 문헌
- Fisher, H., & Thompson, G. L. (1963). Probabilistic learning combinations of local job-shop scheduling rules. In J. F. Muth & G. L. Thompson (Eds.), Industrial Scheduling. Prentice-Hall.
- Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129.
- Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.
- Carlier, J., & Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 35(2), 164–176.
- Pinedo, M. L. (2016). Scheduling: Theory, Algorithms, and Systems (5th ed.). Springer.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.