플로우 샵 스케줄링

플로우 샵 스케줄링(flow-shop scheduling)은 컴퓨터 과학 및 운영 연구의 최적화 문제이다. 이는 최적 작업 스케줄링의 한 변형이다. 일반적인 작업 스케줄링 문제에서, 우리는 다양한 처리 시간을 가진 n개의 작업 J1, J2, ..., Jn을 가지며, 이를 다양한 처리 능력을 가진 m개의 기계에 스케줄링해야 한다. 이때 목표는 메이크스팬을 최소화하는 것이다. 메이크스팬은 전체 스케줄의 총 길이(즉, 모든 작업이 처리를 마쳤을 때)를 의미한다. 플로우 샵 스케줄링으로 알려진 특정 변형에서는 각 작업이 정확히 m개의 작업을 포함한다. 작업의 i번째 작업은 i번째 기계에서 실행되어야 한다. 어떤 기계도 동시에 두 개 이상의 작업을 수행할 수 없다. 각 작업의 각 작업에 대해 실행 시간이 지정된다.

플로우 샵 스케줄링은 모든 작업에 대해 수행될 모든 작업의 엄격한 순서가 있는 잡 샵 스케줄링의 특수 사례이다. 플로우 샵 스케줄링은 제조업 시설뿐만 아니라 컴퓨팅 설계에도 적용될 수 있다. 플로우 샵 스케줄링 문제의 특별한 유형은 순열 플로우 샵 스케줄링 문제인데, 이는 리소스에서 작업의 처리 순서가 후속 처리 단계마다 동일한 경우이다.

최적 작업 스케줄링 문제에 대한 표준 3필드 표기법에서 플로우 샵 변형은 첫 번째 필드에 F로 표시된다. 예를 들어, "F3||"로 표시되는 문제는 단위 처리 시간을 가진 3기계 플로우 샵 문제이며, 목표는 최대 완료 시간을 최소화하는 것이다.

정의
m개의 기계와 n개의 작업이 있다. 각 작업은 정확히 m개의 작업을 포함한다. 작업의 i번째 작업은 i번째 기계에서 실행되어야 한다. 어떤 기계도 동시에 두 개 이상의 작업을 수행할 수 없다. 각 작업의 각 작업에 대해 실행 시간이 지정된다.

하나의 작업 내의 작업은 지정된 순서대로 수행되어야 한다. 첫 번째 작업은 첫 번째 기계에서 실행되고, (첫 번째 작업이 완료되면) 두 번째 작업은 두 번째 기계에서 실행되며, m번째 작업까지 계속된다. 그러나 작업은 어떤 순서로든 실행될 수 있다. 문제는 가능한 가장 짧은 총 작업 실행 메이크스팬을 가진 최적의 배열을 결정하는 것이다.

순서 지정 성능 측정 (γ)
순서 지정 문제는 하나 또는 여러 순서 지정 목표를 최적화하는 순서 S를 결정하는 것으로 명시될 수 있다.
 (평균) 플로우 시간, 
 메이크스팬, Cmax
 (평균) 지연, 
 ....
성능 측정에 대한 자세한 논의는 베남 말라쿠티(2013)에서 찾을 수 있다.Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. .

플로우 샵 스케줄링의 복잡성
게리(Garey) 외 (1976)가 제시했듯이, 플로우 샵 스케줄링 문제의 대부분 확장 버전은 NP-난해이며, 그 중 소수는 O(nlogn)으로 최적으로 해결할 수 있다. 예를 들어, F2|prmu|Cmax는 존슨의 규칙을 사용하여 최적으로 해결할 수 있다.

타이야르(Taillard)는 플로우 샵, 오픈 샵, 잡 샵 스케줄링을 위한 상당한 벤치마크 문제를 제공한다.

해결 방법
플로우 샵 스케줄링 문제를 해결하기 위해 제안된 방법은 분기 한정법과 같은 정확한 알고리즘과 유전 알고리즘과 같은 휴리스틱 알고리즘으로 분류될 수 있다.

 메이크스팬 Cmax 최소화 

F2|prmu|Cmax와 F3|prmu|Cmax는 존슨의 규칙을 사용하여 최적으로 해결할 수 있지만, 일반적인 경우에는 해의 최적성을 보장하는 알고리즘이 없다.

플로우 샵에는 시간 0에 동시에 사용 가능하며 그 사이에 무제한 저장 공간을 가진 직렬로 배열된 두 대의 기계에 의해 처리될 n개의 작업이 포함된다. 모든 작업의 처리 시간은 확실히 알려져 있다. 메이크스팬을 최소화하기 위해 기계에 n개의 작업을 스케줄링해야 한다. 두 기계 플로우 샵에서 작업을 스케줄링하기 위한 존슨의 규칙은 다음과 같다.

최적 스케줄에서, min{p1i,p2j} < min{p1j,p2i}인 경우 작업 i가 작업 j보다 먼저 온다. 여기서 p1i는 기계 1에서 작업 i의 처리 시간이고 p2i는 기계 2에서 작업 i의 처리 시간이다. 유사하게, p1j와 p2j는 각각 기계 1과 기계 2에서 작업 j의 처리 시간이다.

존슨의 알고리즘:
p1j를 기계 1에서 작업 j의 처리 시간으로 둔다.
p2j를 기계 2에서 작업 j의 처리 시간으로 둔다.

존슨의 알고리즘:
 p1j < p2j인 모든 작업을 포함하는 set1을 생성한다.
 p1j > p2j인 모든 작업을 포함하는 set2를 생성한다. p1j = p2j인 작업은 두 집합 중 어느 하나에 넣을 수 있다.
 다음과 같이 순서를 생성한다:
 (i) set1의 작업은 순서에서 먼저 오며, p1j의 오름차순(SPT)으로 온다.
 (ii) set2의 작업은 p2j의 내림차순(LPT)으로 뒤따른다. 동점은 임의로 처리한다.
이러한 유형의 스케줄을 SPT(1)–LPT(2) 스케줄이라고 한다.

사용 가능한 해결 방법에 대한 자세한 논의는 베남 말라쿠티 (2013)에서 제공된다.

 같이 보기 

 오픈 샵 스케줄링
 잡 샵 스케줄링

 각주 

분류:최적 스케줄링