최장 처리 시간 우선 스케줄링

Longest-Processing-Time-First(LPT; 최장 처리 시간 우선)는 작업 스케줄링을 위한 까다로운 알고리즘입니다.알고리즘에 대한 입력은 작업 세트이며, 각 작업에는 특정 처리 시간이 있습니다.작업을 처리할 수 있는 시스템의 수를 지정하는 숫자 m도 있습니다.LPT 알고리즘은 다음과 같이 동작합니다.

처리 시간이 가장 긴 작업이 우선하도록 처리 시간의 내림차순으로 작업을 정렬합니다.
이 시퀀스의 각 작업을 현재 로드(= 예약된 작업의 총 처리 시간)가 가장 작은 시스템으로 예약합니다.

알고리즘의 스텝2는 기본적으로 List-Scheduling(LS; 리스트스케줄링) 알고리즘입니다.차이점은 LS는 임의의 순서로 작업을 루프하고 LPT는 내림차순 처리시간에 따라 작업을 사전 주문한다는 것입니다.

LPT는 1960년대에 Ronald Graham에 의해 동일한 기계 스케줄링 ^[1]문제의 맥락에서 처음 분석되었습니다.나중에, 그것은 문제의 다른 많은 변형에 적용되었다.

LPT는 멀티웨이 번호 분할 알고리즘으로서 보다 추상적인 방법으로 설명할 수도 있습니다.입력은 숫자의 집합 S와 양의 정수 m입니다.출력은 S를 m개의 서브셋으로 분할한 것입니다.LPT는 입력을 가장 큰 것부터 가장 작은 것까지 순서대로 정렬하여 지금까지의 합계가 가장 작은 부분에 넣습니다.

예

입력 집합이 S = {4, 5, 6, 7, 8}이고 m = 2인 경우 결과 파티션은 {8, 5, 4}, {7, 6}입니다.m = 3이면 결과 3방향 파티션은 {8}, {7, 4}, {6, 5}입니다.

특성.

LPT가 최적의 파티션을 찾지 못할 수 있습니다.예를 들어 위의 경우 최적 파티션 {8,7}, {6,5,4}은(는) 두 합계가 모두 15입니다.그러나 하위 최적성은 최악의 경우와 평균의 경우 모두 제한됩니다. 아래 성능 보증을 참조하십시오.

LPT 실행 시간은 정렬에 의해 좌우됩니다.이 정렬에는 O(n log n) 시간이 걸립니다.여기서 n은 입력 수입니다.

퍼포먼스 보증: 동일한 머신

동일한 머신의 스케줄링에 LPT를 사용하면 다음과 같은 근사 비율을 얻을 수 있습니다.

최악의 경우 최대 합계

최악의 경우, 욕심 많은 파티션의 최대 금액은 최적(^[2] $최소) 최대$ 금액의 ${\frac {4}{3}}$ 4 $.$ 3배입니다 ${\frac {4}{3}}$ .

증명

OPT=1이 되도록 입력 항목을 정규화합니다.이는 모든 항목의 합계가 최대 m임을 의미합니다.

항목을 큰 것(2/3 초과), 중간 것(1/3 ~ 2/3 사이) 및 작은 것(1/3 미만)으로 분할합니다.n, n_M, n이라고_S 합니다_L.각 최적 파티션에서 각 부품은 최대 하나의 큰 항목을 포함하므로_L n µ m입니다.또한 각 최적 부품은 큰 항목과 중간 항목 또는 세 개의 중간 항목을 모두 포함할 수 없으므로 n ≤ 2_M(m-n)이다_L.

그리디 알고리즘의 동작은, 다음의 3개의 국면으로 분할할 수 있습니다.

큰 항목 할당 - 각각 다른 통에 넣습니다.n µm 이므로_L 이 단계가 완료되면 각 빈에는 최대 1개의 항목이 포함되므로 최대합은 1이 됩니다.
중간 항목 할당.첫 번째 m-n은_L 빈 빈 빈칸에 들어가고 다음_L m-n은 같은 빈칸에 추가됩니다(있는 경우).n 2 2(m-n_L)이므로_M, 이 단계가 완료되면 각 빈에는 최대 1개의 큰 항목(합계) 또는 최대 2개의 중간 항목(합계)이 포함되며, 합계는 최대 4/3이다.
작은 아이템을 할당하다.각 항목은 가장 작은 금액으로 통에 추가됩니다.가장 작은 합은 기껏해야 평균 합이고, 기껏해야 1이다.따라서 작은 항목이 추가되면 새로운 합계는 최대 3분의 4가 된다.

보다 상세한 분석 결과, 4 ${\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}$ - ${\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}$ ${\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}$ m ${\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}$ ${\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}$ 3 - ${\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}$ ${\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}$ ${\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}$ $7/6\approx 1.167$ { $frac$ { $4 }$ = $flac { 4$ } { 3 $m$ } )의 ${\frac {4m-1}{3m}}={\frac {4}{3}}-{\frac {1}{3m}}$ 인수가 최적(최소) 최대 합계(^[1]^[3]예: m = 2 $7/6\approx 1.167$ 이 $7/$ 인 경우).

증명

이전의 증거는 두 가지 방법으로 다듬을 수 있다.

첫째, 모든 대형 및 중간 항목이 할당되면 각 빈의 합계가 최대 1이라는 것을 증명할 수 있다.

m-n_L 중형 아이템이 많아야 큰 아이템과 중간 아이템을 각각 별도의 통에 넣기 때문에 합계는 1이 됩니다.
그렇지 않은 경우, 첫 번째_L m-n 매체 항목을 상위 매체 항목별로, 나머지 m-n_L 항목(최대 m-n)을 하위 매체 항목별로 나타낸다.
먼저 항목 #m이 1/2보다 크다고 가정합니다.즉, #1, ..., #m 항목은 모두 1/2보다 크기 때문에 각각 다른 최적 부분에 있어야 합니다.각 하위 중간 항목(항목 #m+1,...)#n_M) 항목 #1, ..., #m 중 하나와 최적인 부품에 꼭 들어맞아야 한다.합계가 최대 1이면 일치할 수 있는 두 항목을 호출하여 같은 최적인 부품에 맞도록 하자.홀의 정리에 따르면, k개의 하위-중간 항목의 각 서브셋은 #1, ..., #m 항목의 k개 이상과 일치해야 한다.특히 항목 #m+1은 항목 #m과 일치해야 합니다.항목 #m+1 및 #m+2는 항목 #m-1과 일치해야 합니다.일반적으로 항목 #m+k는 항목 #'m-k+1과 일치해야 합니다.LPT는 항목 #m+k를 #'m-k+1과 같은 빈에 넣습니다.따라서 각 빈의 최대 합은 1입니다.

