병렬기계스케줄링 (Parallel Machine Scheduling)
한 줄 정의: 동일하거나 유사한 기능을 가진 여러 대의 기계에 작업들을 배정하여 전체 처리 성과(완료시간, 지연 등)를 최적화하는 스케줄링 문제입니다.
쉽게 풀면
은행 창구가 여러 개 열려 있을 때 손님들을 어느 창구로 안내할지 정하는 상황을 떠올려보면 됩니다. 병렬기계스케줄링은 이렇게 같은 역할을 하는 여러 대의 기계(또는 창구, 작업자)에 여러 작업을 어떻게 나눠 배정해야 전체적으로 가장 빨리 끝나거나 지연을 최소화할 수 있는지를 다루는 문제입니다.
왜 중요한가
동일한 설비가 여러 대 있는 생산라인이나 서버 클러스터, 콜센터 등 다양한 환경에서 작업 배정 효율이 곧 전체 성과로 직결됩니다. 산업공학에서는 병렬기계스케줄링을 통해 작업 배정 규칙과 알고리즘을 개발하여 생산성과 자원 활용도를 높이는 연구를 수행합니다.
논문에서는 이렇게 쓰입니다
"본 연구는 이종 병렬기계스케줄링 문제에서 총 가중 완료시간을 최소화하는 발견적 알고리즘을 제안하였다."
기계 성능이 서로 다른 상황에서의 최적 배정 문제를 다룬 사례입니다.
"반도체 웨이퍼 테스트 공정의 병렬기계스케줄링에 유전알고리즘을 적용하여 설비 가동률을 향상시켰다."
실제 제조 공정에 메타휴리스틱 기법이 적용된 사례를 보여줍니다.
조금 더 깊게 보면
병렬기계스케줄링은 기계 성능이 동일한 동일병렬기계(identical parallel machines)와 성능이 다른 이종병렬기계(unrelated/uniform parallel machines)로 구분됩니다. 목적함수로는 총 완료시간(makespan), 총 가중 완료시간, 총 지연시간 등이 흔히 사용되며, 문제 규모가 커지면 최적해를 구하기 어려워 발견적 기법이나 메타휴리스틱이 널리 활용됩니다.
주의할 점
병렬기계스케줄링은 기계 간 전환(setup) 시간이나 작업 우선순위 같은 현실적 제약을 단순화하는 경우가 많아, 실제 적용 시에는 이러한 제약을 추가로 반영해야 정확한 결과를 얻을 수 있습니다.