서론 - 스케줄링의 역할과 기능 | Scheduling 001

스케줄링의 역할

스케줄링 (Scheduling) 은 주어진 시간 동안 특정 작업 (task) 에 가용한 자원 (resource) 과 처리 순서를 할당하는 의사 결정 과정 또는 알고리즘이다. 스케줄링의 목적 (goal) 은 보통 하나 또는 그 이상의 목표 (objectives) 를 최적화하는 것이다. 

 

여기에서 특정 작업과 가용한 자원은 생산 공정의 작업과 기계, 공항의 이착륙과 활주로, 또는 컴퓨터 프로그램의 실행과 처리 장치 등이 될 수 있다. 목표의 예로는 마지막 작업 완료 시간의 최소화 또는 마감 시간을 지나서 완료된 작업의 수 최소화 등이 될 수 있다. 

 

예제 1-1 종이 봉투 생산 공장 

시멘트, 숯, 개 사료 등의 종이 봉투를 생산하는 공장을 생각해보자. 이러한 작업의 기본 원자재는 종이 롤이다. 생산 공정은 로고 인쇄, 가방 측면 접착, 가방의 한쪽 끝 또는 양쪽 끝을 재봉하는 3단계로 구성된다. 각 기계는 작동 속도, 인쇄할 수 있는 색상 수 또는 생산할 수 있는 가방의 크기가 조금씩 다를 수 있다. 각 생산 주문에는 약속된 배송 날짜 또는 기한까지 생산 및 배송해야 하는 특정 가방의 수량이 표시되어 있다. 각 단계의 처리 시간은 주문의 크기, 즉 주문한 가방의 수에 비례한다. 

 

한 종류의 가방에서 다른 종류의 가방으로 생산 품목을 전환할 때는 기계 설정이 필요하며, 이러한 기계 설정 시간은 두 연속 주문 간의 유사성 (예: 공통 색상 수, 봉투 크기 차이 등) 에 따라 달라진다. 스케줄링의 중요한 목표는 기계 설정에 소요되는 총 시간을 최소화하는 것이다. 또한 배송이 늦어지면 영업 손실의 형태로 위약금이 부과되므로, 스케줄링의 다른 목표는 이러한 위약금의 합을 최소화하는 것이다. 

 

예제 1-2 반도체 제조 시설 

메모리 칩과 마이크로프로세서와 같은 반도체의 생산 공정은 일반적으로 웨이퍼 (wafer) 제작, 웨이퍼 프로브, 조립 또는 패키징, 최종 테스트의 네 단계로 구성된다. 웨이퍼 제작은 기술적으로 가장 복잡한 단계로 웨이퍼 위에 금속과 웨이퍼 재료의 층을 패턴으로 쌓아 회로를 제작한다. 각 레이어에는 (i) 세척, (ii) 산화, 증착 및 금속화, (iii) 리소그래피, (iv) 에칭, (v) 이온 주입, (vi) 포토레지스트 박리, (vii) 검사 및 측정과 같은 여러 작업이 반복적으로 필요하다. 웨이퍼는 로트 (lot) 단위로 생산되며, 일부 장비는 작업을 위해 사전 설정이 필요할 수 있다. 사전 설정 시간은 방금 완료된 웨이퍼 로트와 앞으로 시작될 웨이퍼 로트의 구성에 따라 달라진다.

 

 

반도체 생산 공정의 주문에는 고유한 출시일과 배송 또는 마감일이 정해져 있다. 스케줄링의 목표는 처리량을 최대화하면서 약속된 배송 날짜를 최대한 많이 맞추는 것이다. 후자의 목표는 특히 병목 현상이 발생하는 장비의 가동률을 극대화함으로써 달성할 수 있으므로 유휴 시간과 설정 시간을 최소화해야 한다.

 

예제 1-3 공항에서의 게이트 배정  

주요 공항의 각 게이트에서는 매일 수백 대의 비행기가 도착하고 출발한다. 게이트와 비행기는 모두 동일하지 않다. 이 예제에서 공항의 게이트는 자원이고 비행기의 취급 및 서비스는 작업이다. 게이트에 비행기가 도착하는 것은 작업의 시작 시간을, 출발은 작업의 완료 시간을 의미한다. 

 

 

비행기는 정해진 스케줄에 따라 게이트에 도착 및 출발하는 것을 목표로 하지만, 예기치 않은 상황으로 인해 일정이 어느 정도 변경될 수 있다. 비행기가 게이트를 점유하는 시간 동안 도착 승객이 내리고, 비행기를 정비하고, 출발 승객을 탑승시킨다. 스케줄링은 여러 가지 목표를 최적화하면서 각 도착 시간에 이용 가능한 적절한 게이트에 비행기를 배정해야 한다. 이러한 목표 중에는 항공사 직원의 업무 시간 최소화 및 비행기 출발 지연 시간 최소화 등이 포함된다. 

 

예제 1-4 CPU 에서 작업 예약하기 

