증명이 딸린 디스패칭 룰 셋: SPT, WSPT, EDD 그리고 증명이 끝나는 곳
최단 처리시간, 가중 최단 처리시간, 최단 납기는 각각 한 설비에서 한 가지 목적에 대해 최적임이 증명된 룰입니다. 작업 5개 예제를 가능한 120가지 순서 전부와 대조해 각 룰이 무엇을 얻고 무엇을 내주는지 보이고, 설비가 둘이 되는 순간 정렬 룰이 왜 정리가 아니게 되는지 설명합니다.
이 페이지 목차
디스패칭 룰은 한 가지 질문에 답합니다. 설비가 방금 비었고 기다리는 작업이 여럿일 때, 어느 것을 먼저 할 것인가. 스케줄링 라이브러리는 룰을 열 개 넘게 싣고 있고, 대부분은 어떤 공장에서 우연히 잘 맞은 경험칙입니다. 그중 셋은 다릅니다. 각각 좁은 조건에서 "어떤 순서도 이 지표에서 이보다 나을 수 없다"는 정리가 딸려 있습니다.
이 글은 그 세 정리를 적고, 작업 5개 예제에서 각 룰이 무엇을 얻고 무엇을 내주는지 보이고, 정리가 더는 적용되지 않는 지점, 곧 대부분의 실제 공장이 시작되는 지점을 짚습니다.
정리가 전제하는 상황
세 결과 모두 설비 한 대, 모든 작업이 시각 0에 준비되어 있고, 처리시간을 알고, 작업 사이에 준비 교체가 없는 경우의 이야기입니다. 작업 j에 대해:
- pⱼ는 처리시간, dⱼ는 납기입니다.
- Cⱼ는 완료 시각입니다. 앞선 작업들의 처리시간 합에 자기 처리시간을 더한 값입니다.
- Lⱼ = Cⱼ − dⱼ는 납기 편차(lateness)입니다. 일찍 끝나면 음수입니다.
- Tⱼ = max(0, Lⱼ)는 지연(tardiness)입니다.
- wⱼ는 가중치로, 이 작업의 대기 한 시간이 다른 작업에 비해 얼마나 비싼지를 나타냅니다.
세 룰과 각각이 최적인 지표
| 룰 | 정렬 기준 | 최소화하는 것 |
|---|---|---|
| SPT, 최단 처리시간 | pⱼ 오름차순 | 평균 완료시간(곧 평균 흐름시간) |
| WSPT, 가중 최단 처리시간 | pⱼ / wⱼ 오름차순 | 가중 합 Σ wⱼCⱼ |
| EDD, 최단 납기 | dⱼ 오름차순 | 최대 납기 편차 max Lⱼ |
SPT는 가중치가 모두 같은 WSPT입니다. 가중 비율 룰은 W. E. Smith가 1956년에, 납기 순서 결과는 J. R. Jackson이 1955년 연구 보고서에서 증명했습니다.
증명은 짧은 교환 논증입니다. 룰 기준으로 서로 거꾸로 놓인 이웃 두 작업 i, j가 시각 t에서 시작한다고 합시다. SPT에서 i를 먼저 하면 완료 시각은 t + pᵢ, t + pᵢ + pⱼ이고 합은 2t + 2pᵢ + pⱼ입니다. j를 먼저 하면 2t + 2pⱼ + pᵢ입니다. 앞의 것이 pᵢ − pⱼ만큼 큽니다. 그러니 긴 작업이 앞에 있으면 짧은 작업 뒤로 바꿀 때마다 합이 줄고, 일정의 나머지는 달라지지 않습니다. 거꾸로 놓인 이웃이 없어질 때까지 반복하면 룰이 나옵니다. WSPT와 EDD도 각자의 기준으로 같은 방식입니다.
작업 5개 예제
설비 한 대, 작업 다섯 개가 동시에 준비되어 있습니다. 단위는 시간입니다.
| 작업 | p (처리시간) | d (납기) | w (가중치) |
|---|---|---|---|
| A | 6 | 9 | 1 |
| B | 2 | 3 | 1 |
| C | 4 | 6 | 3 |
| D | 3 | 14 | 1 |
| E | 5 | 8 | 2 |
도착 순서(A B C D E)로 돌린 경우와 각 룰로 돌린 경우입니다.
| 룰 | 순서 | 평균 C | 최대 L | Σ T | Σ wC | 지연 작업 수 |
|---|---|---|---|---|---|---|
| 도착 순서 | A B C D E | 12.2 | 12 | 24 | 105 | 4 |
| SPT | B D C E A | 10.0 | 11 | 20 | 82 | 3 |
| EDD | B C E A D | 11.2 | 8 | 17 | 79 | 3 |
| WSPT | C B E D A | 11.0 | 11 | 17 | 74 | 3 |
가능한 120가지 순서를 전부 돌려 보기도 했습니다. 평균 완료시간 10.0에 닿는 순서는 정확히 하나이고 SPT 순서입니다. Σ wC = 74에 닿는 순서도 정확히 하나이고 WSPT 순서입니다. 최대 납기 편차의 최솟값은 8이고 여섯 가지 순서가 닿으며 EDD 순서가 그중 하나입니다. 정리가 말하는 대로 각 룰이 자기 열에서 이깁니다.
하지만 다른 열도 읽어야 합니다. SPT는 평균이 가장 좋지만 가장 긴 작업 A가 맨 끝으로 밀려 납기보다 11시간 늦고, 그래서 최대 납기 편차가 11입니다. EDD는 최악의 경우를 8시간으로 막는 대신 평균에서 1.2시간을 냅니다. WSPT는 무거운 작업 C를 먼저 하여 가중 합에서 이기지만 A는 여전히 11시간 늦습니다. 세 정리 모두 Σ T나 지연 작업 수에 대해서는 아무 말도 하지 않습니다. 그 두 열은 결과가 아니라 참고 정보이고, 이 숫자에서는 우연히 EDD와 WSPT에 유리하게 나왔을 뿐입니다.
그러니 룰을 고른다는 것은 무엇을 지킬지 고르는 일입니다. 평균 대기, 가장 나쁜 약속, 비용으로 가중한 대기 중에서요.
증명이 끝나는 곳
정리가 전제한 상황에서 벗어나는 순간 룰은 휴리스틱이 됩니다.
- 설비가 둘 이상이거나, 작업이 정해진 순서로 여러 설비를 거치는 경우(잡숍). 룰은 설비마다 따로 다음 작업을 고르고, 한 설비에서 국소적으로 최적인 선택이 다음 설비를 굶길 수 있습니다.
- 작업이 시간에 따라 도착하는 경우. 가장 좋은 다음 작업이 아직 도착하지 않았을 수 있습니다.
- 직전 작업에 따라 달라지는 준비 교체 시간. 위 논증이 모두 기대는 "처리시간의 합"이 깨집니다.
휴리스틱도 얼마든지 좋을 수 있습니다. Vepsalainen과 Morton(1987)은 정리가 닿지 않는 가중 지연 잡숍을 위해 ATC(명백 지연비용) 룰을 설계했고, 최적임을 증명하는 대신 모의 잡숍 실험으로 시험했습니다. 교환 논증과는 다른 종류의 근거이고, 어떤 룰이 어느 쪽 위에 서 있는지 아는 것이 중요합니다.
Forge Plan에서 해 보기
Forge Plan의 일정 화면에는 디스패칭 룰 14개가 있습니다. 고른 룰 아래에 출처가 표시됩니다. SPT와 WSPT는 Smith(1956), EDD는 Jackson(1955), ATC는 Vepsalainen과 Morton(1987)입니다. 나머지 룰은 인용할 출처가 없어서, 지어내는 대신 출처 미확보 — 검증 권장 배지가 표시됩니다.
내 데이터에서 룰을 비교하려면 같은 주문을 룰만 바꿔 돌리고 결과를 시나리오로 저장합니다. 비교 화면은 저장한 시나리오를 지표별로 나란히 보여 주고(총 소요시간, 총 지연, 최대 지연, 지연 주문 수 등) 각 행에서 가장 좋은 값에 최량 표시를 합니다.
솔직한 한계가 둘 있습니다. 위 정리는 설비 한 대에 대한 말이고 Forge Plan은 공장 전체를 계획하므로, 룰의 인용은 결과에 대한 보증이 아니라 그 룰이 합리적인 기본값인 이유로 읽어야 합니다. 또 비교 화면은 총 소요시간과 지연 계열 지표를 보여 줄 뿐 평균 흐름시간은 없으므로, 위 표의 평균 완료시간 열은 손이나 스프레드시트로 확인할 몫입니다.
참고문헌
- W. E. Smith, "Various optimizers for single-stage production", Naval Research Logistics Quarterly, 3(1–2), 1956, pp. 59–66, doi:10.1002/nav.3800030106.
- J. R. Jackson, "Scheduling a production line to minimize maximum tardiness", Research Report 43, Management Sciences Research Project, University of California, Los Angeles, 1955년 1월. 결과는 위 표에서처럼 최대 납기 편차(lateness)에 관한 것입니다.
- A. P. J. Vepsalainen and T. E. Morton, "Priority rules for job shops with weighted tardiness costs", Management Science, 33(8), 1987, pp. 1035–1047, doi:10.1287/mnsc.33.8.1035.
- M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, 5th ed., Springer, 2016, doi:10.1007/978-3-319-26580-3. 위 표기와 단일 설비 결과의 일반 참고서.