플로우샵 스케줄링

플로우샵 스케줄링은 컴퓨터 과학 및 운영 연구에 있어 최적화 문제입니다.이것은 최적의 작업 스케줄링의 변형입니다.일반적인 작업 스케줄링 문제에서는 작업 시간 J, J₂, ..., J를 n개 부여합니다.이 작업들은₁ 일정의 총 길이(모든_n 작업이 처리가 완료된 시점)를 최소화하면서 다양한 처리 능력을 가진 m개의 기계로 스케줄링되어야 합니다.플로우 숍 스케줄링이라고 불리는 특정 바리안트에서는 각 작업에는 정확히 m개의 연산이 포함됩니다.작업의 i번째 작업은 i번째 기계에서 실행해야 합니다.어떤 기계도 동시에 여러 작업을 수행할 수 없습니다.각 작업의 각 조작에 대해 실행 시간이 지정된다.

플로우 숍 스케줄링은 모든 작업에 대해 모든 작업을 엄격하게 수행할 수 있는 작업 숍 스케줄링의 특별한 경우입니다.플로우샵 스케줄링은 컴퓨팅 설계뿐만 아니라 생산 설비에도 적용될 수 있습니다.플로우 숍 스케줄링의 특수한 타입의 문제는 자원상의 작업의 처리 순서가 후속 처리 단계별로 동일한 치환 플로우 숍 스케줄링 문제입니다.

최적 작업 스케줄링 문제에 대한 표준 3필드 표기법에서 플로우샵 바리안트는 첫 번째 필드에서 F로 표시됩니다.예를 들어 " $p_{ij}$ p $p_{ij}$ $\$ style $p_{ij}$ $C_{\max }$ max $\$ 로 나타나는 문제는 유닛 처리 시간의 3 머신 플로우샵 문제이며 최대 완료 시간을 최소화하는 것이 목표입니다.

형식적 정의

n개의 기계와 m개의 작업이 있습니다.각 작업에는 정확히 m개의 작업이 포함됩니다.작업의 i번째 작업은 i번째 기계에서 실행해야 합니다.어떤 기계도 동시에 여러 작업을 수행할 수 없습니다.각 작업의 각 조작에 대해 실행 시간이 지정된다.

한 작업 내의 작업은 지정된 순서대로 수행해야 합니다.첫 번째 조작은 첫 번째 머신에서 실행된 후 (첫 번째 조작이 완료되면) 두 번째 머신에서 두 번째 조작이 실행되며, n번째 조작까지 계속됩니다.그러나 작업은 임의의 순서로 실행할 수 있습니다.문제의 정의는 이 작업 순서가 각 머신에 대해 완전히 동일함을 의미합니다.문제는 이러한 최적의 배치, 즉 가능한 한 총 작업 실행 시간이 가장 짧은 배치를 결정하는 것이다.

성능 측정 시퀀싱())

시퀀스 문제는 하나 또는 여러 시퀀스 목표가 최적화되도록 시퀀스 S를 결정하는 것이라고 할 수 있다.

(평균)흐름시간 $\sum (w_{i})F_{i}$ ( $\sum (w_{i})F_{i}$ i ) $\sum (w_{i})F_{i}$ \ $displaystyle \ sum$ ( w $_$ { $\sum (w_{i})F_{i}$ ) $F_{i}}$
메이크스판, C_max
(평균)지각, $\sum (w_{i})T_{i}$ ( $\sum (w_{i})T_{i}$ i ) $\sum (w_{i})T_{i}$ \ $displaystyle \ sum$ ( w $_$ { $\sum (w_{i})T_{i}$ ) $T_{i}}$
....

성능 측정에 대한 자세한 설명은 Malakooti(2013)^[1]에서 확인할 수 있다.

플로우 숍 스케줄링의 복잡성

Garey et al.(1976)^[2]가 제시한 바와 같이, 플로우 숍 스케줄링 문제의 확장은 대부분 NP-hard이며 O(nlogn)에서 최적으로 해결할 수 있는 문제는 거의 없다. 예를 들어 F2 prmu_max C는 Johnson's ^[3]Rule을 사용하여 최적으로 해결할 수 있다.

Taillard는 플로우 숍, 오픈 숍 및 취업 ^[4]숍 스케줄링을 위한 상당한 벤치마크 문제를 제공합니다.

해결 방법

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

제작 시간 최소화, C_max

F2 prmu_max C와 F3 prmu_max C는 Johnson's^[3] Rule을 사용하여 최적으로 풀 수 있지만 일반적인 경우 솔루션의 최적성을 보장하는 알고리즘은 없다.