컴퓨터 운영 체제의 기능 중 하나는 CPU 가 실행해야 하는 여러 프로그램에 할당하는 시간을 예약하는 것이다. 각 프로그램의 정확한 처리 시간은 일반적으로 미리 알 수 없지만, 이러한 무작위 처리 시간의 분포는 그 평균과 편차를 포함하여 미리 알 수 있다. 각 프로그램의 작업은 일반적으로 특정 우선 순위 수준이 있다. 이러한 경우 스케줄링의 목표는 모든 작업의 가중치가 적용된 완료 시간의 예상 합계를 최소화하는 것이다.

 

상대적으로 짧은 처리 시간을 가진 작업이 더 높은 우선순위를 가진 훨씬 더 긴 처리 시간을 가진 작업이 완료되기를 기다리며 시스템에 오랫동안 남아 있는 상황을 피하기 위해, 운영 체제는 각 작업을 작은 조각으로 '슬라이스' 한다. 이후, 운영 체제는 CPU에서 이러한 슬라이스를 회전시켜 주어진 시간 간격에 따라 CPU가 각 작업에 일정 시간을 소비하도록 한다. 이러한 경우, 처리 시간이 매우 짧은 작업은 상대적으로 빠르게 시스템을 떠날 수 있다. 

 

 

 

스케줄링의 기능 

현대의 공장이나 서비스 조직은 중앙 컴퓨터와 데이터베이스를 포함하는 정교한 정보 시스템을 갖추고 있는 경우가 많다. 이러한 정교한 정보 시스템을 제어하는 소프트웨어를 일반적으로 전사적 자원 관리 (ERP) 시스템이라고 한다. 이러한 ERP 시스템은 모든 조직 수준에서 의사 결정 지원 시스템과 연결하여 기업을 가로지르는 정보 고속도로 역할을 한다. 

스케줄링은 대개 ERP 시스템에 연결된 개인용 컴퓨터나 워크스테이션에 설치된 의사 결정 지원 시스템을 통해 이루어진다. ERP 시스템에 연결된 주요 위치의 단말기를 통해 기업 내 모든 부서에서 모든 최신 일정 정보에 접근할 수 있다. 이러한 부서는 다시 스케줄링 시스템에 작업 및 기계의 상태에 관한 최신 정보를 제공할 수 있다. 물론 스케줄링 기능과 다른 의사 결정 주체 간의 커뮤니케이션이 회의나 메모를 통해 이루어지는 환경도 여전히 존재한다. 

 

 

제조 환경에서의 스케줄링 

일반적인 제조 환경에서 출고되는 주문은 마감 시간이 연결된 작업으로 변환되어야 한다. 이러한 작업은 기계에서 주어진 순서에 따라 처리되어야 한다. 특정 기계가 사용 중일 경우 작업 처리가 지연될 수 있으며, 우선 순위가 높은 작업이 사용 중인 기계에 도착하면 선점 현상이 발생할 수 있다. 기계 고장이나 예상보다 긴 처리 시간 등 작업 현장에서 예기치 못한 이벤트도 일정에 큰 영향을 미칠 수 있다. 

스케줄링 프로세스에 영향을 미치는 부분은 작업 현장만이 아니라 전체 조직의 중장기 계획을 처리하는 생산 계획 프로세스의 영향도 받는다. 생산 계획 프로세스는 재고 수준, 수요 예측 및 자원 요구 사항을 기반으로 회사의 전체 제품 믹스와 장기 자원 할당을 최적화하려 시도한다. 여기에서 내려진 결정은 스케줄링 과정에 직접적인 영향을 미칠 수 있다. 아래 Fig 1.1 은 제조 시스템의 정보 흐름 다이어그램을 보여준다.

 

제조 환경에서는 스케줄링 기능이 다른 의사 결정 기능과 상호 작용해야 하는데, 그 중 하나는 자재 소요량 계획 (MRP) 시스템이다. 각 작업에는 생산에 필요한 부품을 항목별로 정리한 자재 명세서 (BOM) 가 있다. MRP 시스템은 각 부품의 재고를 추적하며, 각 자재의 구매 시기를 결정한다. 이 과정에서 스케줄링 시스템에서 사용되는 것과 유사한 로트 크기 조정 및 로트 스케줄링과 같은 기술을 사용한다. 시설에 스케줄링 시스템이 없는 경우에도 생산 계획 목적으로 MRP 시스템을 사용할 수 있다. 

 

서비스에서의 스케줄링 

서비스에서의 스케줄링 기능은 제조 환경에서의 스케줄링 기능과 마찬가지로 정교한 정보 시스템 내에서 다른 의사 결정 기능과 조율되어야 한다. 이러한 정보 시스템은 일반적으로 자원 가용성 및 (잠재적) 고객과 관련된 모든 관련 정보를 포함하는 광범위한 데이터베이스에 의존한다. 스케줄링 시스템은 예측 및 수율 관리 모듈과 자주 상호 작용한다. 아래 Fig 1.2 는 서비스 조직의 정보 흐름을 보여준다. 제조 환경과 다르게 서비스 환경에는 일반적으로 MRP 시스템이 없다. 

 

 

참고문헌 

M. Pinedo (2016), Scheduling: Theory, Algorithms, and Systems - Fifth Edition

 

Scheduling 의 다음 글 읽기 

결정론적 모델의 표기법과 분류 방법 | Scheduling 002

결정론적 모델의 표기법과 분류 방법 | Scheduling 002