이동병목절차 (Shifting Bottleneck Procedure)
쉽게 풀면
여러 대의 기계를 제각기 다른 순서로 거쳐야 하는 주문들이 뒤엉킨 공장에서, 모든 기계의 작업 순서를 한꺼번에 최적으로 정하는 일은 사실상 불가능에 가깝습니다. 이동병목절차는 이 문제를 기계 한 대씩 푸는 방식으로 잘게 나눕니다. 일정이 꼬인 여러 회의실 가운데 예약 경쟁이 가장 치열한 방부터 시간표를 확정하고 그 결과를 나머지 방의 제약조건으로 넘기는 것과 비슷합니다. 아직 순서가 정해지지 않은 기계들 중 지연을 가장 크게 유발하는 기계를 병목으로 지목해 순서를 고정하고, 고정할 때마다 이미 확정된 기계들의 순서를 다시 손봅니다. 모든 기계가 확정될 때까지 이 과정을 반복합니다.
왜 중요한가
잡숍 스케줄링은 대표적인 계산난해 문제여서 기계와 작업 수가 조금만 늘어도 최적해를 구하기 어렵습니다. 이동병목절차는 이론과 알고리즘이 잘 정리된 단일기계 부분문제를 반복적으로 활용해 실용적인 시간 안에 품질 좋은 해를 만들어 냅니다. 이 때문에 후속 메타휴리스틱 연구에서 초기해 생성기나 성능 비교의 기준선으로 널리 쓰입니다.
논문에서는 이렇게 쓰입니다
구조적 휴리스틱으로 좋은 출발점을 만든 뒤 타부탐색으로 개선하는 이단계 설계를 뜻합니다. 무작위 초기해보다 수렴이 빠른 경우가 많습니다.
투입가능시각과 납기가 주어진 단일기계 문제를 기계별로 풀고, 지연이 가장 심하게 나온 기계를 그 반복의 병목으로 지목했다는 뜻입니다.
새 기계를 확정한 뒤 기존 확정 기계들의 순서를 다시 푸는 재최적화가 해의 품질에 크게 기여함을 실험으로 확인했다는 의미입니다.
조금 더 깊게 보면
이 절차는 잡숍 문제를 분리그래프로 표현한 뒤, 아직 방향이 정해지지 않은 기계 하나를 골라 그 기계의 작업 순서를 정하는 일을 반복하는 것으로 볼 수 있습니다. 각 기계의 부분문제는 이미 확정된 부분에서 유도한 투입가능시각과 납기를 갖는 단일기계 최대지연 최소화 문제이며, 이를 정확히 푸는 전용 분지한정 알고리즘이 알려져 있습니다. 부분 탐색트리를 유지하며 여러 병목 후보를 함께 전개하는 확장형도 제안되었고, 총가중지연 같은 다른 목적함수로 옮기려면 부분문제 자체를 바꿔야 합니다.
주의할 점
여기서 말하는 병목은 설비 용량이 만성적으로 부족한 물리적 병목이 아니라, 현재 부분해에서 지연을 가장 크게 유발하는 기계를 뜻하며 반복마다 바뀝니다. 이름에 이동이 붙은 이유도 그 때문입니다. 또한 휴리스틱이므로 최적해를 보장하지 않습니다.