멀티비트 알고리즘

멀티비트 알고리즘은 원래 동일한 머신 스케줄링 문제를 위해 개발된 멀티웨이 번호 분할 알고리즘입니다.그것은 Coffman, Garey, ^[1]Johnson에 의해 개발되었다.이것의 참신함은 그것이 서브루틴으로 또 다른 유명한 문제인 쓰레기통 패킹 문제를 위한 알고리즘을 사용한다는 사실에서 비롯된다.

알고리즘

알고리즘에 대한 입력은 숫자 집합 S와 파라미터 n입니다.필요한 출력은 S를 n개의 서브셋으로 분할하여 가장 큰 서브셋합(makespan이라고도 함)을 가능한 한 작게 하는 것입니다.

이 알고리즘은 서브루틴으로서 First-fit-decreating bin packing(FFD; 퍼스트 핏 감소 빈 패킹)이라고 불리는 알고리즘을 사용합니다.FFD 알고리즘은 같은 숫자의 집합 S와 빈 용량 c를 입력으로 받아들입니다.각 빈의 숫자의 합계가 최대 C가 되도록 경험적으로 숫자를 빈에 묶어서 가능한 한 적은 빈을 사용하는 것을 목표로 합니다.멀티잇은 용량 C가 다른 FFD를 여러 번 실행하고 용량 C를 가진 FFD가 최대 n개의 빈에 S를 채울 때까지 C를 찾습니다.이를 찾기 위해 다음과 같이 바이너리 검색을 사용합니다.

