오픈숍스케줄링 (Open Shop Scheduling)
쉽게 풀면
여러 과목의 숙제를 순서에 상관없이 아무렇게나 끝내도 되는 상황을 떠올려보면 됩니다. 오픈숍스케줄링에서는 각 작업(job)이 여러 기계에서 처리를 받아야 하지만, 어느 기계를 먼저 거쳐야 한다는 정해진 순서가 없습니다. 예를 들어 A작업이 기계1과 기계2에서 처리되어야 한다면, 기계1을 먼저 거치든 기계2를 먼저 거치든 상관없습니다. 이 자유도 때문에 문제를 푸는 방법도 달라집니다.
왜 중요한가
실제 생산 현장 중에는 작업 순서가 엄격하게 정해지지 않은 경우도 존재하며, 이런 상황에서 최적의 작업 배치를 찾는 것은 순서가 고정된 문제와는 다른 접근이 필요합니다. 산업공학에서는 오픈숍스케줄링을 통해 순서 제약이 없는 상황에서의 최적 일정 수립 이론을 연구합니다.
논문에서는 이렇게 쓰입니다
오픈숍스케줄링이 이론적 최적화 알고리즘 연구의 대상이 됨을 보여줍니다.
오픈숍 모형이 제조업뿐 아니라 서비스 환경에도 적용될 수 있음을 나타냅니다.
조금 더 깊게 보면
오픈숍스케줄링은 작업 순서가 고정된 흐름작업(Flow Shop)이나 작업별로 순서가 다르게 정해진 잡숍(Job Shop)과 대비되는 개념입니다. 목적함수로는 총 완료시간(makespan) 최소화, 총 지연시간 최소화 등이 주로 사용되며, 기계 대수가 2대인 경우에는 다항시간 알고리즘이 알려져 있으나 기계 대수가 늘어나면 일반적으로 계산 복잡도가 크게 증가하는 것으로 알려져 있습니다.
주의할 점
오픈숍스케줄링은 순서 제약이 없다는 이론적 가정 때문에 실제 생산 현장에 그대로 적용하기 어려운 경우가 많으며, 실무에서는 부분적인 순서 제약을 추가한 변형 모형이 활용되기도 합니다.