병렬 머신 스케줄링

병렬 기계 스케줄링이란?

병렬 기계 일정계획은 총소요시간(makespan, 전체 완료 시간) 최소화나 총 지연 최소화 같은 목표를 달성하도록 여러 대의 동일한 기계에 작업 집합을 배정하는 문제입니다. 단일 기계 일정계획을 제조, 컴퓨팅, 물류에서 흔히 볼 수 있는 다중 기계 환경으로 확장한 것입니다.

LPT(최장 작업시간 우선) 규칙은 병렬 기계에서 총소요시간을 최소화하는 데 널리 쓰이는 휴리스틱입니다. 작업을 처리 시간이 긴 순서로 정렬한 뒤, 각 작업을 가장 먼저 비는 기계에 배정합니다. LPT는 동일한 기계에서 최적해의 4/3 이내인 총소요시간을 보장합니다. SPT, EDD, WSPT 등 다른 규칙은 서로 다른 목표를 최적화합니다.

기계 가동률, 즉 각 기계가 전체 시간 중 작업을 수행하는 시간의 비율은 부하 균형의 품질을 드러냅니다. 기계 간 가동률이 고르면 균형이 좋다는 뜻입니다. 간트 차트는 기계별 일정 타임라인을 보여 주어 유휴 시간과 부하 불균형을 즉시 확인할 수 있게 합니다.

Formula: Makespan = max(Completion Time of all machines) Utilization = Σ Processing Time / (Makespan x m) Tardiness = max(0, Completion - Due Date) LPT: Assign longest job to earliest available machine SPT: Assign shortest job to earliest available machine

계산 예시

기계 2대에 작업 4개(p=8,6,5,3)를 LPT로 배정합니다. 작업1(8)→M1, 작업2(6)→M2, 작업3(5)→M2(부하 6→11), 작업4(3)→M1(부하 8→11)로 배정하면 총소요시간은 11입니다. 가동률은 M1=11/11=100%, M2=11/11=100%로 완벽하게 균형을 이룹니다. LPT를 쓰지 않고 FCFS로 처리하면 총소요시간이 14가 되고 균형도 나빠질 수 있습니다.

이 계산기를 사용하는 경우

• 여러 동일 기계에 걸쳐 작업 배치를 스케줄링하고 메이크스팬 또는 총 지연을 최소화해야 할 때
• 기계 추가가 현재 작업량의 메이크스팬을 의미 있게 줄이는지 평가하는 생산능력 계획 시
• 특정 작업 조합에 대한 디스패칭 규칙을 비교할 때 — 서로 다른 규칙이 서로 다른 목표를 최적화하며 최선의 선택은 우선순위에 따라 다름
• 기계 고장 후 남은 작업을 가용 기계에 빠르게 재스케줄링하고 납기 영향을 평가할 때
• 모든 기계가 생산 일정에 동등하게 기여하도록 기계 간 부하를 균형 잡아 유휴 시간을 최소화할 때

흔한 실수

• 메이크스팬 최소화에 SPT 사용 — SPT는 평균 흐름 시간을 최소화하지 메이크스팬이 아님; 병렬 기계에서 메이크스팬에는 가장 긴 작업을 먼저 할당하는 LPT 사용
• 더 많은 기계가 항상 메이크스팬을 비례적으로 줄인다고 가정 — 개선은 수확 체감 법칙을 따름; 작업 크기가 매우 불균등하면 기계 추가가 메이크스팬을 거의 줄이지 않을 수 있음
• 작업이 다른 시간에 도착할 때 투입 시간을 고려하지 않음 — 정적 디스패칭 규칙은 모든 작업이 시간 0에 가용하다고 가정; 도착 시간이 다르면 동적 디스패칭 사용
• 기계 가동률 균형 무시 — 최소 메이크스팬 스케줄이 일부 기계를 장기간 유휴 상태로 만들 수 있음; 공정성과 마모 균형을 위해 모든 기계의 가동률 확인

결과 해석 방법

• 모든 기계의 가동률이 동등(각각 >90%) — 부하가 잘 균형 잡힘; 디스패칭 규칙이 효율적으로 수행
• 한 기계가 100% 가동이고 나머지는 상당히 낮음 — 해당 기계가 병목; 가장 긴 작업이 메이크스팬을 결정할 가능성
• 총 지연 = 0 — 모든 작업이 납기 전에 완료; 스케줄이 모든 납기 약속을 충족
• 많은 지연 작업과 높은 총 지연 — 작업량이 납기 기간 내 생산능력을 초과; 잔업, 추가 기계, 연장된 납기 협상 고려
• LPT와 SPT가 매우 유사한 메이크스팬 — 작업 처리 시간이 상대적으로 균일; 작업이 크기에서 유사할 때 규칙 선택이 덜 중요

관련 표준 및 참고문헌

• APICS CPIM Body of Knowledge — 생산 활동 관리 모듈 내 병렬 기계 스케줄링 개념 포함
• ISA-95 (IEC 62264) — 상세 기계 수준 스케줄링을 포함한 스케줄링 수준을 정의하는 기업-제어 시스템 통합 표준

자주 묻는 질문

병렬 기계에서 총소요시간을 최소화하는 배정 규칙은 무엇인가요?

총소요시간 최소화에는 LPT(최장 작업시간 우선)가 가장 좋은 휴리스틱입니다. 처리 시간이 긴 작업을 먼저 배정하기 때문에 큰 작업이 마지막에 병목을 만드는 일을 막습니다. LPT는 기계 수를 m이라 할 때 최적해의 4/3 - 1/(3m) 이내인 해를 보장합니다. 기계가 2대이면 최적해의 7/6(약 17%) 이내입니다.

투입 가능 시점이나 납기가 서로 다른 작업은 어떻게 처리하나요?

투입 가능 시점이 있으면 작업은 그 시점 이후에만 시작할 수 있으므로, 기계가 빌 때마다 우선순위를 다시 평가하는 동적 배정 방식을 사용합니다. 납기가 있으면 EDD나 CR 규칙이 지연 최소화에 도움이 됩니다. 두 제약이 함께 있는 복잡한 문제에서는 여러 규칙을 시뮬레이션하여 성과 지표를 비교합니다. 최적의 규칙은 구체적인 작업 구성과 목표에 따라 달라집니다.