작업장스케줄링 (Job Shop Scheduling)
한 줄 정의: 여러 작업(job)이 각각 서로 다른 순서로 여러 기계를 거쳐야 하는 생산 환경에서, 각 작업을 각 기계에 언제 배정할지 결정하는 스케줄링 문제입니다.
쉽게 풀면
여러 손님이 각각 다른 순서로 병원의 여러 검사실을 돌아야 한다고 생각해보면 됩니다. 어떤 손님은 엑스레이부터 찍고 혈액검사를 받아야 하고, 다른 손님은 반대 순서로 진행해야 할 수도 있습니다. 작업장스케줄링은 이렇게 각 작업(손님)마다 거쳐야 할 기계(검사실)의 순서가 서로 다를 때, 전체적으로 가장 효율적으로 순서를 짜는 문제를 다룹니다. 순서가 제각각이라 흐름작업스케줄링보다 훨씬 복잡합니다.
왜 중요한가
다품종 소량 생산이나 주문형 제조 환경에서는 제품마다 필요한 공정 순서가 다르기 때문에 작업장스케줄링 문제가 빈번하게 발생합니다. 산업공학에서는 이 문제를 잘 풀수록 납기 준수율과 설비 가동률을 높이고 전체 생산시간(메이크스팬)을 줄일 수 있어 생산성 향상에 직결됩니다.
논문에서는 이렇게 쓰입니다
"본 논문은 작업장스케줄링 문제에서 메이크스팬을 최소화하기 위한 유전 알고리즘 기반 접근법을 제안하였다."
여러 작업의 순서를 최적화 알고리즘으로 결정해 전체 생산 완료 시간을 줄이는 방법을 다루었다는 뜻입니다.
"동적 작업장스케줄링 환경에서 디스패칭규칙의 성능을 비교 분석하였다."
새로운 작업이 계속 들어오는 현실적인 상황에서 여러 배정 규칙 중 어떤 것이 더 효율적인지 비교했다는 의미입니다.
조금 더 깊게 보면
작업장스케줄링은 조합이 매우 많아지는 특성 때문에 대표적인 NP-hard 문제로 알려져 있으며, 최적해를 정확히 구하기 어려운 대규모 문제에는 디스패칭규칙이나 메타휴리스틱 같은 근사적 방법이 자주 사용됩니다. 목적함수로는 메이크스팬 외에도 납기 지연, 평균 완료시간 등이 활용됩니다.
주의할 점
작업장스케줄링과 흐름작업스케줄링은 자주 혼동되지만, 흐름작업스케줄링은 모든 작업이 동일한 순서로 기계를 거친다는 점에서 다릅니다.