둘째, 작은 입력을 할당할 때 모든 새로운 빈의 합계가 최대 4/3-1/(3m)임을 증명할 수 있다.두 가지 경우가 있습니다.

현재 최소 합계가 최대 1-1/(3m)인 경우, 작은 입력 하나를 추가한 후 새 합계는 최대 1-1/(3m)+1/3 = 4/3-1/(3m)입니다.
그렇지 않으면 모든 합계가 1-1/(3m)보다 크므로 m-1의 가장 큰 빈의 합계는 m-1/3+1/(3m) = m-(4/3-1/(3m)보다 큽니다.모든 입력의 총합은 최대 m이므로 새로운 합계는 4/3-1/(3m) 미만이어야 합니다.

$4m$ ${\frac {4m-1}{3m}}$ $13m$

조임 예

2 $2m+1$ + $2m+1$ (여기서 $m$ 은 짝수) $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ 이 $2m+1$ 2 m $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ - $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ , $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ m - $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ , $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ m - $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ , $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ 2 $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ - $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ , $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ m - 2 $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ , $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ - $2m+1$ 2 $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ . m $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ - $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ , $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ + $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ m + 1 , $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ m , $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ , $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ m , $2m-1,2m-1,2m-2,2m-2,\ldots ,m+1,m+1,m,m,m$ , m , 1 \ $display style$ 2 m-1 , 2 $m-2$ , 2 $m-2$ , \ $ldots ,$ 2 m + $1$ , m + $m$ , 1 , 1 , m + m , m , 1 , 1 , m 1 .

$(\displaystyle 2m-1,m,m)$
$2m-1,m$
$2m-2,m+1$
$2m-2,m+1$ m - $2m-2,m+1$ , $2m-2,m+1$ + $2m-2,m+1$ ({ $displaystyle$ 2 $m-2$ , $m+1}$
...
$3m/2,3m/2-1$
$3m/2,3m/2-1$

최대 $4m-1$ $4m-1$ (\ $style 4m-1$ 이지만 최적의 파티션은 다음과 같습니다.

$m,m,m$
$2m-1,m+1$
$2m-1,m+1$
$(\displaystyle 2m-2,m+2)$
$(\displaystyle 2m-2,m+2)$
...
$3m/2,3m/2$

최대 $(디스플레이$ 스타일 $3m$ 입니다.

훨씬 더 상세한 분석은 최대합 부분의 입력 수를 고려합니다.

gready 파티션의 각 부분에서 j번째로 큰 숫자는 $OPT/j$ $(\displaystyle$ OPT/ $j$ ^[4]입니다.
최대합이 있는 탐욕 부분 P에 L 입력이 있다고 가정합니다.다음으로, 탐욕 알고리즘의 근사비는 ${\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}$ + ${\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}$ - ${\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}$ L ${\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}$ = ${\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}$ + ${\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}$ ${\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}$ - ${\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}$ L m ${\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}$ ({ $displaystyle {\frac$ { $Lm}}$ - {\ $frac$ {1} { $Lm$ } = 1 + ${\frac$ {1} ${Lm$ } ${\frac {L+1}{L}}-{\frac {1}{Lm}}=1+{\frac {1}{L}}-{\frac {1}{Lm}}$ ^[3] $=$ 1 + { $Lm}$ - {\ $frac {$ 1} {Lm $}$ 3 입니다.증명.^[4] P의 숫자를 x,x_L,x로 나타냅니다₁.x가 P에 삽입되기 전에는_L 그 합이 가장 작았습니다.따라서 부품당 평균 합계는 최소한 x+입니다₁.+x_L-1 + x_L/m최적 최대 합계는 적어도 평균 합계가 되어야 합니다.반면 욕심 많은 합은 x+이다₁.+x_L-1+x_L. 따라서 차이는 최대 (1-1/m)x_L, 즉 (1)은 최대 (1-1/m)*OPT/L입니다. 따라서 비율은 최대 (1 + 1/L - 1/Lm)입니다.

최악의 경우 최소 합계

최악의 경우 반환되는 파티션의 최소 합계는 최적( $최대)$ 최소 ^[5]합계의 최소 ${\frac {3}{4}}$ 입니다 ${\frac {3}{4}}$ .

증명

증거는 모순에 의한 것이다.우리는 최소한의 반례, 즉 가장 작은 m과 가장 적은 입력 번호를 가진 반례를 고려한다.P,......P로₁_m 그리디 파티션을 나타내고 Q,......Q로_m 최적₁ 파티션을 나타냅니다.최소 반례의 속성은 다음과 같습니다.

최적 파티션의 min-sum은 4이고, gready 파티션의 min-sum은 3보다 작습니다(이것은 정규화일 뿐이며, 일반성을 잃지 않습니다).
gready 파티션의 max-sum은 4를 초과합니다(두 파티션의 총합이 같고 최소 4m이기 때문입니다).
gready bin_i P에 대해 sum_i(P)3 3인 경우_i P는 최적의_j bin Q에 의해 지배되지 않습니다.증명: 만약_i P가 Q에_j 의해 지배된다면, 우리는 m을 m-1로 줄이고 P의 항목을_i 제거함으로써 더 작은 반례를 만들 수 있다.욕심 많은 파티션의 최소합은 3 미만입니다.최적 파티션에서는 P 내의_i 항목을 Q 내의_j 주요 항목으로 치환할 수 있으므로 최소 4개가 남는다.
gready bin_i P에 대해 sum_i(P)3 3이면 P에는_i 적어도2개의 숫자가 포함되어 있습니다.증명: P가 숫자 x를 하나만 포함할 경우_i, P는 x.givese를 포함하는_j 최적 빈 Q에 의해 지배되며, 일부 입력 x는 최소 3이며, 탐욕 알고리즘은 이를 일부_i P에 넣습니다.그러면 합계가 3보다 작은 번들이 있기 때문에, 탐욕 알고리즘은 이전의 조건과 모순되는 다른 입력을 P에_i 넣지 않습니다.
모든 그리디 빈_i P는 3/2보다 약하게 큰 입력을 최대 1개 포함합니다.증명: P를 이러한 입력 2개가 할당된 첫 번째 욕심 빈으로 합니다_i.입력은 내림차순으로 할당되므로 P는_i 두 개의 입력이 할당된 첫 번째 그리디 빈입니다.즉, 가장 큰 m+1 입력 중 가장 작은 두 개의 입력을 포함해야 합니다.또, 이 2개의 항목의 합계가 적어도 3/2+3=3이므로, P에는_i 다른 입력이 할당되지 않는다.한편 비둘기홀 원리에 따르면 가장 큰 m+1 입력 중 2개의 입력을 포함하는 최적의 빈_j Q가 존재해야 합니다.따라서_i P는 Q에 의해_j 지배됩니다.
그리디 알고리즘의 실행중에, 어느 하나의 빈의_i 합이 4를 넘기기 전에, 각 빈 P의 합은 적어도 8/3이 된다.증명: y가 일부 빈 P에_i 추가된 첫 번째 입력이라고 가정합니다. 이 입력은 합계를 4보다 크게 만듭니다.y가 더해지기 전에는 P의_i 합계가 가장 작았고, 이는 가정상 8/3보다 작았다. 즉 y>4/3임을 의미한다.T는 첫 번째 입력에서 y까지의 모든 입력 세트를 나타냅니다.이 모든 입력도 4/3보다 큽니다.P가 8/3보다 작았기 때문에_i T의 x가 정확히 1개 들어 있었습니다.따라서_i P에는 정확히 2개의 항목 {x,y}이(가) 포함되어 알고리즘이 종료될 때까지 이 2개의 항목이 남아 있습니다.첫 번째 항목부터 x까지의 항목 수를 m으로 하고, T의 항목을 두 가지 방법으로 세어 모순을 보여 줍니다.
- 먼저 n개의 최적 빈을 고려합니다.이러한 빈에 x 이상의 항목이 포함되어 있으면 T의 다른 항목은 포함할 수 없습니다. 그렇지 않으면 {x,y}이(가) 지배적이기 때문입니다.또한 이러한 빈은 T의 세 항목을 포함할 수 없습니다. 왜냐하면 두 항목의 합계가 8/3보다 크므로 x보다 크며, 세 번째 항목은 최소 y이므로 {x,y}을(를) 지배합니다.따라서 T의 항목 수는 최대 1*m + 2*(n-m) = 2n-m이다.
- 이제 n개의 욕심 많은 빈을 생각해 보겠습니다.x를 포함한 번들에 y를 더하면 합계가 가장 작은 번들이 됩니다.따라서 x보다 작은 T의 모든 원소는 적어도 하나의 다른 T 항목과 함께 욕심 많은 빈에 있어야 합니다.x와 y도 마찬가지입니다.따라서 T의 항목 수는 적어도 (m-1)+2*(n-m+1) = 2n-m+1 - 모순이다.
일반성의 손실 없이 모든 입력이 1/3보다 작거나 적어도 1이라고 가정할 수 있습니다.증명: 입력 x가 (1/3,1)에 있다고 가정합니다.x를 1로 바꿉니다.이것은 분명히 최적의 최소 합계를 감소시키지 않는다.우리는 그것이 욕심 많은 민섬을 바꾸지 않는다는 것을 보여준다.일부 탐욕 번들 P의_i 최종 합계가 4보다 크다는 것을 알고 있습니다.마지막 입력이 P에_i 추가되기 전에는 합계가 3보다 작았기 때문에_i 1보다 큰 입력이 추가되면 P가 4보다 커집니다.이전 조항에 따르면, 그 시점에서 다른 모든 탐욕 번들의 합계는 최소 8/3이었습니다.알고리즘은 그 후에 x에 도착합니다.알고리즘이 어떤 빈_j P에 x를 더하면 P의 합계는_j 적어도 8/3+1/3=3이 되므로 P에_j 더 이상의 항목이 추가되지 않는다.따라서_j P에는 크기가 [1/3,1]인 입력이 하나만 포함됩니다.x를 1로 치환해도 P에_j 삽입되어 합계가 3을 넘습니다.그래서 욕심 많은 민섬은 변하지 않는다.
입력은 작은(1/3 미만)과 큰(1 이상)으로 분할할 수 있습니다.P의_i 작은 항목 집합은 S로 표시됩니다_i.알고리즘이 작은 항목의 처리를 시작하면 모든 번들의 합계는 8/3 이상이 됩니다.

최소한의 반례가 존재하지 않는다는 증거는 가중치 체계를 사용한다.각 입력 x에는 크기와 그리디 번들_i P에 따라 w(x)가 할당됩니다.

x가 큰 항목인 경우:
- x가 P의 단일_i 큰 항목이면 w(x)=8/3이다.
- 만약_i P가 정확히 두 개의 항목 {x,y}을 포함하고 둘 다 크고 x>y와 sum(P_i)≥3이면 w(x)=8/3이다.
- 그렇지 않으면 w(x)=4/3 입니다.
x가 작은 항목인 경우:
- sum(P_i)33이면 w(x) = 4x/(3sum(S_i))이다. 따라서_i w(S) = 4/3이다.
- sum(P_i)<3이면 w(x) = 2x/(3sum(S_i)), 즉 w(S_i) = 2/3이다.

이 가중치 방식에는 다음 속성이 있습니다.

x22이면 w(x)=8/3이다.증명: x는 크다.P에_i 있다고 가정합니다.P에 다른 큰 아이템 y가 포함되어 있으면_i x+y33이므로 P에는_i 다른 아이템이 없습니다.게다가 x>y는 3/2보다 큰 항목이 1개까지 있기 때문입니다.그래서 w(x)=8/3이다.
x <1/3인 경우 w(x) > 2x. 증명: x가 작습니다.P에_i 있다고 가정합니다.
- sum_i(P)3 3이면 x가 더해지기 전에는 sum(P_i)이 3보다 작았기 때문에 현재는 10/3보다 작습니다.그러나 알고리즘이 작은 항목을 처리하기 시작했을 때 합(P_i)은 최소 8/3이었습니다.즉, sum(S_i) < 2/3이므로 w(x) = 4x/(3sum(S_i)) > 2x가 됩니다.
- sum(P_i)<3이면 sum(S_i)< 3-8/3=1/3이므로 w(x)=2x/(3sum(S_i)>2x입니다.
모든 욕심 빈_i P의 무게는 최대 4이고, 욕심 빈 하나 이상의 무게는 최대 10/3입니다.실증:
- P의_i 모든 입력이 크면 가중치가 8/3인 단일 입력, 가중치가 8/3+4/3인 두 입력 또는 가중치가 4/3+4/3인 세 개의 입력이 포함됩니다.
- P의_i 일부 입력이 작을 경우 총 무게는 최대 4/3입니다.최대 2개의 큰 입력이 있으며, 이들의 가중치는 8/3 또는 4/3+4/3이다.
- 마지막으로, 합계가 3보다 작은 그리디 빈의 무게는 최대 8/3(큰 입력만 있는 경우) 또는 10/3(작은 입력만 있는 경우)입니다.
각 최적 빈 Q의_j 무게는 최소 4입니다.실증:
- Q가 작은 항목만 포함하는 경우_j 각 항목은 w(x) > 2x를 충족하므로 w(Q_j) > 2sum(Q_j) 8 8이 됩니다.
- Q에 큰 항목 x가 정확히 1개 포함되어 있는 경우_j 합계가 4-x 이상이고 무게가 8-2x 이상인 작은 항목을 포함해야 합니다.x<2 및 소품 중량은 8~4=4 이상, 또는 xin(2,3) 및 w(x)=8/3 이상, 소품 중량은 8~6=2 이상이다.두 경우 모두 총 중량은 최소 4입니다.
- Q에 x > y 및 x 22가 정확히2개의 큰 항목이 포함되어 있다면 적어도_j 8/3+4/3=4가 있습니다.x+y10 10/3이면 작은 항목의 합계가 2/3 이상이어야 하므로 총 중량은 4/3+4/3+2/3=4 이상이어야 한다.그렇지 않으면 x>5/3 입니다.그래서 x는 욕심 많은_m 빈 P의 첫 번째 입력입니다.z가 P에 추가된_m 두 번째 입력이라고 합니다.x+z33이면 P에_m 더 이상 입력이 없으므로 w(x)=8/3이면 끝입니다.그 이외의 경우는 x+z<3 입니다.v가 합계가 4를 초과하는 gready bin에서 가장 작은 입력이라고 가정합니다.x<8/3이므로 z는 v보다 먼저 처리되어야 하므로 zvv.이제 Q의 작은_j 항목 t가 욕심 많은 빈_i P에 있다고 가정합니다.
  - sum(P_i)<3인 경우, v가 P에 포함되지_i 않았다는 것은 v > 4-sum(large-items-in-P_i) > 1+sum(small-items-in-P_i)임을 의미합니다.따라서 1+sum(S_i)+x < v+x z z+x < 3 및 sum(S_i)< 2-x 입니다.즉, 2*sum(S_i) <4-2x 44-x-y sumsum(small-items-in-Q_j)입니다.따라서 w(t) = 2t/(3sum(S_i)) > 4t/(3sum(small-items-in-Q_j))입니다.
  - sum(P_i)≥3, sum(S_i)11이면 w(t)=4/3이면 끝이다.t를 더하기 전에 합(P_i)이 3보다 작았으므로 합(P_i)<3+sum(S_i)/2이다.v가 P에 포함되지_i 않았다는 것은 v > 4-sum(대항목-in-P_i) > 1+sum(small-items-in-P_i)/2임을 의미합니다.전 항과 마찬가지로 w(t) > 4t/(3sum(small-items-in-Q_j))입니다.
  - 따라서 Q의_j 모든 작은 항목의 총 중량은 4/3 이상이므로 Q의 총_j 중량은 4/3+10/3 이상이다.
- Q에 정확히 3개 이상의 큰 항목이 포함되어 있는 경우_j, Q의 총 중량은 4/3+4/3+4=4 이상이어야 한다.
전자는 모든 입력의 무게가 최대 4m-2/3이고 후자는 모든 입력의 무게가 최소 4m임을 의미하기 때문에 마지막 두 주장은 모순된다.그러므로 반례가 존재하지 않는다.

보다 정교한 분석 결과, 이 ${\frac {3m-1}{4m-2}}$ 은 $($ 예를 들어 m $=2$ 인 경우 5/^[6]^[7]6)인 것으로 나타났다.꽉 ^[5]조여요.

조임 예

3m-1 입력이 있다고 가정합니다(여기서 m은 짝수입니다).첫 번째 2m 입력은 2m-1, 2m-1, 2m-2, 2m-2, ..., m, m입니다.마지막 m-1 입력은 모두 m입니다.다음으로 그리디 알고리즘은 다음과 같이 반환됩니다.

2m-1, m, m
2m-1, m, m
2m-2, m+1, m
2m-2, m+1, m
...
3 m/2, 3 m/2-1, m
3 m/2, 3 m/2-1

최소 3m-1.그러나 최적의 파티션은 다음과 같습니다.

2m-1, 2m-1
2m-2, m, m
2m-2, m, m
2m-3, m+1, m
2m-3, m+1, m
...
3 m/2, 3 m/2-2, m
3 m/2, 3 m/2-2, m
3 m/2-1, 3 m/2-1, m

최소 4m-2.

LPT의 변형인 Restricted-LPT 또는 ^[8]RLPT는 입력이 등급이라고 불리는 크기 m의 서브셋으로 분할된다(1위는 가장 큰 m 입력을 포함, 2위는 다음으로 큰 m 입력을 포함).각 순위의 입력은 m개의 서로 다른 빈에 할당되어야 합니다. 즉, 1등급이 먼저 지정된 다음 2등급이 지정됩니다.RLPT의 최소합계는 기껏해야 LPT의 최소합계이다.최소 합계를 최대화하기 위한 RLPT의 근사 비율은 최대 m이다.

평균 케이스 최대 합계

평균적인 경우 [0,1]에서 입력 번호가 균일하게 분포되어 있다면 LPT 스케줄에서 가장 큰 합계는 다음 특성을 만족한다.

m=2 머신의 예상 최대 합계는 ${\frac {n}{4}}+{\frac {1}{4n+4}}$ ${\frac {n}{4}}+{\frac {1}{4n+4}}$ + ${\frac {n}{4}}+{\frac {1}{4n+4}}$ ${\frac {n}{4}}+{\frac {1}{4n+4}}$ {\ $frac$ {n} + {\ $frac {1}$ ${4n+4$ ${\frac {n}{4}}+{\frac {e}{2n+2}}$ 이고 ${\frac {n}{4}}+{\frac {1}{4n+4}}$ ${\frac {n}{4}}+{\frac {e}{2n+2}}$ ${\frac {n}{4}}+{\frac {e}{2n+2}}$ ${\frac {n}{4}}+{\frac {e}{2n+2}}$ ${\frac {n}{4}}+{\frac {e}{2n+2}}$ ${\frac {n}{4}}+{\frac {e}{2n+2}}$ { $displaystyle {n}$ + {\ $frac {e}$ { $n+2}$ 입니다. 여기서 n은 입력 ^[9]번호입니다.
최대 합계는 최대 1 $1+O(\log {\log {n}}/n)$ + $1+O(\log {\log {n}}/n)$ ( $log$ ${\$ n / n ) ( \ $displaystyle$ 1 + $O ($ \ log { $n }$ / $n$ ) 。 $1+O(1/n)$ 는 $1+O(1/n)$ 1 + $1+O(1/n)$ ( $1+O(1/n)$ / $1+O(1/n)$ n $1+O(1/n)$ ) ( \ $displaystyle$ 1 + $O$ ( $1$ / $n )$ 입니다 $1+O(1/n)$ . $n$ 서 $n$ 은 $n$ ^[10]입력 수입니다.
LPT 최대합계와 최적 최대합계의 차이는 $O(\log {n}/n)$ 확실하게 O $O(\log {n}/n)$ n / $)$ { $displaystyle$ O $(\log {n}/n)}($ 균일한 분포 또는 음의 지수 분포의 경우)이고, $O(m^{2}/n)$ O $O(m^{2}/n)$ 2 / $)$ { $display style$ O $(m^{2}/n})}($ 균일한 분포의 경우)입니다 $O(\log {n}/n)$ $O(m^{2}/n)$ .이러한 결과는 속도가 ^[11]다른 머신에서도 유효합니다.

일반적인 목적

C(i가 1과 m 사이인 경우)를 주어진 파티션에서 부분 집합 i의 합으로 합니다_i.목적함수 max(C_i)를 최소화하는 대신 목적함수 max(f(C_i))를 최소화할 수 있습니다. 여기서 f는 고정함수입니다.마찬가지로 목적함수합(f(C_i))을 최소화할 수 있다.Alon, Azar, Woeginger 및 Yadid는^[12] f가 다음 두 조건을 만족하는 경우 다음을 증명한다.

조건 F*라고 하는 강력한 연속성 조건은 0마다 존재하며, y-x <'x'이면 f(y)-f(x) <'f(x)'이면 f(x(x)가 됩니다.
볼록.

그러면 LPT 규칙은 합(f_i(C))을 최소화하기 위한 유한 근사 비율을 가집니다.

다른 설정에 대한 적응

LPT는 동일한 머신 스케줄링의 단순한 경우 외에도 보다 일반적인 설정에 맞게 조정되었습니다.

균일한 기계

균일한 머신 스케줄링에서는 머신마다 속도가 다를 수 있습니다.LPT 규칙은 각 작업을 완료 시간이 가장 빠른 머신에 할당합니다(즉, LPT는 이 머신이 다른 모든 ^[13]머신보다 더 빨리 작업을 완료할 수 있을 정도로 빠를 경우 현재 부하가 큰 머신에 작업을 할당할 수 있습니다).

Gonzalez, Ibarra 및 Sahni는^[13] m개의 균일한 기계에서 LPT의 근사비가 $2m/(m+1)$ $2m/(m+1)$ / ( $2m/(m+1)$ + $2m/(m+1)$ ) $2m/(m+1)$ (\ $displaystyle 2m$ / ( $m$ + $1)$ 임을 나타냅니다 $2m/(m+1)$ 꽉 끼지는 않지만 m이 무한대에 가까워질 때 1.5의 점근 하한이 있습니다.m=2 기계의 특수한 경우, 근사비는 $(1+{\sqrt {17}})/4\approx 1.281$ $(1+{\sqrt {17}})/4\approx 1.281$ + $(1+{\sqrt {17}})/4\approx 1.281$ ) / 4 $(1+{\sqrt {17}})/4\approx 1.281$ 1. $(1+{\sqrt {17}})/4\approx 1.281$ ${displaystyle (1+{\displayrt {17})$ / 4 $\약$ 1. $281}$ 이며 $(1+{\sqrt {17}})/4\approx 1.281$ , 촘촘하다.
Mireault, Orlin 및 Vohra는^[14] 두 대의 기계를 사용하여 하나의 기계가 다른 기계보다 q배 더 빠른 설정을 연구합니다.LPT의 근사 비율을 q의 함수로 계산합니다.q=1이면 결과는 동일한 기계에 대해 알려진 7/6 요인과 일치합니다.
Koulams와 Kyparis는^[15] LPT의 수정을 제시하는데, LPT 규칙에 따라 최장 3개의 작업이 최적으로 스케줄 되고 나머지 작업은 스케줄 된다.2대의 기계의 근사비는 ${\sqrt {1.5}}\approx 1.2247$ .5 ${\sqrt {1.5}}\approx 1.2247$ .2247 $(displaystyle)$ 로, 약 1. $2247($ 약 1. $2247$ 입니다 ${\sqrt {1.5}}\approx 1.2247$ .

카디널리티 제약

균형 파티션 문제에서는 각 시스템에 할당할 수 있는 작업 수에 제한이 있습니다.간단한 제약사항은 각 시스템이 대부분의 c 작업을 처리할 수 있다는 것입니다.LPT 규칙은 c개 미만의 작업 중에서 부하가 가장 작은 시스템에 각 작업을 할당합니다.이 규칙을 수정 LPT 또는 MLPT라고 합니다.

Kelerer와 Woeginger는^[16] 최대 3*m의 작업이 있는 변종을 연구하며, 각 머신에는 최대 3개의 작업이 포함되어야 합니다(이것은 3 파티션 문제의 일반화라고 볼 수 있습니다).MLPT는 최대 $(4m-1)/(3m)$ ( $(4m-1)/(3m)$ m - $(4m-1)/(3m)$ ) $(4m-1)/(3m)$ / ( $(4m-1)/(3m)$ m $){$ $displaystyle ($ 4 m-1) / (3 m $)}$ 의 $(4m-1)/(3m)$ 최소 합계에 도달합니다.이것은 LPT가 제약되지 않은 문제에 대해 취득하는 근사비와 동일합니다.MLPT에 대한 경계가 엄격합니다.MLPT는 보다 일반적인 카디널리티 제약(c>3)에 대해 같은 근사비를 갖는 것으로 추측된다^[17].현재 일반적인 c>3에 대한 MLPT의 근사비는 최대 ^[18]2인 것으로 알려져 있습니다.
Chen, He 및^[19] Lin은 같은 문제에 대해 MLPT가 최소 $(3m-1)/(4m-2)$ ( $(3m-1)/(4m-2)$ - $(3m-1)/(4m-2)$ ) $(3m-1)/(4m-2)$ / ( $(3m-1)/(4m-2)$ $(3m-1)/(4m-2)$ 2) $(3m-1)/(4m-2)$ ({ $displaystyle (3m-1)$ / ( $4m-2)}$ 의 $(3m-1)/(4m-2)$ 최소 합계에 도달한다는 것을 나타냅니다.이것은 LPT가 제약 없는 문제에 대해 얻는 비율과 동일합니다.

또 다른 제약사항은 모든 기계에서 작업 수가 $/m$ (\ $displaystyle n/$ m $n/m$ )으로 올림 또는 내림해야 한다는 것입니다.제한 LPT 또는 RLPT라고 하는 LPT의 적응에서 입력은 쌍으로 할당된다(m=2 기계의 ^[9]경우).결과적으로 생성되는 파티션은 설계에 따라 균형 조정됩니다.

Coffman, Frederickson 및 Lueker는^[9] 입력이 균일하게 분포된 랜덤 변수일 때 예상되는 RLPT의 최대 합계가 ${\frac {n}{4}}+{\frac {1}{2n+2}}$ ${\frac {n}{4}}+{\frac {1}{2n+2}}$ 4 ${\frac {n}{4}}+{\frac {1}{2n+2}}$ + ${\frac {n}{4}}+{\frac {1}{2n+2}}$ 2 ${\frac {n}{4}}+{\frac {1}{2n+2}}$ + ${\frac {n}{4}}+{\frac {1}{2n+2}}$ { $style$ { $frac$ { n } + { \ $frac$ { ${\frac {n}{4}}+{\frac {1}{2n+2}}$ 1 ${\frac {n}{4}}+{\frac {1}{2n+2}}$ } { $2$ n + 2 ${\frac {n}{4}}+{\frac {1}{2n+2}}$ 임을 보여줍니다.최대값과 최소값의 예상 차이는 $\Theta (1/n)$ ( $\Theta (1/n)$ / $\Theta (1/n)$ ) { $displaystyle \Theta (1/$ n $\Theta (1/n)$ ^[20] 입니다.

커널 제약 - 비동시 가용성

커널 파티셔닝 문제에는 커널이라고 하는 사전 지정된 작업이 몇 개 있으며 각 커널은 고유한 시스템으로 예약되어야 합니다.다른 시간에 머신을 사용할 수 있는 경우의 스케줄링도 이에 해당합니다.각 머신의 i는 어느 시점_i t≤ 0(시간_i t는 커널 작업의 길이로 간주할 수 있습니다).

SLPT라고 ^[21]불리는 단순한 경험적 알고리즘은 각 커널을 다른 서브셋에 할당하고 LPT 알고리즘을 실행합니다.

Lee는^[22] 이 휴리스틱이 최소 금액으로 $3m-12m의 정확$ 한 ${\frac {3m-1}{2m}}$ 근사 비율을 ${\frac {3m-1}{2m}}$ 있음을 증명했다 $.$ 그런 다음 두 번째 단계에서 LPT의 수정 버전을 실행할 것을 제안하고 LPT가 근사 ${\frac {4}{3}}$ $(\$ 에 도달했음을 증명합니다.
Lin, Yao 및 He는^[23] 이 휴리스틱이 $\display\frac {2m-1}{3m-2$ })의 ${\frac {2m-1}{3m-2}}$ 정확한 근사 ${\frac {2m-1}{3m-2}}$ 을 가지고 있다는 것을 증명했다.
Shen, Wang 및^[24] Wang은 이 설정에 대해 서로 다른 목적 함수를 연구하고 다항식 시간 알고리즘을 제시한다.

온라인 설정

대부분의 경우 입력이 온라인 상태가 되어 그 사이즈는 도착한 후에야 알 수 있습니다.이 경우 미리 정렬할 수 없습니다.목록 스케줄링은 목록을 정렬할 필요가 없는 임의의 순서로 가져오는 유사한 알고리즘입니다.근사비는 $=$ }}= $2-{\frac {1}{m$ 입니다.

LPT를 온라인 환경에 보다 정교하게 적응시키면 대략 3/^[25]2의 비율을 얻을 수 있다.

실장

Python: 번호 파티셔닝 패키지와 prtpy 패키지에 LPT("greedy")가 구현되어 있습니다.

「」를 참조해 주세요.

그리디 넘버 파티셔닝 - 멀티웨이 넘버 파티셔닝 문제에 대한 LPT의 일반화 및 확장.

레퍼런스

^ ^a ^b Graham, R. L. (March 1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. CiteSeerX 10.1.1.90.8131. doi:10.1137/0117039. JSTOR 2099572. NAID 30006801878 ProQuest 917998761.
^ Xiao, Xin (2017-04-01). "A Direct Proof of the 4/3 Bound of LPT Scheduling Rule". Proceedings of FMSMT 2017. Atlantis Press: 486–489. doi:10.2991/fmsmt-17.2017.102. ISBN 978-94-6252-331-9.
^ ^a ^b Coffman, E. G.; Sethi, Ravi (1976-03-29). "A generalized bound on LPT sequencing". Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation. SIGMETRICS '76. New York, NY, USA: Association for Computing Machinery: 306–310. doi:10.1145/800200.806205. ISBN 978-1-4503-7497-2.
^ ^a ^b Chen, Bo (1993-10-01). "A note on LPT scheduling". Operations Research Letters. 14 (3): 139–142. doi:10.1016/0167-6377(93)90024-B. ISSN 0167-6377.
^ ^a ^b 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.
^ Csirik, János; Kellerer, Hans; Woeginger, Gerhard (June 1992). "The exact LPT-bound for maximizing the minimum completion time". Operations Research Letters. 11 (5): 281–287. doi:10.1016/0167-6377(92)90004-M.
^ Wu, Bang Ye (December 2005). "An analysis of the LPT algorithm for the max–min and the min–ratio partition problems". Theoretical Computer Science. 349 (3): 407–419. doi:10.1016/j.tcs.2005.08.032.
^ Walter, Rico (2013-01-01). "Comparing the minimum completion times of two longest-first scheduling-heuristics". Central European Journal of Operations Research. 21 (1): 125–139. doi:10.1007/s10100-011-0217-4. ISSN 1613-9178.
^ ^a ^b ^c Coffman, E. G.; Frederickson, G. N.; Lueker, G. S. (1984-05-01). "A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors". Mathematics of Operations Research. 9 (2): 260–266. doi:10.1287/moor.9.2.260. ISSN 0364-765X.
^ Frenk, J.B.G.; Kan, A.H.G.Rinnooy (June 1986). "The rate of convergence to optimality of the LPT rule". Discrete Applied Mathematics. 14 (2): 187–197. doi:10.1016/0166-218X(86)90060-0. hdl:1765/11698.
^ Frenk, J. B. G.; Rinnooy Kan, A. H. G. (1987-05-01). "The Asymptotic Optimality of the LPT Rule". Mathematics of Operations Research. 12 (2): 241–254. doi:10.1287/moor.12.2.241. ISSN 0364-765X.
^ Alon, Noga; Azar, Yossi; Woeginger, Gerhard J.; Yadid, Tal (1998). "Approximation schemes for scheduling on parallel machines". Journal of Scheduling. 1 (1): 55–66. doi:10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J. ISSN 1099-1425.
^ ^a ^b Gonzalez, Teofilo; Ibarra, Oscar H.; Sahni, Sartaj (1977-03-01). "Bounds for LPT Schedules on Uniform Processors". SIAM Journal on Computing. 6 (1): 155–166. doi:10.1137/0206013. ISSN 0097-5397.
^ Mireault, Paul; Orlin, James B.; Vohra, Rakesh V. (1997-02-01). "A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines". Operations Research. 45 (1): 116–125. doi:10.1287/opre.45.1.116. ISSN 0030-364X.
^ Koulamas, Christos; Kyparisis, George J. (2009-07-01). "A modified LPT algorithm for the two uniform parallel machine makespan minimization problem". European Journal of Operational Research. 196 (1): 61–68. doi:10.1016/j.ejor.2008.02.008. ISSN 0377-2217.
^ Kellerer, Hans; Woeginger, Gerhard (1993-09-07). "A tight bound for 3-partitioning". Discrete Applied Mathematics. 45 (3): 249–259. doi:10.1016/0166-218X(93)90013-E. ISSN 0166-218X.
^ Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "The m-partitioning problem". Mathematical Methods of Operations Research. 47 (1): 59–82. doi:10.1007/BF01193837. ISSN 1432-5217.
^ Dell'Amico, Mauro; Martello, Silvano (2001). "Bounds for the cardinality constrained P∥Cmax problem". Journal of Scheduling. 4 (3): 123–138. doi:10.1002/jos.68. ISSN 1099-1425.
^ Chen, Shi Ping; He, Yong; Lin, Guohui (2002-03-01). "3-Partitioning Problems for Maximizing the Minimum Load". Journal of Combinatorial Optimization. 6 (1): 67–80. doi:10.1023/A:1013370208101. ISSN 1573-2886.
^ Tsai, Li-Hui (1992-02-01). "Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling". SIAM Journal on Computing. 21 (1): 59–64. doi:10.1137/0221007. ISSN 0097-5397.
^ Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). "Three-partitioning containing kernels: Complexity and heuristic". Computing. 57 (3): 255–271. doi:10.1007/BF02247409. ISSN 1436-5057.
^ Lee, Chung-Yee (1991-01-07). "Parallel machines scheduling with nonsimultaneous machine available time". Discrete Applied Mathematics. 30 (1): 53–61. doi:10.1016/0166-218X(91)90013-M. ISSN 0166-218X.
^ Lin, Guo-Hui; Yao, En-Yu; He, Yong (1998-03-01). "Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times". Operations Research Letters. 22 (2): 75–81. doi:10.1016/S0167-6377(97)00053-9. ISSN 0167-6377.
^ Shen, Lixin; Wang, Dan; Wang, Xiao-Yuan (2013-04-01). "Parallel-machine scheduling with non-simultaneous machine available time". Applied Mathematical Modelling. 37 (7): 5227–5232. doi:10.1016/j.apm.2012.09.053. ISSN 0307-904X.
^ Chen, Bo; Vestjens, Arjen P. A. (1 November 1997). "Scheduling on identical machines: How good is LPT in an on-line setting?". Operations Research Letters. 21 (4): 165–169. doi:10.1016/S0167-6377(97)00040-0.

[Graham19692-1] Graham, R. L. (March 1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. CiteSeerX 10.1.1.90.8131. doi:10.1137/0117039. JSTOR 2099572. NAID 30006801878 ProQuest 917998761.

[2] Xiao, Xin (2017-04-01). "A Direct Proof of the 4/3 Bound of LPT Scheduling Rule". Proceedings of FMSMT 2017. Atlantis Press: 486–489. doi:10.2991/fmsmt-17.2017.102. ISBN 978-94-6252-331-9.

[:2-3] Coffman, E. G.; Sethi, Ravi (1976-03-29). "A generalized bound on LPT sequencing". Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation. SIGMETRICS '76. New York, NY, USA: Association for Computing Machinery: 306–310. doi:10.1145/800200.806205. ISBN 978-1-4503-7497-2.

[:1-4] Chen, Bo (1993-10-01). "A note on LPT scheduling". Operations Research Letters. 14 (3): 139–142. doi:10.1016/0167-6377(93)90024-B. ISSN 0167-6377.

[:4-5] 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.

[6] Csirik, János; Kellerer, Hans; Woeginger, Gerhard (June 1992). "The exact LPT-bound for maximizing the minimum completion time". Operations Research Letters. 11 (5): 281–287. doi:10.1016/0167-6377(92)90004-M.

[7] Wu, Bang Ye (December 2005). "An analysis of the LPT algorithm for the max–min and the min–ratio partition problems". Theoretical Computer Science. 349 (3): 407–419. doi:10.1016/j.tcs.2005.08.032.

[8] Walter, Rico (2013-01-01). "Comparing the minimum completion times of two longest-first scheduling-heuristics". Central European Journal of Operations Research. 21 (1): 125–139. doi:10.1007/s10100-011-0217-4. ISSN 1613-9178.

[:3-9] Coffman, E. G.; Frederickson, G. N.; Lueker, G. S. (1984-05-01). "A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors". Mathematics of Operations Research. 9 (2): 260–266. doi:10.1287/moor.9.2.260. ISSN 0364-765X.

[10] Frenk, J.B.G.; Kan, A.H.G.Rinnooy (June 1986). "The rate of convergence to optimality of the LPT rule". Discrete Applied Mathematics. 14 (2): 187–197. doi:10.1016/0166-218X(86)90060-0. hdl:1765/11698.

[:5-11] Frenk, J. B. G.; Rinnooy Kan, A. H. G. (1987-05-01). "The Asymptotic Optimality of the LPT Rule". Mathematics of Operations Research. 12 (2): 241–254. doi:10.1287/moor.12.2.241. ISSN 0364-765X.

[:12-12] Alon, Noga; Azar, Yossi; Woeginger, Gerhard J.; Yadid, Tal (1998). "Approximation schemes for scheduling on parallel machines". Journal of Scheduling. 1 (1): 55–66. doi:10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J. ISSN 1099-1425.

[:0-13] Gonzalez, Teofilo; Ibarra, Oscar H.; Sahni, Sartaj (1977-03-01). "Bounds for LPT Schedules on Uniform Processors". SIAM Journal on Computing. 6 (1): 155–166. doi:10.1137/0206013. ISSN 0097-5397.

[14] Mireault, Paul; Orlin, James B.; Vohra, Rakesh V. (1997-02-01). "A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines". Operations Research. 45 (1): 116–125. doi:10.1287/opre.45.1.116. ISSN 0030-364X.

[15] Koulamas, Christos; Kyparisis, George J. (2009-07-01). "A modified LPT algorithm for the two uniform parallel machine makespan minimization problem". European Journal of Operational Research. 196 (1): 61–68. doi:10.1016/j.ejor.2008.02.008. ISSN 0377-2217.

[16] Kellerer, Hans; Woeginger, Gerhard (1993-09-07). "A tight bound for 3-partitioning". Discrete Applied Mathematics. 45 (3): 249–259. doi:10.1016/0166-218X(93)90013-E. ISSN 0166-218X.

[:42-17] Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "The m-partitioning problem". Mathematical Methods of Operations Research. 47 (1): 59–82. doi:10.1007/BF01193837. ISSN 1432-5217.

[:9-18] Dell'Amico, Mauro; Martello, Silvano (2001). "Bounds for the cardinality constrained P∥Cmax problem". Journal of Scheduling. 4 (3): 123–138. doi:10.1002/jos.68. ISSN 1099-1425.

[19] Chen, Shi Ping; He, Yong; Lin, Guohui (2002-03-01). "3-Partitioning Problems for Maximizing the Minimum Load". Journal of Combinatorial Optimization. 6 (1): 67–80. doi:10.1023/A:1013370208101. ISSN 1573-2886.

[:52-20] Tsai, Li-Hui (1992-02-01). "Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling". SIAM Journal on Computing. 21 (1): 59–64. doi:10.1137/0221007. ISSN 0097-5397.

[21] Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). "Three-partitioning containing kernels: Complexity and heuristic". Computing. 57 (3): 255–271. doi:10.1007/BF02247409. ISSN 1436-5057.

[22] Lee, Chung-Yee (1991-01-07). "Parallel machines scheduling with nonsimultaneous machine available time". Discrete Applied Mathematics. 30 (1): 53–61. doi:10.1016/0166-218X(91)90013-M. ISSN 0166-218X.

[23] Lin, Guo-Hui; Yao, En-Yu; He, Yong (1998-03-01). "Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times". Operations Research Letters. 22 (2): 75–81. doi:10.1016/S0167-6377(97)00053-9. ISSN 0167-6377.

[24] Shen, Lixin; Wang, Dan; Wang, Xiao-Yuan (2013-04-01). "Parallel-machine scheduling with non-simultaneous machine available time". Applied Mathematical Modelling. 37 (7): 5227–5232. doi:10.1016/j.apm.2012.09.053. ISSN 0307-904X.

[25] Chen, Bo; Vestjens, Arjen P. A. (1 November 1997). "Scheduling on identical machines: How good is LPT in an on-line setting?". Operations Research Letters. 21 (4): 165–169. doi:10.1016/S0167-6377(97)00040-0.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

Search

최장 처리 시간 우선 스케줄링

네임스페이스

더

목차

예

특성.