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