L : = max ( sum ( S ) / n , max ( S ) 。빈 용량이 L보다 작으면 모든 패킹이 n개 이상의 빈을 사용해야 합니다.
U : = max ( 2 sum ( S ) / n, max ( S ) 。참고: 빈 용량이 U 이상인 경우 FFD는 최대 n개의 빈을 사용합니다.증명: 모순을 통해 일부 입력_i s가 처음 n개의 빈에 맞지 않는다고 가정합니다.확실히 이것은 i n n+1일 경우에만 가능하다.s > C/2일 경우_i 입력은 내림차순으로 정렬되므로 S의 첫 번째 n+1 입력 모두에 대해 동일한 부등식이 유지됩니다.즉, sum(S) > (n+1) C/2 > n U/2는 U의 정의에 모순됩니다.그렇지 않으면 s c C/2가 됩니다_i.따라서 처음 n개의 빈의 합계는 C/2보다 큽니다.이는 다시 sum(S)> n C/2> n U/2의 모순을 의미합니다.
k회 반복(여기서 k는 정밀도 파라미터):
- C : = (L+U)/2로 하자.용량이 C인 S에서 FFD를 실행합니다.
  - FFD가 최대 n개의 빈을 필요로 하는 경우 U := C로 하여 U를 감소시킨다.
  - FFD에 n개 이상의 bin이 필요한 경우 L : = C로 하여 L을 증가시킨다.
마지막으로 용량 U로 FFD를 실행합니다. 최대 n개의 빈을 사용할 수 있습니다.결과 스케줄링을 반환합니다.

성능

멀티짓은 상수 요인 근사 알고리즘입니다.항상 최적의 제작 시간보다 최대 일정 요인이 되는 파티션을 찾습니다.이 상수를 구하려면 먼저 FFD를 분석해야 합니다.FFD의 표준 분석에서는 용량이 일정할 때 빈 개수의 근사치를 고려하지만, 여기서는 빈 개수가 일정할 때 빈 개수의 근사치를 분석할 필요가 있다.형식적으로 모든 입력 크기 S 및 정수 n에 대해 $OPT(S,n)$ $OPT(S,n)$ T $OPT(S,n)$ ( $OPT(S,n)$ , $OPT(S,n)$ n $OPT(S,n)$ ) { $displaystyle$ OPT ( $S$ , $n$ ) } 를 $OPT(S,n)$ 이 용량의 n 개의 빈에 넣을 수 있도록 최소 용량으로 $OPT(S,n)$ . $OPT(S,n)$ $OPT(S,n)$ T $OPT(S,n)$ ( $OPT(S,n)$ , $OPT(S,n)$ $){$ $displaystyle$ OPT ( $S$ , $n$ )는 $OPT(S,n)$ 원래 스케줄링 인스턴스에 대한 최적의 솔루션 값입니다.

$r_{n}$ n $r_{n}$ { $displaystyle$ r _ { $n$ } be $r_{n}$ 、 $r_{n}\cdot OPT(S,n)$ $r_{n}\cdot OPT(S,n)$ $r_{n}\cdot OPT(S,n)$ $r_{n}\cdot OPT(S,n)$ $r_{n}\cdot OPT(S,n)$ , $r_{n}\cdot OPT(S,n)$ $){$ $display r$ _ { $n$ }\ $cdot$ OPT ( $S$ , $n$ )가 $r_{n}\cdot OPT(S,n)$ 최대 n개의 빈을 사용하는 모든 입력 S에 대해 최소 실수라고 $r_{n}$ .

상한

Coffman, Garey 및 Johnson은 $(\$ ^[1]의 $r_{n}$ 상한을 증명합니다.

$r_{n}\leq 8/7\approx 1.14$ $r_{n}\leq 8/7\approx 1.14$ $r_{n}\leq 8/7\approx 1.14$ 8 $r_{n}\leq 8/7\approx 1.14$ / $r_{n}\leq 8/7\approx 1.14$ $r_{n}\leq 8/7\approx 1.14$ 1 $r_{n}\leq 8/7\approx 1.14$ {\ $displaystyle r_{n}\leq$ 8 $/7\약$ 1. $14($ n $r_{n}\leq 8/7\approx 1.14$ = 2일 경우)
$r_{n}\leq 15/13\approx 1.15$ n $r_{n}\leq 15/13\approx 1.15$ $r_{n}\leq 15/13\approx 1.15$ / $r_{n}\leq 15/13\approx 1.15$ $r_{n}\leq 15/13\approx 1.15$ 1. $r_{n}\leq 15/13\approx 1.15$ {\ $displaystyle$ r_ ${n$ }\ $leq$ 15 $/13\약$ 1. $15($ n $r_{n}\leq 15/13\approx 1.15$ = 3일 경우)
$r_{n}\leq 20/17\approx 1.176$ n $r_{n}\leq 20/17\approx 1.176$ 4,5,6,7에 대해 r $r_{n}\leq 20/17\approx 1.176$ $r_{n}\leq 20/17\approx 1.176$ $r_{n}\leq 20/17\approx 1.176$ / $r_{n}\leq 20/17\approx 1.176$ 1.19 $r_{n}\leq 20/17\approx 1.176$ (\ $displaystyle r_{$ n}\ $leq$ 20 $/17\apprough$ 1 $.17 )$
$r_{n}\leq 122/100=1.22$ $22}($ 모든 $r_{n}\leq 122/100=1.22$ n÷8).

MultiFit 알고리즘에서 하한 L은 항상 S를 n개의 빈으로 채울 수 없는 용량입니다.따라서 N-SCTY Limited 항공(S, N)는 N-SCTY Limited 항공(S)에서 N)를 표시합니다. ( 1 $U-L\leq (1/2)^{k}\cdot OPT(S,n)$ ) $U-L\leq (1/2)^{k}\cdot OPT(S,n)$ O $U-L\leq (1/2)^{k}\cdot OPT(S,n)$ P $U-L\leq (1/2)^{k}\cdot OPT(S,n)$ ( $U-L\leq (1/2)^{k}\cdot OPT(S,n)$ , $U-L\leq (1/2)^{k}\cdot OPT(S,n)$ n ){ $displaystyle$ $U$ - L \ $leq$ $($ $U-L\leq (1/2)^{k}\cdot OPT(S,n)$ $U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)$ / $U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)$ $)^{$ k $U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)$ $cdot OPT$ ( $U-L\leq (1/2)^{k}\cdot OPT(S,n)$ $U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)$ , n ) $U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)$ 、 $U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)$ ( $U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)$ , n ) $display$ o / / / / / / / / / / / / / / / / / / $q$ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /최적의 제작 시간의 두 배입니다.k $(\displaystyle$ k $)$ 가 $k$ 충분히 $크면$ MultiFit의 근사 계수를 r $(\$ 에 $r_{n}$ 로 가깝게 할 수 있으며, 최대 1.22입니다.

이후 논문들은 멀티핏에 대한 보다 상세한 분석을 수행했으며, 그 근사 비율이 최대 6/5=1.^[2]2이고, 이후 최대 13/11µ1.182임을 ^[3]입증했다.이것에 대한 원래의 증거는 일부 사례를 놓쳤다; 완전하고 단순한 증거를 제시했다.13/11은 개선할 수 없습니다. 근사 비율이 정확히 13/^[2]11인 n=13인 경우가 있습니다.

하한

n=4의 경우: $r_{n}\geq 20/17$ 은^[5] r n $r_{n}\geq 20/17$ 20 $r_{n}\geq 20/17$ / $r_{n}\geq 20/17$ { $displaystyle r_{n}\geq$ 20 $/17$ 으로, 꽉 끼는 것을 나타냅니다.입력은 9,7,6,5,5,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4 입니다.다음과 같이 용량 17의 4개의 빈에 포장할 수 있습니다.

9, 4, 4
7, 6, 4
5, 4, 4, 4
5, 4, 4, 4

그러나 빈 용량이 20보다 작은 FFD를 실행하면 채워진 빈은 다음과 같습니다.

9,7 [4는 맞지 않음]
6,5,5 [4가 맞지 않음]
4,4,4,4 [4가 맞지 않음]
4,4,4,4
4

처음 4개의 빈의 합계는 각각 16이므로 그 안에 4개를 더 넣을 수 없습니다.따라서 빈 4개로는 충분하지 않습니다.

n=13의 경우: $r_{n}\geq 13/11$ 은^[2] r n $r_{n}\geq 13/11$ 13 $r_{n}\geq 13/11$ $r_{n}\geq 13/11$ { $displaystyle r_{n}\geq$ 13 $/11$ 로, 꽉 끼는 것을 나타냅니다.입력은 다음과 같이 용량 66의 13개의 빈에 넣을 수 있습니다.

40, 13, 13 {8회}
25, 25, 16 {3회}
25, 24, 17 {2회}

그러나 66*13/11 = 78보다 작은 빈 용량으로 FFD를 실행하면 채워진 빈은 다음과 같습니다.

40,25 {8회}
24, 24, 17
17, 16, 16, 16
13, 13, 13, 13, 13 {3회}
13

처음 13개의 빈의 합계는 각각 65이므로 그 안에 13개를 더 넣을 수 없습니다.따라서 13개의 빈으로는 충분하지 않습니다.

균일한 머신으로 퍼포먼스 향상

또한 MultiFit은 균일한 기계 스케줄링이라는 보다 일반적인 설정에서도 사용할 수 있으며, 기계가 처리 ^[6]속도가 다를 수 있습니다.2개의 균일한 머신이 있는 경우 근사 계수는 ${\sqrt {6}}/2$ 6/ $({displaystyle {sqrt$ {6 $}}/2$ 입니다.MPT 알고리즘과 MultiFit을 조합하면 비율은 2 ${\sqrt {2}}+1/2$ + ${\sqrt {2}}+1/2$ / $({sqrt {2}}+1/$ 2 ${\sqrt {2}}+1/2$ ^{[clarification needed]}로 향상됩니다.

최소합계를 최대화하는 퍼포먼스

가장 큰 합(맥스팬)을 최소화하는 이중 목표는 가장 작은 합을 최대화하는 것입니다.Deuermeyer, Friesen 및 Langston은 MultiFit이 이 ^[7]문제에 대해 적절한 근사 계수를 가지고 있지 않다고 주장합니다.

「MULTIIT를 사용한 메이크 스판 문제의 해결에서는, 1개의 프로세서를 전혀 ^{[clarification needed]}사용하지 않는 경우의 예를 간단하게 작성할 수 있습니다.이러한 솔루션은 제조 기간 문제에 대해서는 허용되지만 우리 문제에는 전혀 허용되지 않습니다.MULTICT의 수정은 우리의 문제에 더 적합할 수 있지만 LPT보다 더 나은 최악의 경우를 만들어 낼 수 있는 것은 없습니다."

실증 아이디어

최소 반례

$(\$ })의 $r_{n}$ 상한은 모순으로 증명됩니다.임의의 정수 p q에 대해 $r_{n}>p/q$ n $r_{n}>p/q$ > $r_{n}>p/q$ / $r_{n}>p/q$ { $displaystyle$ r $_$ { $n$ } > $p/q$ }의 경우 인스턴스 S 및 n개의 빈으로 정의되는 (p/q)-countrexample이 존재합니다.

S는 용량 q의 n개의 빈에 포장할 수 있다.
FFD는 용량 p의 n개의 빈에 S를 채울 수 없습니다.

이러한 반례가 존재하는 경우, 최소(p/q)-반례도 존재하며, 이는 S에서 가장 적은 수의 항목과 가장 작은 수의 빈 n을 갖는 (p/q)-반례이다.최소(p/q) 카운트의 예에서 FFD는 마지막(가장 작은) 항목을 제외한 S의 모든 항목을 용량 p의 n개의 빈으로 포장한다.최소(p/q)-카운트 예시로, 용량_n p의 이들₁ n개의 빈에 대한 (불완전한) FFD 패킹, 용량 p의 P의 빈, 용량_n+1 q의 n개의 빈에 대한 (완전한_n) 최적 패킹을 나타낸다₁.다음과 같은 조건을 증명할 수 있습니다.

{QQ_1,...,_n}의 k개 하위 집합의 결합은 {PP_1,...,_n+1}의 k개 하위 집합의 결합에 의해 지배되지 않습니다("지배적"은 지배적 하위 집합의 각 항목이 지배적 하위 집합의 약하게 정의된 항목에 매핑된다는 의미).그렇지 않으면 다음과 같은 작은 반례를 얻을 수 있다.[1] P의_i 모든 항목을 삭제합니다.완전하지 않은 FFD 패킹에는 n-k개의 빈이 필요하지만 가장 작은 항목(또는 전체 빈)은 여전히 개봉된 상태로 남아 있습니다.[2] 최적 포장_i Q는 각각의 아이템을 주요 아이템과 교환한다.여기서 k개의 서브셋Q는_i 더 크지만(아마도 q보다 크다), 다른 모든 n개의 서브셋은 더 작습니다(특히 최대 q).따라서 P의_i 모든 항목을 삭제한 후 나머지 항목은 크기 q의 n-k bin까지 포장할 수 있습니다.
각 QQ에는_1,...,_n 최소 3개의 항목이 포함되어 있습니다.이것은 [a] 하나의 항목을 가진 각 Q가_i_i 그 항목을 포함하는 P에_j 의해 지배되기 때문입니다.[b] 두 개의 항목 x와 y가 모두 동일한_j P에 있으면 Q가_i 이 P에_j 의해 지배됩니다. [c] xyy, x가 일부_j P에 있고 y가 일부 P에_k 있다고 가정합니다.즉, y가 P에 적합하지_j 않다는 것을 의미합니다.하지만 x+y qq.즉, P에 z y y 항목이 포함되어 있어야 합니다_j. 따라서_i Q는 P에 의해_j 지배됩니다. [d] x,y, x는 일부_j P에 있고 y는 일부 P에_k 있습니다.즉, 이전 항목 z x x가 있어야 하므로 Q는_i P가_k 지배합니다.
그렇지 않으면 우리에게 지배권이 있었고, 이전의 보조명언에 의해, 더 작은 반례를 얻을 수 있었다.
각_1,...,_n PP는 최소 2개의 항목을 포함합니다.이는 일부_i P가 하나의 항목만 포함하는 경우 마지막(가장 작은) 항목이 P에 적합하지 않음을 의미하기 때문입니다.즉, 이 단일 항목은 이전 조건과 달리 최적의 번들에 단독으로 있어야 합니다.
가장 작은 아이템의 사이즈로 합시다. $s>{\frac {n}{n-1}}(p-q)$ 으로 s $s>{\frac {n}{n-1}}(p-q)$ > $s>{\frac {n}{n-1}}(p-q)$ - $s>{\frac {n}{n-1}}(p-q)$ ( $s>{\frac {n}{n-1}}(p-q)$ - $){\frac {n}{n-1}(p-q$ 증거:nbsp; nbsp; ={n}(를) + ={n2}) + ={n2}(를)에 적합하게 됩니다.U. $\sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q$ ) $\sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q$ + $\sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q$ $\sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q$ { $displaystyle \sum$ _ { $i=1}^{n}sum(P_{i}+s\leq$ n $\cdot$ q $\sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q$ 부등식을 차감하면 $s>{\frac {n}{n-1}}(p-q)$ > $s>{\frac {n}{n-1}}(p-q)$ - 1 ( $s>{\frac {n}{n-1}}(p-q)$ $s>{\frac {n}{n-1}}(p-q)$ ) {\ $displaystyle$ s > { $n$ } { n - 1 $s>{\frac {n}{n-1}}(p-q)$ } （ p - $q$ ） } $s>{\frac {n}{n-1}}(p-q)$ 。
모든 아이템의 사이즈는 $q-2s$ q - $q-2s$ (\ $displaystyle q-2s$ 이는 각 최적 보관함에 최소 3개의 항목(용량 q)이 있기 때문입니다.
각 bin_1,...,_n PP의 항목 합계가 p $p-s$ - $p-s$ \ $displaystyle$ 크며, 그렇지 않으면 최소 항목을 추가할 수 있습니다.

5/4 상한

위의 조건으로부터 이미 느슨한 $r_{n}\leq 5/4=1.25$ r $r_{n}\leq 5/4=1.25$ 5 $r_{n}\leq 5/4=1.25$ / $r_{n}\leq 5/4=1.25$ $r_{n}\leq 5/4=1.25$ ${{display$ style $r_{n}\leq$ 5/ $4=1.$ 25 $r_{n}\leq 5/4=1.25$ 을 증명할 수 있습니다. 증명.S, n을 최소(5/4)-카운트 예제로 합니다.위의 렘마는 다음을 의미합니다.

$s>{\frac {n}{n-1}}(5-4)>1$ > $s>{\frac {n}{n-1}}(5-4)>1$ - $s>{\frac {n}{n-1}}(5-4)>1$ 1 ( $s>{\frac {n}{n-1}}(5-4)>1$ - $s>{\frac {n}{n-1}}(5-4)>1$ )> $s>{\frac {n}{n-1}}(5-4)>1$ \ $displaystyle$ s > { \ $frac$ { $n$ } { n - $1$ 。최적의 용량은 4이므로 최적의 빈에는 4개 이상의 항목을 포함할 수 없습니다.따라서 각 최적 통에는 최대 3개의 항목이 들어 있어야 하며 항목 수는 최대 3n개입니다.
각 항목의 크기는 $4-2s$ 4 - $(\$ displaystyle $4-2s$ 이고 각 FFD 빈의 크기는 $(\displaystyle 5-s$ 를 $5-s$ 합니다. 일부 FFD 빈에 2개만 포함된 경우, 합계는 $8-4s=5+(3-3s)-s<5-s$ 8 $8-4s=5+(3-3s)-s<5-s$ - $=$ + ( $8-4s=5+(3-3s)-s<5-s$ - $8-4s=5+(3-3s)-s<5-s$ ) - $8-4s=5+(3-3s)-s<5-s$ (\ $display$ style $8$ - 3s )가 됩니다.그러나 이는 FFD가 정확히 n개의 빈을 산출한다는 것을 의미합니다. 이는 모순입니다.

FFD 패킹 구조

보다 엄격한 경계를 입증하려면 최소(p/q)-카운트 예의 FFD 패킹을 자세히 살펴봐야 합니다.항목 및 FFD bin₁ P,...P의_n 명칭은 다음과 같습니다.

일반 항목은 다음 빈_i+1 P를 열기 전에 일부 빈 P에_i 추가된 항목입니다.마찬가지로 정규항목은 적어도 j>i의 각 bin_j P 내의 모든 항목과 같은 크기의 P 내의_i 항목이다.
폴백 항목은 다음 빈_i+1 P를 연 후 일부 빈 P에_i 추가되는 항목이다.마찬가지로 폴백 아이템은 P의_i+1 가장_i 큰 아이템보다 작은 아이템이다.
일반 k-bin은 k개의 일반 항목을 포함하고 폴백 항목은 포함하지 않는 빈입니다.
폴백 k-bin은 k개의 일반 항목과 일부 폴백 항목을 포함하는 빈입니다.

이러한 정의와 FFD의 작동 직후에 다음과 같은 Lemma가 있습니다.

k₁<k이면₂ 모든 k-bin은₁ 모든 k-bin의₂ 왼쪽에 있습니다.이는 모든 빈의 용량이 동일하기 때문에 빈에 들어가는 일반 항목이 많을 경우 이러한 항목은 더 작아야 하므로 나중에 할당해야 합니다.
P가 k-bin일 경우_i P의_i k 정규 항목의 합계는 ${\frac {k}{k+1}}\cdot p$ k ${\frac {k}{k+1}}\cdot p$ + ${\frac {k}{k+1}}\cdot p$ p $(\displaystyle\frac {k}{k+1}\cdot$ p ${\frac {k}{k+1}}\cdot p$ 보다 커집니다.그렇지 않으면 새 bin을 열기 전에 다른 항목을 추가할 수 있습니다.
P와_i+1 P가 둘 다 k-빈이고 P의_i k 정규 항목의 합계가 P의_i+1 합계와 같으면(이는_i 항목이 크기를 줄여서 정렬되기 때문입니다).
모든 일반 k-bin은 모든 폴백 k-bin의 왼쪽에 있다.이는 모든 빈의 용량이 동일하기 때문에 빈에 들어가는 폴백 항목이 많을 경우 이러한 항목은 더 작아야 하므로 나중에 할당해야 합니다.

최소한의 반례에서는 (각 빈은 적어도 2개의 항목을 포함하므로) 정규 1-빈이 없으므로 위의 렘마별로 FFD 빈 P₁,......P가_n 유형별로 정렬됩니다.

제로 이상의 폴백 1-빈
다음으로, 0 이상의 일반 2-bins;
그 후, 0 이상의 폴백 2-bins;
그 후, 0 이상의 일반 3-bins;
그 후, 0 이상의 폴백 3-bins;
기타 등등.

1.22 상한

$r_{n}\leq 1.22$ $r_{n}\leq 1.22$ n $({displaystyle r_{n}\leq$ 1. $22)$ 는 $r_{n}\leq 1.22$ ^[1] 최소(122/100) 카운트 예를 가정하여 증명됩니다.각 품목은 크기와 FFD 패킹 내 통에 따라 무게가 부여됩니다.가중치는 각 FFD 빈의 총 무게가 최소 x이고 거의 각 최적 빈의 총 무게가 최대 x(일부 사전 결정된 x)가 되도록 결정된다.이는 FFD 빈의 수가 최적인 빈의 수라는 것을 의미하며, 이는 반례라는 가정과 모순됩니다.

위의 레마로 알 수 있는 것은 다음과 같습니다.

가장 작은 항목의 크기는 s > p-q = 22를 충족하므로 일부 D > 0의 경우 s = 22+D입니다.
각 최적 빈에는 최대 4개의 항목(바닥(100/22))이 들어 있고 각 FFD 빈에는 최대 5개의 항목(바닥(122/22))이 들어 있습니다.
모든 항목의 크기는 최대 q-2s = 56-2D입니다.
각 FFD 빈의 합계는 p-s = 100-D보다 큽니다.
1-bin에서는 정규 항목의 크기가 p/2=61 이상이어야 하지만 여기서는 모든 항목의 크기가 56 미만이어야 하므로 1-bin은 없습니다.

D > 4 의 경우는, 각 항목의 사이즈가 26 보다 크기 때문에, 각 최적의 빈(용량 100)에는 최대 3 개의 아이템을 포함할 필요가 있습니다.각 항목은 56-2D보다 작고 각 FFD 빈은 100-D보다 큰 합계를 가지므로 각 FFD 빈은 최소 3개의 항목을 포함해야 합니다.따라서 최대 n개의 FFD 빈 - 모순이 있습니다.그래서 지금부터 우리는 D44로 가정합니다.품목에는 다음과 같이 유형 및 무게가 할당됩니다.

각 일반 2-bin에 있는 두 개의 항목은 마지막 항목을 제외하고 크기가 각각 (100-D)/2보다 큽니다.이러한 항목은 모두 타입₂ X라고 불리며 무게(100-D)/2가 할당됩니다.마지막 2개의 일반 빈은 특수한 경우입니다.두 항목의 크기가 (100-D)/2보다 크면 두 항목도 유형 X입니다₂.그렇지 않으면 유형 Z라고 불리며 무게는 크기와 동일합니다.
각 폴백 2-bin의 2개의 일반 아이템의 총 사이즈는 2*122/3보다 큽니다.이것들은 타입₂ Y라고 불리며, 무게는 사이즈에서 D를 뺀 것과 같습니다.
각 일반 3-bin의 3개 항목(마지막 항목 제외)은 각각 (100-D)/3보다 클 수 있습니다.이러한 항목은 모두 타입₃ X라고 불리며 (100-D)/3의 무게가 할당됩니다.마지막 3개의 일반 빈은 특수한 경우입니다.모든 아이템의 사이즈가 (100-D)/3보다 크면 그 아이템도 타입₃ X가 됩니다.그렇지 않으면 타입 Z라고 불리며 무게는 사이즈와 동일합니다.
각 폴백 3-bin의 3개의 일반 아이템은 총 사이즈가 3*122/4보다 큽니다.이것들은 타입₃ Y라고 불리며, 무게는 사이즈에서 D를 뺀 것과 같습니다.
각 일반 4-bin의 4개 항목은 마지막 항목을 제외하고 크기가 각각 (100-D)/4보다 큽니다.이러한 항목은 모두 타입₄ X라고 불리며 (100-D)/4의 무게가 할당됩니다.마지막 4개의 일반 빈은 특수한 경우입니다.모든 아이템의 사이즈가 (100-D)/4보다 크면 그 아이템도 타입₄ X가 됩니다.그렇지 않으면 타입 Z라고 불리며 무게는 사이즈와 동일합니다.
나머지 항목(폴백 2-bin 및 3-bin의 모든 폴백 항목, 모든 폴백 4-bin 및 기타 모든 5개 항목 빈 포함)은 모두 유형₅ X라고 하며, 그 무게는 22(D / 12/5) 또는 (100-D)/4(그렇지 않은 경우)와 같습니다.임계값 12/5는 가중치가 항상 최대 22+D가 되도록 계산되었으며, 따라서 가중치는 항상 크기보다 작습니다.

각 항목의 무게는 최대 크기입니다(중량은 "반올림"된 크기로 볼 수 있습니다).그러나 모든 FFD 보관함에 있는 항목의 총 무게는 최소 100-D입니다.

일반 2-bin, 일반 3-bin 및 일반 4-bin의 경우:
- 마지막이 아닌 사람들에겐, 이것은 즉시입니다.
- 마지막 빈에는 무게가 크기와 같은 Z 유형 항목만 포함되므로 이러한 빈의 총 무게가 총 크기인 100-D보다 큽니다.
폴백 2-바인에는 총 무게가 2*122/3-2D보다 큰 2개의 타입₂ Y 항목과 무게가 22 이상인 최소 1개의 타입₅ X 항목(D 12 12/5) 또는 (100-D)/4(그렇지 않은 경우)이 포함됩니다.두 경우 모두 총 중량은 100-D를 초과합니다.
폴백 3-bin은 총 중량이 3*122/4-3D보다 큰 3종류의₃ Y품목과 최소 중량이 22종류의 X품목을₅ 포함합니다.따라서 D is4 이후 총 중량은 3*122/4+22-3D = 113.5-3D > 105.5-D > 100-D를 초과합니다.
5-품목 통에는 크기가 22+D 이상이고 무게가 22 이상인 5개의 항목이 들어 있으므로 총 무게가 100-D보다 큽니다.

대부분의 최적 빈에 있는 항목의 총 무게는 최대 100-D입니다.

이는 Y형₂ 아이템 또는 Y형₃ 아이템을 포함하는 모든 최적 빈에 대해 명확합니다. 왜냐하면 그 무게는 크기에서 D를 뺀 값이고, 다른 아이템의 무게는 최대 크기이며, 최적 빈의 총 크기는 최대 100이기 때문입니다.
유형₂ X, 유형₃ X, 유형₄ X 및 유형₅ X 항목만 포함하는 최적 빈의 경우 가능한 모든 구성(크기 100의 최적 빈에 맞는 모든 조합)을 확인하고 각 구성의 총 무게가 최대 100-D인지 확인할 수 있습니다.
유형 Z 항목이 들어 있는 최적 빈의 총 무게가 100-D보다 클 수 있습니다.총 중량은 최대 100이므로 이러한 빈마다 최대 D의 "초과 중량"이 있습니다.단, Type-Z 항목의 수는 제한되어 있습니다.
- D > 12/5 의 경우는, 최대 5 개의 타입 Z 항목이 있습니다(마지막의 레귤러 2-bin 에 2 개, 마지막의 레귤러 3-bin 에 3 개 있습니다.마지막의 레귤러 4-bin 에 있는 항목은 모두 타입₄ X 입니다).따라서 초과 중량은 최대 5D입니다.FFD와 최적 빈의 총 무게를 비교하면 s < 5D 20 20 < 22가 나오는데, 이는 모순이다.
- 그렇지 않으면 최대 9개의 타입 Z 항목(2+3+4)이 있습니다.따라서 초과 중량은 최대 9D입니다.FFD와 최적 빈의 총 무게를 비교하면 s < 9D 108 108/5 < 22가 나오는데, 이는 모순이다.

13/11 상한

$r_{n}\leq 13/11\approx 1.182$ $r_{n}\leq 13/11\approx 1.182$ n $r_{n}\leq 13/11\approx 1.182$ 13 $r_{n}\leq 13/11\approx 1.182$ $r_{n}\leq 13/11\approx 1.182$ 1. $r_{n}\leq 13/11\approx 1.182$ ${$ $displaystyle r$ _ { $n$ } \ $leq$ 13 / $11 \ about$ 1.182 $r_{n}\leq 13/11\approx 1.182$ }는 $r_{n}\leq 13/11\approx 1.182$ ^[3] 최소((120-3d) 카운트 예제를 가정하고 d< 20/33)를 사용하여 모순을 도출함으로써 증명된다.

비단조성

MultiFit은 다음과 같은 점에서 모노톤이 아닙니다. MultiFit이 반환하는 파티션의 최대 합계가 증가하는 동안 입력이 감소할 수 있습니다.예를 들어,^[1]^{: Fig.4} n=3과 입력 번호는 다음과 같습니다.

44, 24, 24, 22, 21, 17, 8, 8, 6, 6.

FFD는 이러한 입력을 용량 60(최적)의 3개의 빈에 넣습니다.

44, 8, 8;
24, 24, 6, 6;
22, 21, 17.

그러나 "17"이 "16"이 되면 용량이 60인 FFD에는 4개의 빈이 필요합니다.

44, 16;
24, 24, 8;
22, 21, 8, 6;
6.

따라서 MultiFit은 용량을 62로 늘려야 합니다.

44, 16;
24, 24, 8, 6;
22, 21, 8, 6.

일반화: 잡무의 공정한 할당

멀티잇은 ^[5]더 일반적인 문제인 가사 분담의 최대화 문제로 확장되었다.이 문제에서 S는 허드렛일 세트이며, 허드렛일에 잠재적으로 다른 평가를 할당하는 에이전트가 n개 있습니다.목표는 각 에이전트에게 i의 평가에 따라 최적의 스케줄링에서 최대 r배의 가치를 지닌 일련의 허드렛일을 제공하는 것입니다.간단한 접근법은 각 에이전트가 MultiFit 알고리즘을 사용하여 임계값을 계산하고 각 에이전트가 자신의 임계값을 사용하는 알고리즘을 사용하는 것입니다.이 어프로치가 유효하면, 대략 13/11이 됩니다.단, 이 접근법은 FFD의 비단조성으로 인해 실패합니다.

예

여기 ^[5]^{: Ex.5.2}예가 있습니다.4개의 에이전트가 있으며 두 가지 유형의 평가를 가지고 있다고 가정합니다.


타입 A:	51	27.5	27.5	27.5	27.5	25	12	12	10	10	10	10	10	10	10	10	10
타입 B:	51	27.5	27.5	27.5	27.5	24	20	20	8.33	8.33	8.33	8.33	8.33	8.33	8.33	8.33	8.33

두 유형 모두 집안일을 총 가치 75의 4개 부분으로 나눌 수 있습니다.타입 A:

51, 12, 12
27.5, 27.5, 10, 10
27.5, 27.5, 10, 10
25, 10, 10, 10, 10, 10

타입 B:

51, 24
27.5, 27.5, 20
27.5, 27.5, 20
8.33 {9회}

4개의 에이전트가 모두 동일한 경우 임계값 75의 FFD가 4개의 최적 빈을 채웁니다.단, 타입 B의 에이전트가1개 있고 다른 에이전트가 타입 A의 에이전트가 있다고 가정합니다.그 후 첫 번째 라운드에서 타입 B의 에이전트는 번들51,24를 취득합니다(다른 에이전트는 값이 51,25이고 합계가 75를 초과하기 때문에 다른 에이전트는 번들51,25를 취득할 수 없습니다).다음 라운드에서 유형 A 에이전트에 대해 다음 번들이 채워집니다.

27.5, 27.5, 12 [합계는 67 - 10을 더 넣을 수 있는 공간이 없습니다]
27.5, 27.5, 12 [합계는 67 - 10을 더 넣을 수 있는 공간이 없습니다]
10, 10, 10, 10, 10, 10, 10, 10, 10 [합계는 70 - 10을 더 넣을 공간이 없습니다]

나머지 두 가지 집안일은 할당되지 않은 채로 남아있어요

보다 정교한 임계값 계산을 사용하면 최적값이 알려진 경우 각 에이전트에 대해 최대 11/9≈1.22의 최적값을 보장하고 최적값이 알려지지 않은 경우 최대 5/411.25의 최적값을 보장할 수 있다.

실장

Python: prtpy 패키지에는 멀티비트 구현이 포함되어 있습니다.

레퍼런스

^ ^a ^b ^c ^d Coffman, Jr., E. G.; Garey, M. R.; Johnson, D. S. (1978-02-01). "An Application of Bin-Packing to Multiprocessor Scheduling". SIAM Journal on Computing. 7 (1): 1–17. doi:10.1137/0207001. ISSN 0097-5397.
^ ^a ^b ^c Friesen, Donald K. (1984-02-01). "Tighter Bounds for the Multifit Processor Scheduling Algorithm". SIAM Journal on Computing. 13 (1): 170–181. doi:10.1137/0213013. ISSN 0097-5397.
^ ^a ^b Yue, Minyi (1990-12-01). "On the exact upper bound for the multifit processor scheduling algorithm". Annals of Operations Research. 24 (1): 233–259. doi:10.1007/BF02216826. ISSN 1572-9338. S2CID 120965788.
^ Cao, Feng (1995), Du, Ding-Zhu; Pardalos, Panos M. (eds.), "Determining the Performance Ratio of Algorithm Multifit for Scheduling", Minimax and Applications, Nonconvex Optimization and Its Applications, Boston, MA: Springer US, vol. 4, pp. 79–96, doi:10.1007/978-1-4613-3557-3_5, ISBN 978-1-4613-3557-3, retrieved 2021-08-23
^ ^a ^b ^c Huang, Xin; Lu, Pinyan (2021-07-18). "An Algorithmic Framework for Approximating Maximin Share Allocation of Chores". Proceedings of the 22nd ACM Conference on Economics and Computation. EC '21. New York, NY, USA: Association for Computing Machinery: 630–631. arXiv:1907.04505. doi:10.1145/3465456.3467555. ISBN 978-1-4503-8554-1. S2CID 195874333.
^ Burkard, R. E.; He, Y. (1998-09-01). "A note on MULTIFIT scheduling for uniform machines". Computing. 61 (3): 277–283. doi:10.1007/BF02684354. ISSN 1436-5057. S2CID 37590584.
^ Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (June 1982). "Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System". SIAM Journal on Algebraic and Discrete Methods. 3 (2): 190–196. doi:10.1137/0603019.

[:0-1] Coffman, Jr., E. G.; Garey, M. R.; Johnson, D. S. (1978-02-01). "An Application of Bin-Packing to Multiprocessor Scheduling". SIAM Journal on Computing. 7 (1): 1–17. doi:10.1137/0207001. ISSN 0097-5397.

[:1-2] Friesen, Donald K. (1984-02-01). "Tighter Bounds for the Multifit Processor Scheduling Algorithm". SIAM Journal on Computing. 13 (1): 170–181. doi:10.1137/0213013. ISSN 0097-5397.

[:2-3] Yue, Minyi (1990-12-01). "On the exact upper bound for the multifit processor scheduling algorithm". Annals of Operations Research. 24 (1): 233–259. doi:10.1007/BF02216826. ISSN 1572-9338. S2CID 120965788.

[4] Cao, Feng (1995), Du, Ding-Zhu; Pardalos, Panos M. (eds.), "Determining the Performance Ratio of Algorithm Multifit for Scheduling", Minimax and Applications, Nonconvex Optimization and Its Applications, Boston, MA: Springer US, vol. 4, pp. 79–96, doi:10.1007/978-1-4613-3557-3_5, ISBN 978-1-4613-3557-3, retrieved 2021-08-23

[:3-5] Huang, Xin; Lu, Pinyan (2021-07-18). "An Algorithmic Framework for Approximating Maximin Share Allocation of Chores". Proceedings of the 22nd ACM Conference on Economics and Computation. EC '21. New York, NY, USA: Association for Computing Machinery: 630–631. arXiv:1907.04505. doi:10.1145/3465456.3467555. ISBN 978-1-4503-8554-1. S2CID 195874333.

[6] Burkard, R. E.; He, Y. (1998-09-01). "A note on MULTIFIT scheduling for uniform machines". Computing. 61 (3): 277–283. doi:10.1007/BF02684354. ISSN 1436-5057. S2CID 37590584.

[:4-7] Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (June 1982). "Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System". SIAM Journal on Algebraic and Discrete Methods. 3 (2): 190–196. doi:10.1137/0603019.

[1]

[2]

[3]

[5]

[6]

[7]

Search