선형 병목 현상 할당 문제

수학 내 영역인 결합 최적화의 경우 선형 병목현상 할당 문제(LBAP)는 선형 할당 문제와 유사하다.^[1]

간단히 말해서 그 문제는 다음과 같이 명시되어 있다.

에이전트와 태스크가 여러 개 있다.모든 에이전트는 에이전트-태스크 할당에 따라 달라질 수 있는 일부 비용을 발생시키면서 모든 작업을 수행하도록 할당할 수 있다.개별 할당 중 최대 비용이 최소화되도록 각 태스크에 정확히 하나의 에이전트를 할당하여 모든 태스크를 수행해야 한다.

"병목"이라는 용어는 공통적인 유형의 문제 적용으로 설명되며, 여기서 비용은 대리인이 수행하는 업무의 지속시간이다.이 설정에서 "최대 비용"은 "최대 기간"이며, 이는 전체 작업 스케줄의 병목 현상을 최소화하기 위한 것이다.

형식 정의

병목현상 할당 문제의 공식 정의는

무게 함수 C : A × T → R과 함께 A와 T의 두 세트를 주어 비용 함수가 다음과 같은 바이어스 f : A → T를 찾는다.

${\displaystyle \max _{a\in A}C(a,f(a))}$

최소화한다.

일반적으로 중량 함수는 정사각형 실질 가치 매트릭스 C로 간주되므로 비용 함수는 다음과 같이 기록된다.

${\displaystyle \max _{a\in A}C_{a,f(a)}}$

수학적 프로그래밍 공식

${\displaystyle \min \,\max_{i,j}c_{ij}x_{ij}}}}}$

대상:

${\displaystyle \sum _{j=1}^{n}x_{ij}=1(i=1,2,\reason,n),}$

${\displaystyle \sum _{i=1}^{n}x_{ij}=1(j=1,2,\light,n),}$

${\displaystyle x_{ij}\in \{0,1\}(i,j=1,2,\n)}$

점증약학

$c{\displaystyle {}_{}^{}}$ ${{\$은(는) n 에이전트 및 n 태스크의 문제에 대한 최적의 목표 함수 값을 나타낸다.비용 $c{\displaystyle {}_{}}$ i ${\displaystyle j_{}}$ ${\$이(가) (0,1)의 균일한 분포로부터 샘플링된 경우$$,

${\displaystyle E[c_{n}^{*}}={\frac {\log n+\log 2+\gamma }{n}}}{n}+O\left({\log n)^{2}}{n^{n^{7/5}}\오른쪽)}}}}$

그리고

${\displaystyle Var[c_{n}^{*}}={\frac {\frac}-2(\log 2)^{2}}:{n^{2}}+O\왼쪽({\frac {(\log n)^{2}}{n^{7/3}}}\오른쪽).}$

참조