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