스케줄링 3필드 표기법 (Three-Field Notation for Scheduling)
한 줄 정의: 기계환경 α, 작업특성 β, 목적함수 γ를 α|β|γ 형식으로 적어 스케줄링 문제를 분류하는 표기법입니다.
쉽게 풀면
스케줄링 문제는 기계가 몇 대인지, 작업에 어떤 제약이 있는지, 무엇을 최소화하는지에 따라 종류가 매우 많습니다. 3필드 표기법은 이것을 '1|rⱼ|ΣCⱼ'처럼 세 칸으로 줄여 씁니다. 첫 칸은 기계 환경, 둘째 칸은 작업 조건, 셋째 칸은 최적화 목표입니다.
왜 중요한가
스케줄링 논문은 연구하는 문제를 이 표기로 먼저 밝히는 것이 관례이고, 문제의 계산 복잡도를 정리한 표들도 이 표기로 작성됩니다. 이 표기를 읽을 줄 알아야 선행연구가 같은 문제를 다뤘는지 빠르게 판단할 수 있습니다.
논문에서는 이렇게 쓰입니다
"본 연구는 순서의존 셋업시간을 갖는 병렬기계 총납기지연 최소화 문제 Pm|sᵢⱼ|ΣTⱼ를 다룬다."
동일한 병렬기계, 순서의존 셋업시간 조건, 총 납기지연 최소화 목적의 문제라는 뜻입니다.
조금 더 깊게 보면
그레이엄(R. L. Graham), 롤러(E. L. Lawler), 렌스트라(J. K. Lenstra), 리누이 칸(A. H. G. Rinnooy Kan)이 1979년 논문에서 체계화했습니다. α에는 1(단일기계), Pm·Qm·Rm(병렬기계 종류), Fm(흐름작업), Jm(작업장), Om(오픈숍) 등이, β에는 rⱼ(도착시간), prec(선행관계), prmp(선점 허용) 등이, γ에는 Cmax(메이크스팬), ΣwⱼCⱼ, Lmax, ΣTⱼ 등이 들어갑니다. β칸이 비어 있으면 특별한 제약이 없다는 뜻입니다.
주의할 점
켄달 표기법이 대기행렬 모형을 분류한다면, 3필드 표기법은 스케줄링 문제를 분류한다는 점이 다릅니다. 세부 기호는 교재·논문마다 약간씩 다르게 쓰이므로 본문의 정의를 확인해야 합니다.