혼합흐름공정 스케줄링 (Hybrid Flow Shop Scheduling)
한 줄 정의: 여러 단계의 공정마다 병렬로 운용되는 다수의 동일하거나 서로 다른 기계가 존재하는 흐름공정(flow shop) 환경에서 작업 순서와 기계 배정을 동시에 결정하는 스케줄링 문제입니다.
쉽게 풀면
일반적인 흐름공정(flow shop)은 모든 작업이 같은 순서로 각 단계를 거치되, 각 단계에는 기계가 하나씩만 있다고 가정합니다. 그러나 실제 공장에서는 특정 단계에 같은 역할을 하는 기계가 여러 대 있는 경우가 많습니다. 혼합흐름공정 스케줄링은 이렇게 각 단계마다 여러 대의 병렬 기계가 있는 상황에서, 어떤 작업을 어느 기계에 언제 배정할지를 함께 결정하는 문제입니다.
왜 중요한가
혼합흐름공정 스케줄링은 실제 다단계 병렬설비 생산현장의 특성을 더 현실적으로 반영하기 때문에, 이론적으로 구한 일정이 실무에 바로 적용될 가능성이 높아지고 총 완료시간이나 납기지연을 실질적으로 줄이는 데 기여합니다.
논문에서는 이렇게 쓰입니다
"본 논문은 혼합흐름공정 스케줄링(Hybrid Flow Shop Scheduling) 문제에 대해 총 완료시간을 최소화하는 발견적 알고리즘을 제안하였다."
여러 단계에 병렬 기계가 존재하는 생산환경에서 작업 순서를 정하는 새로운 해법을 다루었다는 의미입니다.
"제안된 유전알고리즘은 혼합흐름공정 스케줄링 벤치마크 문제에서 기존 규칙 기반 방법보다 평균 12% 낮은 makespan을 보였다."
제안한 방법이 기존 방법보다 전체 작업 완료시간을 더 짧게 만들었다는 뜻입니다.
조금 더 깊게 보면
혼합흐름공정 스케줄링은 NP-hard 문제로 알려져 있어 대규모 문제에서는 정확해를 구하기 어려운 경우가 많고, 유전알고리즘·타부서치·시뮬레이티드 어닐링 같은 메타휴리스틱이 흔히 사용됩니다. 병렬 기계 간 속도 차이나 설정시간(setup time)의 유무에 따라 문제의 난이도와 접근법이 달라집니다.
주의할 점
혼합흐름공정 스케줄링 모형은 흔히 작업 순서가 모든 작업에 동일하다고 가정하는데, 실제 현장에서 공정 순서가 작업마다 다르면 이 가정이 성립하지 않아 job shop 등 다른 모형을 검토해야 합니다.