LPT
, n , L t i, i=1,,L. NP- . LPT (longest-processing task first) - ), . . BellLaboratories , 1967. :
.
LPT
L
={Zi} n
i=1
: T £ (4/3-1/3n)*T0,
- LPT,
T0- .
,
T0 ≥
.
1. ?
1.1 , .
1.2 .
1.3 .
2. ?
2.1 .
2.2 .
2.3 .
3. ?
3.1 q.
3.2 q.
3.3 q.
4. q
4.1 q = max{max ti, }
4.2 q = max ti
4.3 q = min{max ti, }
5. ?
5.1 / .
5.2 .
5.3 .
6. LPT?
6.1 .
6.2 .
6.3 1 .
7. LPT?
7.1 .
|
|
7.2 .
7.3 , .
8. LPT?
8.1 T0 =
8.2 T0 £ max{max ti, }
8.3 T0 = 1/n * min {ti}
9. ?
9.1 / .
9.2 , .
9.3 .
10. LPT ?
10.1 , .
10.2 .
10.3 .