단일기계 스케줄링 (Single Machine Scheduling)
한 줄 정의: 기계 한 대에서 여러 작업의 처리 순서를 정해 완료시간·납기 관련 목적함수를 최적화하는 스케줄링 문제군입니다.
쉽게 풀면
기계가 하나뿐인 작업장에서 여러 일을 어떤 순서로 처리할지 정하는 문제입니다. 목표가 '평균 완료시간 줄이기'인지 '납기 늦는 일 줄이기'인지에 따라 좋은 순서가 달라집니다. 가장 단순한 스케줄링이지만 이론의 출발점입니다.
왜 중요한가
여러 기계 문제의 하위 문제나 병목 공정 분석으로 자주 쓰이고, 어떤 목적함수가 쉽게 풀리고 어떤 것이 NP-hard인지의 경계가 잘 정리되어 있어 새 알고리즘의 시험대가 됩니다. 논문에서는 α|β|γ 표기로 문제를 짧게 밝힙니다.
논문에서는 이렇게 쓰입니다
"본 연구는 순서의존 셋업시간이 있는 1|s_ij|ΣwjTj 문제에 대해 분지한정 알고리즘을 제안한다."
1|β|γ 표기로 제약과 목적함수를 밝힌 예문입니다.
조금 더 깊게 보면
그레이엄 등의 3필드 표기에서 α 자리에 1을 쓰면 단일기계 문제를 뜻합니다. 총완료시간(ΣCj)은 처리시간이 짧은 순(SPT)으로, 최대지연(Lmax)은 납기가 빠른 순(EDD)으로 최적해를 얻습니다. 지연작업 수(ΣUj)는 Moore–Hodgson 알고리즘으로 풀립니다. 반면 가중 총지연(ΣwjTj)이나 작업 도착시간이 서로 다른 경우 상당수가 NP-hard여서 분지한정법이나 메타휴리스틱을 씁니다.
주의할 점
순서결정문제는 순서를 정하는 문제 일반을, SPT·EDD는 개별 규칙을 뜻하는 반면, 단일기계 스케줄링은 목적함수별 최적 규칙과 난이도 경계를 묶어 다루는 특정 문제군입니다. 같은 규칙도 목적함수가 바뀌면 최적성이 사라진다는 점에 주의하세요.