0000120

Chodzi o to. oby zminimalizować. przez wybór odpowiodniogo przy. dziełu u°. noJwiękezy koszt Jednoetkowy. Woźmy no przykłod oy-tuocjv gdy momy wykonoć m różnych proc rozpoczynaJocych eię jednocześnie. Czoo trwonię całej oporocji okroiło proco wykonywano najdłużej. Dysponując n pracownikami noloży tok przydzio-llć im proce, oby zminimalizować czoo trwania całej oporocji. Wartość k(u) okroiło czoo wykonywania pracy b6D przoz pracownika a£ A. gdy *a.b.u> € P w grafie możliwości przydziału C •

■ <AC*B,U,P> . Sytuację tę przedstawia rye.14.14.

14.4.1. Algoryta przydziału optymalnego minioax

© Zakładajęc, że w toblicy [^ktmiin *»8*V®tkie oczko e« do -puszczolno, wyznaczamy najlicznieJozy zbiór niezależnych oczok dopuszczalnych o licznoicl r ■ min (m,n).

(© wśród wybranych oczok wyznaczomy najwlękozę wartość k^. ■ M 1 w tablicy    akroilaoiy •łszyotkio oczka o wartości

równej i śriękozej od tej Wartości dyskryminującej. Zapamiętujemy wartość dyokryminujęcę 1 jako oczka dopusz -czelne przyjmujemy oczka nieokreślone.

©) W zbiorze oczok dopuszczalnych wyznaczamy ponownie najliczniejszy zbiór oczok niezdolnych. Dożęli liczność tego zbioru jest równa r, to przechodzimy do punktu (^) . W przeciwnym przypadku poprzedni przydziel był optymalny.

Przykład 14.4

Wyznaczymy przydział optymalny za pomocę przedetawlonego algorytmu, przy tablicy fk.,,1,.*. przedstawionej na rye.14.15.

(y.? (o.    K

	8	7	100
5		9	1
4	4	(7)	4
5	7	100	<Ś>
e	3	to	6
5	100	7	6

1
	1
		1
			1

r • A

Rys.14.15

Otrzymujemy piorwozy przydziel u'. d’ln którogo

M • enx k(u) ■ G u£U'

r • lU'| - 4

Po okreólcniu oczok o wartoócioch rówhych i więkozych od wor -toóci dyokryninujęcej M. otrzymomy toblicę oczok dopuozczolnych przodotowionę no ryo.14.16.

Ryo.14.16

Roolizujęc procoo cochowonio widzimy, to nio możno ocechowoć kolumny bez Jodynki. Zotem piornozy przydziol U° (ryo.14.15) Joot optymalny, o Jogo wortoóć F(U°) ■ 6«

14.4.2. Przydziol nojliczniojozy moxmin

Ooko funkcję colu F przyjmuje eię funkcję

F( U' ) - Bin k(u) u CU

Należy wyznaczyć toki U°t U , to

F(U°) - mex F{ U¹)

u cu

Wortoóci k(u) • k^ możno w tym wypodku intorprotować joko wy-Uojnoćć procy i-tego procowniko, gdy wykonujo on J-tę procę.

Tok oformulowany probloo nosi hiutorycznę nazwę • p r o b-®ⁿu "ęoklego gordlo”. Nazwo pochodzi od prob-

2 39