플로우 숍에는 시간 0에 동시에 사용 가능한 n개의 작업이 포함되어 있으며, 그 사이에 무제한 저장 공간을 두고 직렬로 배열된 두 대의 기계로 처리됩니다.모든 작업의 처리 시간을 확실하게 알 수 있습니다.제작 시간을 최소화하기 위해 기계에서 n개의 작업을 예약해야 합니다.2대의 머신플로우 숍에서 작업을 스케줄링하기 위한 Johnson의 규칙은 다음과 같습니다.

최적의 스케줄에서는 min{p_1i,p_2j} < min{p_1j,p_2i}인 경우 작업 i가 작업 j보다 우선합니다.여기서_1i p는 기계1에서의 작업i의 처리시간, p는_2i 기계2에서의 작업i의 처리시간이다.마찬가지로_1j p와_2j p는 각각 기계 1과 기계 2의 작업 j의 처리시간이다.

Johnson 알고리즘의 경우:

p를 기계 1의 j작업 처리시간으로 합니다_1j.

그리고_2j p 기계 2의 작업 j의 처리 시간

Johnson 알고리즘:

p < p_2j 의 모든_1j 작업을 포함하는 폼 세트 1
p > p의_2j 모든_1j 작업을 포함하는 폼 세트2에서는 p = p의_2j 작업을_1j 어느 한 세트에 넣을 수 있습니다.
다음과 같이 시퀀스를 형성합니다.
(i) set1의 작업은 순서대로 p(SPT)의_1j 오름차순으로 진행됩니다.

(ii) 세트2의 작업은 p(LPT)의_2j 내림차순으로 이루어진다.타이는 임의로 끊어집니다.

이 타입의 스케줄을 SPT(1)~LPT(2) 스케줄이라고 부릅니다.

사용 가능한 솔루션 방법에 대한 자세한 설명은 Malakooti(2013)^[1]에서 제공합니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b 말라쿠티, B(2013).다양한 목표를 가진 운영 및 운영 시스템John Wiley & Sons. ISBN 978-1-118-58537-5.
^ Garey, M. R., Johnson, D. S., & Sethi, R. (1976).플로우숍과 잡샵 스케줄의 복잡성.연산 연구의 수학, 1(2), 117~129.
^ ^a ^b 존슨, S. M.(1954년)셋업 시간을 포함한 최적의 2단계 및 3단계 생산 일정해군 연구 물류 분기, 1(1), 61-68.
^ Taillard, E. (January 1993). "Benchmarks for basic scheduling problems". European Journal of Operational Research. 64 (2): 278–285. doi:10.1016/0377-2217(93)90182-M.

[Malakooti-1] 말라쿠티, B(2013).다양한 목표를 가진 운영 및 운영 시스템John Wiley & Sons. ISBN 978-1-118-58537-5.

[Garey-2] Garey, M. R., Johnson, D. S., & Sethi, R. (1976).플로우숍과 잡샵 스케줄의 복잡성.연산 연구의 수학, 1(2), 117~129.

[Johnson-3] 존슨, S. M.(1954년)셋업 시간을 포함한 최적의 2단계 및 3단계 생산 일정해군 연구 물류 분기, 1(1), 61-68.

[Taillard-4] Taillard, E. (January 1993). "Benchmarks for basic scheduling problems". European Journal of Operational Research. 64 (2): 278–285. doi:10.1016/0377-2217(93)90182-M.

[1]

[2]

[3]

[4]

v t 최적의 작업 스케줄링 문제
1단계 작업	싱글 머신 동일 기계 균일한 기계 관련 없는 기계
다단계 작업	병렬 태스크 오픈 숍 플로우 숍 잡샵
최적화 목표	메이크스판 귀기울림 지각 지각 스루풋
기타 요건	인터벌 스케줄링 정확한 작업 스케줄링

Search

플로우샵 스케줄링

네임스페이스

더

목차

형식적 정의

성능 측정 시퀀싱())

플로우 숍 스케줄링의 복잡성

해결 방법

제작 시간 최소화, C_max

「」를 참조해 주세요.

레퍼런스

Search

플로우샵 스케줄링

형식적 정의

성능 측정 시퀀싱())

플로우 숍 스케줄링의 복잡성

해결 방법

제작 시간 최소화, Cmax

「 」를 참조해 주세요.

레퍼런스

제작 시간 최소화, C_max

「」를 참조해 주세요.