시뮬레이션 최적화 라이브러리:처리량 최대화

처리량 최대화의 문제는 n단계 흐름 라인에서 최대 예상 처리량을 찾으려고 시도하는 반복 확률 최적화 알고리듬군입니다.Pichitlamken 등에 따르면.(2006), 개별 서비스 속도 중간 규모 문제에 대한 두 가지 해결책이 있습니다.예상 처리량(시간 측정에 설명된 바와 같이 예열 기간 및 비율 추정의 필요성을 통해 유도된 근사치와 달리 긴 시간에 걸친 제한 처리량으로 정의됨).각 시뮬레이션 복제는 빈 시스템에서 시작하여 2000개의 릴리스된 작업으로 시스템을 워밍업한 다음, 다음 50개의 작업을 릴리스하는 데 필요한 시간 T를 기록하고, 이 복제의 처리량을 단위 시간당 50=T 작업으로 추정하는 것으로 구성되어야 합니다.그런 다음 시간은 수행된 시뮬레이션 복제 횟수로 측정됩니다.

문제명세서

스테이션 2, 3, ..., n 앞에 유한 버퍼 저장이 있고, b2, b3, ..., bn으로 표시되며, 스테이션 1 앞에 무한한 수의 작업이 있는 n단계 흐름 라인을 고려합니다.각 스테이션에는 단일 서버가 있으며, 스테이션 i의 서비스 시간은 서비스 속도 ri, i = 1, ..., n으로 지수 분포됩니다. 스테이션 i의 버퍼가 가득 차면 스테이션 i-1이 차단(생산 차단)되어 스테이션 i-1에서 완료된 작업을 해제할 수 없습니다. i = 2, ..., n.총 버퍼 공간 및 서비스 속도가 제한됩니다.목표는 처리량(단위 시간당 흐름 라인의 평균 출력)이 최대화되도록 버퍼 할당 및 서비스 속도를 찾는 것입니다.선택적으로 서비스 속도를 정수 또는 연속형 변수로 사용할 수 있습니다.두 경우 모두 버퍼 할당이 정수이기 때문에 문제는 여전히 정수 순서로 간주됩니다.제약 조건은 다음과 같습니다.

b₂+...+b_n≤Br₁+r₂+...+r_n≤R

권장 매개 변수 설정

중간 크기의 문제는 n = 3;B = 20;R = 20입니다.더 큰 문제는 n = 12;B = 80;R = 80입니다.

시작 솔루션

b=를₂ 예로 들어 보겠습니다...=b_n 제약 조건을 위반하지 않고 가능한 한 큼.잔여 버퍼 공간을 가장 큰 숫자의 스테이션(버퍼당 하나)에 할당합니다.마찬가지로 균일한 서비스 요금을 선택합니다.여러 개의 초기 솔루션이 필요한 경우 다음과 같이 버퍼 간격과 서비스 속도를 샘플링합니다.연속 서비스 속도의 경우, 심플렉스 {r≥0:r₁+r₂+}에서 균일하게 샘플링하십시오.+r_n≤R}. 이것은 n-1 독립적인 균일 랜덤 변수₁ U,...,Uon_n-1 [0,R]을 생성하여 U≤...가 되도록₍₁₎ 순서를 지정함으로써 수행할 수 있습니다.≤ U_(n-1), U=0 및 U_(n)=R을 설정하고₍₀₎ 마지막으로 r=U-U_(k)(k-1), k = 1,...,n을 설정합니다_k. 이와 유사한 절차를 사용하여 버퍼 공간을 할당할 수 있으며 값 0을 사용할 수 있습니다.

시간 측정

각 시뮬레이션 복제는 빈 시스템에서 시작하여 2000개의 릴리스된 작업으로 시스템을 워밍업한 다음, 다음 50개의 작업을 릴리스하는 데 필요한 시간 T를 기록하고, 이 복제의 처리량을 단위 시간당 50=T 작업으로 추정하는 것으로 구성되어야 합니다.그런 다음 시간은 수행된 시뮬레이션 복제 횟수로 측정됩니다.

최적 솔루션

버퍼 공간을 작업 대기 중인 조각의 수로 간주합니다. 즉, 현재 작업은 버퍼 공간의 일부로 계산되지 않습니다. 각 작업을 통해 모든 단계를 떠나는 시간을 결정합니다.개별 서비스 속도 중간 크기 문제에 대한 두 가지 해결책이 있습니다. 즉, r = (6, 7, 7), b = (12, 8) 및 r = (7, 7, 6), b = (8, 12), 예상 처리량(장기적인 범위에 걸친 제한 처리량으로 정의됨,"시간 측정"에 설명된 바와 같이, 예열 기간 및 비율 추정의 필요성을 통해 유도된 근사치와는 대조적입니다.

처리량 = 50/(마지막 작업이 출시된 시간 - 50번째에서 마지막 작업이 출시된 시간)

보고된 알고리즘 성능

없음.

레퍼런스

^{[1] [2] [3]}