Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

54
Universitatea Titu Maiorescu Facultatea de Informatică LUCRARE DE LICEN Ă Ț Coordonator ști in ific ț Lect. Univ. Dr. Radu ori!a A"solvent# $o%escu Marian Ale&andru Mi'ai ucure(ti) *+,-

Transcript of Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 1/54

Universitatea Titu Maiorescu

Facultatea de Informatică

LUCRARE DE LICEN ĂȚ

Coordonatorștiin ificț

Lect. Univ. Dr. Radu ori!a

A"solvent#$o%escu Marian Ale&andru Mi'ai

ucure(ti) *+,-

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 2/54

CUPRINS

Introducere..................................................................................................................................3Capitolul 1: Algoritmi Greedy....................................................................................................4

1.1 Noţiuni introductive .......................................................................41.2 Clase de metode de optimizare ....................................................61.3 Algoritmi iterativi i convergenţ! ................................................61." Clasi#carea metodelor de optimizare .........................................7

Capitolul 2: Tehnica Divide et Impera........................................................................................8Algoritmi de programare dinamic.................................................................11

2.1 Cautare binara ...............................................................................112.2 Branch & Bound ............................................................................142.3 Ar$orii $inari de c!utare tip data ..............................................162." Ar$orele optim ..............................................................................16

Capitolul 3: A!G"#IT$I D% &#"G#A$A#% DI'A$IC%................................................183.1 %rei Principii &undamentale ale Program!rii 'inamice ...........183.2 Programarea dinamic! comparat! cu te(nica )R**'+ ..........20

Capitolul 4: &lani(icarea proce)elor..........................................................................................21".1 Plani#carea proceselor ................................................................21

".2 Criteriile plani#c!rii ......................................................................21".3 Pro$lemele plani#catorului .........................................................21"." Strategiile plani#catorului ..........................................................21"., -irst Come -irst Served Sc(eduling .........................................22". Round Ro$in Sc(eduling ..............................................................25"./ Round Ro$in ..................................................................................26".0 Alegerea cuantei ...........................................................................27". Priorit sc(eduling .......................................................................27

".1 )ruparea priorit!4ilor ................................................................31Capitolul *: &ro+lema optimi,are.............................................................................................3*

,.1 5odelul pro$lemei de plani#care ..............................................35,.2 'escrierea matematic! a pro$lemei .........................................38,.3 5etode clasice de rezolvare .......................................................40

Aplicatie....................................................................................................................................4-Conclu,ii...................................................................................................................................*3i+liogra(ie...............................................................................................................................*4

2

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 3/54

Introducere

/n proce) repre,inta un )et de activitati din program0 care nu )e pot )uprapune )ee ecuta )ecvential . /n proce) e)te determinat de o )ecventa de in)tructiuni o procedura din programul care )e e ecuta. Termenul de proce) e)te (olo)it pentru a de)emna o+iectulactivitatii proce)orului0 in timpul e ecutiei unui program.

Algoritmii de plani(icare a e ecutiei proce)elor )unt impartiti0 in principiu0 in douamari cla)e: nonpreemptivi )i preemptivi.

Algoritmii nonpreemptivi )unt proiectati ca0 atunci cand un proce) intra in e ecutie0 )a(ie rulat pana cand a (o)t epui,at timpul )au de e ecutie. Algoritmii preemptivi )e conducdupa notiunea de prioritate proce)ul cu prioritatea cea mai mare tre+uie )a (ie cel care

(olo)e)te proce)orul&rogramarea dinamic e)te o metod de ela+orare a algoritmilor care )e aplic 5n

general pro+lemelor pentru care )e cere determinarea unui optim 5n urma adopt rii unor deci,ii.

'u e i)t un criteriu pe +a,a c ruia ) identi(ic m cu )iguran6 o pro+lema pentrure,olvarea c reia tre+uie ) utili, m metoda program rii dinamice0 dar putem (ormula doua propriet 6i care )ugerea, o )olu6ie prin programare dinamica.

7n acea)t lucrare 5ncerc ) pre,int c teva din metodele generale de ela+orare aalgoritmilor de programare a activitatilor.

3

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 4/54

Capitolul 16 Algoritmi )reed

1.1 Noţiuni introductiveAlgoritmii greedy greedy 9 lacom )unt in general )impli )i )unt (olo)iti la pro+leme de

optimi,are0 cum ar (i: )a )e ga)ea)ca cea mai +una ordine de e ecutare a unor lucrari pecalculator0 )a )e ga)ea)ca cel mai )curt drum intr un gra( etc. In cele mai multe )ituatii deace)t (el avem:

• multime decandidati lucrari de e ecutat0 var(uri ale gra(ului etc• (unctie care veri(ica daca o anumita multime de candidati con)tituie o solutie posibila 0 nu

neaparat optima0 a pro+lemei• (unctie care veri(ica daca o multime de candidati e)te fezabila 0 adica daca e)te po)i+il )a

completam acea)ta multime a)t(el incat )a o+tinem o )olutie po)i+ila0 nu neaparatoptima0 a pro+lemei

• functie de selectie care indica la orice moment care e)te cel mai promitator • dintre candidatii inca ne(olo)iti• functie obiectiv care da valoarea unei )olutii timpul nece)ar e ecutarii tuturor lucrarilor

intr o anumita ordine0 lungimea drumului pe care l am ga)it etc acea)ta e)te (unctia pecare urmarim )a o optimi,am minimi,am;ma imi,am

&entru a re,olva pro+lema noa)tra de optimi,are0 cautam o )olutie po)i+ila care )aoptimi,e,e valoarea (unctiei o+iectiv. /n algoritm greedy con)truie)te )olutia pa) cu pa).Initial0 multimea candidatilor )electati e)te vida. !a (iecare pa)0 incercam )a adaugam ace)teimultimi cel mai promitator candidat0 con(orm (unctiei de )electie. Daca0 dupa o a)t(el deadaugare0 multimea de candidati )electati nu mai e)te (e,a+ila0 eliminam ultimul candidatadaugat ace)ta nu va mai (i niciodata con)iderat. Daca0 dupa adaugare0 multimea de candidati)electati e)te (e,a+ila0 ultimul candidat adaugat va ramane de acum incolo in ea. De (iecaredata cand largim multimea candidatilor )electati0 veri(icam daca acea)ta multime nu con)tituieo )olutie po)i+ila a pro+lemei noa)tre. Daca algoritmul greedy (unctionea,a corect0 prima)olutie ga)ita va (i totodata o )olutie optima a pro+lemei. <olutia optima nu e)te in modnece)ar unica: )e poate ca (unctia o+iectiv )a ai+a aceea)i valoare optima pentru mai multe)olutii po)i+ile.

function greedy C =C e)te multimea candidatilor>S ? =S e)te multimea in care con)truim )olutia>'ile not solutie S and C @ do

x ? un element dinC care ma imi,ea,a;minimi,ea,a select xC ? C = x>if fezabil S = x> t'en S ? S = x>if solutie S t'en return S else return Bnu e i)ta )olutie

4

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 5/54

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 6/54

1.2 Clase de metode de optimizare

Dimensiunea problemelor

" m )ur a comple it 6ii pro+lemei de programare e)te dimen)iunea ace)teiae primat prin num rul de necuno)cute Ei de re)tric6ii. Dimen)iunea pro+lemelor care pot (ire,olvate a cre)cut o dat cu de,voltarea teoriei Ei a tehnicilor de calcul.

<e pot di)tinge acum trei categorii de pro+leme: dedimensiune redusă cu cel mult *varia+ile )au re)tric6ii 0 dedimensiune medie 5ntre * Ei 1FF de varia+ile )au re)tric6ii Ei dedimensiuni mari cu pe)te 1FF de varia+ile Ei re)tric6ii . Acea)t cla)i(icare re(lect nu numaidi(eren6e de dimen)iuni0 dar Ei de a+ordare. A)t(el pro+lemele de dimen)iuni mici pot (ire,olvate de m n )au cu un calculator de +u,unar. &ro+lemele de dimen)iuni medii pot (ire,olvate pe un calculator0 (olo)ind programe matematice generale. &ro+lemele de dimen)iunimari nece)it programe )o(i)ticate care e ploatea, caracteri)ticile particulare ale pro+lemeiEi de o+icei )e rulea, pe calculatoare de mare capacitate.

Teoria ini6ial a optimi, rii ) a concentrat a)upra o+6inerii re,ultatelor teoreticeignor nd a)pectele de calcul ale metodelor propu)e. A+ord rile recente )e a ea, pee ploatarea caracteri)ticilor calculatoarelor0 o+6in nd )olu6ia prin metode iterative.

1.3 Algoritmi iterativi i convergenţ!Cea mai important caracteri)tic a calculatoarelor e)te capacitatea lor de a e(ectua

opera6ii repetitive 5ntr un mod e(icient Ei din acea)t cau, ma oritatea algoritmilor dere,olvare a pro+lemelor de optimi,are )unt iterativi. 7n c utarea unei )olu6ii )e alege un vector ini6ial x F Ei algoritmul determin un vector x 1 care conduce la o valoare mai +un a (unc6ieio+iectiv proce)ul )e repet o+6in ndu )e un Eir de vectori x F0 x 10 H 0 x k 0 H 0 (iecare5m+un t 6ind valoarea (unc6iei o+iectiv0 (a6 de precedentul. Ace)t Eir converge c tre

x 0

)olu6ia pro+lemei. 7n pro+lemele de programare liniar )olu6ia )e o+6ine dup un num r (initde paEi. 7n pro+leme de programare neliniar Eirul nu atinge niciodat )olu6ia0 dar convergec tre ea. &ractic0 algoritmul )e opreEte c nd ) a o+6inut un punct )u(icient de aproape de)olu6ie.

Teoria algoritmilor iterativi poate (i 5mpar6it 5n trei p r6i. &rima parte )e ocup cucrearea de algoritmi. A doua parte0 numit Eianaliza convergenţei globale 0 anali,ea,convergen6a unui algoritm c tre )olu6ia optim atunci c nd )e ini6iali,ea, cu un punctdep rtat de )olu6ia optim . Cea de a treia component )e numeEteanaliza convergenţei locale

6

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 7/54

Ei )tudia, rata de convergen6 a Eirului c tre )olu6ia optim . %)te e)en6ial c nd )e recomandun algoritm ) )e men6ione,e Ei o e)timare a timpului nece)ar pentru o+6inerea )olu6iei. J3K

1." Clasi#carea metodelor de optimizare7n (unc6ie de num rul Ei tipul varia+ilelor0 de num rul de re)tric6ii0 )au de tipul (unc6iei

ce tre+uie optimi,at 0 modelele Ei metodele de optimi,are )e 5mpart 5n mai multe categorii.Ta+elul de mai o) ilu)trea, principalele categorii de metode de optimi,are:

Metoda Func/ie o"iectiv Restric/ii$ro!ramare liniară !iniar !iniareDeterminarea drumului minim0Di12stra3

!iniar !iniare

Minimum s%annin! tree !iniar !iniareAl!oritmul Ford4Ful2erson !iniar !iniare$ERT (i !estionea resurselorranc' and oundAl!oritmul alas 0cu valia"ile "inare3 !iniar !iniareAl!oritmi !eneticiAl!oritmul 5oo2e (i 6eeves 'eliniar r re)tric6ii

Metoda La!ran!e 'eliniar %galit 6i neliniareMetode 7R7 'eliniar 'eliniare$ro!ramare 8uadrică Luadric !iniare$ro!ramare liniară secven/ială 'eliniar !iniare$ro!ramare 8uadrică secven/ială 'eliniar

Capitolul 26 %e(nica 'ivide et Impera

Divide et impera e)te o tehnic de ela+orare a algoritmilor care con)t 5n:M De)compunerea ca,ului ce tre+uie re,olvat intr un num r de )u+ca,uri mai mici ale aceleiaEi

pro+leme.M #e,olvarea )ucce)iv Ei independenta a (iec ruia din ace)te )u+ca,uri.M #ecompunerea )u+)olu6iilor a)t(el o+6inute pentru a g )i )olu6ia ca,ului ini6ial.

7

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 8/54

< pre)upunem c avem un algoritm A cu timp p tratic. iec o con)tant 0 a)t(el5nc t timpul pentru a re,olva un ca, de m rimen e)te tA n 9 cn2. < pre)upunem c e)te po)i+il ) re,olvam un a)t(el de ca, prin de)compunerea 5n trei )u+ca,uri0 (iecare dem rime .n;2.. ie d o con)tant 0 a)t(el 5nc t timpul nece)ar pentru de)compunere Eirecompunere e)tet n 9 dn. olo)ind vechiul algoritm Ei ideea de de)compunere recompunere

a )u+ca,urilor0 o+tinem un nou algoritm B0 pentru care:

cnd cndnncnt nt t A B 4;32;34;32;132;3 22 +++=++≤+=

Termenul 3;4cn2 domin pe ceilal6i c ndn e)te )u(icient de mare0 ceea ce 5n)eamnca algoritmul B e)te 5n e)en6 cu 2*N mai rapid dec t algoritmul A. 'u am reuEit 5n) ))chim+ m ordinul timpului0 care r m ne p tratic. &utem ) continu m 5n mod recur)iv ace)t procedeu0 5mp r6ind )u+ca,urile 5n )u+)u+ca,uri etc. &entru )u+ca,urile care nu )unt mai maridec t un anumit pragnF0 vom (olo)i tot algoritmul A. "+6inem a)t(el algoritmulC 0 cu timpul.

Iat o de)criere general a metodei divide et impera:

functiondivimp x=returnea, o )olu6ie pentru ca,ul x>

if x e)te )u(icient de mict'en return adhoc x =de)compune x n )u+ca,urile x10 x20 H0 xk >for i . 1 to k do yi . divimp xi =recompune y10 y20 H0 yk n )copul o+6inerii )olu6iei y pentru x>return y

unde adhoc e)te )u+algoritmul de +a, (olo)it pentru re,olvarea micilor )u+ca,uri ale pro+lemei 5n cau,a in e emplul no)tru0 ace)t )u+algoritm e)te A .

/n algoritm divide et impera tre+uie ) evite de)compunerea recur)iv a)u+ca,urilor B)u(icient de mici 0 deoarece0 pentru ace)tea0 e)te mai e(icienta aplicarea directaa )u+algoritmului de +a,a. Ce 5n)eamn 5n) B)u(icient de mic O

In e emplul precedent0 cu toate ca valoarea luinF nu in(luentea, ordinul timpului0e)te in(luen6at 5n) con)tanta multiplicativa a lui3ln

n 0 ceea ce poate avea un rol con)idera+il5n e(icienta algoritmului. &entru un algoritmdivide et im%era oarecare0 chiar dac ordinultimpului nu poate (i 5m+un t 6it0 )e doreEte optimi,area ace)tui prag 5n )en)ul o+6inerii unuialgoritm c t mai e(icient. 'u e i)t o metod teoretic general pentru acea)ta0 pragul optim

depin, nd nu numai de algoritmul 5n cau, 0 dar Ei de particularitatea implement rii.Con)ider nd o implementare dat 0 pragul optim poate (i determinat empiric0 prin m )urareatimpului de e ecu6ie pentru di(erite valori ale luinF Ei ca,uri de m rimi di(erite.

8

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 9/54

7n general0 )e recomand o metod hi+rid care con)t 5n:i! determinarea teoretic a (ormei ecua6iilor recurenteii! g )irea empiric a valorilor con)tantelor (olo)ite de ace)te ecua6ii0 5n (unc6iede implementare.

#evenind la e emplul no)tru0 pragul optim poate (i g )it re,olv nd ecua6ia:

2;3 nt nt nt A A +=

%mpiric0 g )imnF P-0 adic valoarea pentru care nu mai are important dacaplic m algoritmul A n mod direct0 )au dac continuam de)compunerea. Cu alte cuvinte0at ta timp c t )u+ca,urile )unt mai mari dec tnF0 e)te +ine ) continu m de)compunerea.Dac continu m 5n) de)compunerea pentru )u+ca,urile mai mici dec tnF0 e(icientaalgoritmului )cade.

"+)erv m ca metodadivide et im%era e)te prin de(ini6ie recur)iv . /neori e)te po)i+il ) eliminam recur)ivitatea printr un ciclu iterativ. Implementata pe o maEinaconven6ionala0 ver)iunea iterativa poate fi ceva mai rapida 5n limitele unei con)tantemultiplicative . /n alt avanta al ver)iunii iterative ar (i (aptul c economi)eEte )pa6iul dememorie. Qer)iunea recur)iv (olo)eEte o )tiva nece)ar memor rii apelurilor recur)ive.&entru un ca, de m rimen0 num rul apelurilor recur)ive e)te de multe ori 5n . logn 0 uneorichiar 5n .n .

ie G9RQ0$S un gra( orientat0 unde Q e)te mul6imea v r(urilor Ei $ e)te mul6imeamuchiilor. iec rei muchii i )e a)ocia, o lungime negativ . Dorim ) calcul m lungimeacelui mai )curt drum 5ntre (iecare pereche de v r(uri.

Qom pre)upune c v r(urile )unt numerotate de la 1 la n0 Ei c matricea ! dlungimea (iec rei muchii: !Ji0iK9F0 !Ji0 K≥ F pentru i≠ 0 !Ji0 K9∞ dac muchia i0 nu e i)t .

&rincipiul optimalit 6ii e)te vala+il: dac cel mai )curt drum de la i la trece prinv r(ul U0 atunci por6iunea de drum de la i la U c t Ei cea de la U la 0 tre+uie ) (ie0 de a)emeneaoptime.

Con)truim o matrice D care ) con6in lungimea celui mai )curt drum 5ntre (iecare pereche de v r(uri. Algoritmul de programare dinamic ini6iali,ea, pe D cu !0 apoie(ectuea, n itera6ii. Dup itera6ia U0 D va con6ine lungimile celor mai )curte drumuri care(olo)e)c ca v r(uri intermediare doar v r(urile din =1020H0U>. Dup n itera6ii0 o+6ine re,ultatul(inal. !a itera6ia U0 algoritmul tre+uie ) veri(ice pentru (iecare pereche de v r(uri i0 dace i)t )au nu un drum0 trec nd prin v r(ul U0 care e)te mai +un dec t actualul drum optim cetrece doar prin v r(urile din =1020H0U 1>. ie DU matricea D dup itera6ia U.

Qeri(icarea nece)ar e)te atunci:

DU Ji0 K9min dU 1Ji0 K0 DU 1Ji0UK DU 1JU0 K

unde am ( cut u, de principiul optimalit 6ii pentru a calcula lungimea celui mai )curt drumvia U. implicit0 am con)iderat c un drum optim care trece prin U nu poate trece de dou ori prin U.

Ace)t algoritm )implu e)te datorat lui loyd 1VP2 :

function "loyd !J1..n0 1..nK

9

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 10/54

arra9 DJ1..n0 1..nKD← ! for U ← 1 to n do for i← 1 to n do

for ← 1 to n doDJi0 K← min DJi0 K0 DJi0UK DJU0 K

return D

De e emplu0 dac avem:

∞∞

==

F*1*

F*3F

*1*F*F

*F

F # D

o+tinem )ucce)iv

De o+icei dorim ) a(l m nu numai lungimea celui mai )curt drum0 dar Ei tra)eul ) u. 7nacea)t )itua6ie0 vom con)trui o a doua matrice &0 ini6iali,at cu ,ero. ucla cea mai interioara algoritmului devine

if DJi0UK DJU0 KRDJi0 Kt'en DJi0 K← DJi0UK DJU0 K

&Ji0 K← U

10

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 11/54

C nd algoritmul )e opreEte0 &Ji0 K va con6ine v r(ul din ultima itera6ie care a cau,at omodi(icare 5n DJi0 K. &entru a a(la prin ce v r(uri trece cel mai )curt drum de la i la 0con)ult m elementul &Ji0 K. Dac &Ji0 K9F0 atunci cel mai )curt drum e)te chiar muchia i0 .

Dac &Ji0 K9U0 atunci cel mai )curt drum de la i la trece prin U Ei urmea, ) con)ult mrecur)iv elementele &Ji0UK Ei &JU0 K pentru a g )i Ei celelalte v r(uri intermediare.

Algoritmi de programare dinamic

2.1 Cautare binara

C utarea +inar e)te cea mai )impl aplica6ie a metodeidivide et im%era0 (iindcuno)cut 5nc 5nainte de apari6ia calculatoarelor. 7n e)en6a0 e)te algoritmul dup care )e cautun cuv nt intr un dic6ionar0 )au un nume 5n cartea de tele(on.

ie $ J1 ..nK un ta+lou ordonat cre)c tor Ei x un element oarecare. &ro+lema con)t5n a l g )i pe x n $ 0 iar dac nu )e a(l acolo 5n a g )i po,i6ia unde poate (i in)erat. C ut mdeci indicelei a)t(el 5nc t 1 9i 9 n Ei$ JiK 9 x R$ Ji 1K0 cu conven6ia$ JFK 9 80$ Jn 1K 9 8.

Cea mai evident metod e)tecăutarea secvenţială :

function se%uential $ J1 ..nK0 x=caut )ecven6ial pe x n ta+loul$ >for i . 1 to n doif $ JiK S x t'en return i 1return n

11

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 12/54

Algoritmul nece)it un timp 5n W 1r 0 unde r e)te indicele returnat acea)tain)eamn W 1 pentru ca,ul cel mai (avora+il Ei W n pentru ca,ul cel mai ne(avora+il. Dac pre)upunem c elementele lui$ )unt di)tincte0 ca x e)te un element al lui$ Ei c )e a(la cu pro+a+ilitate egal 5n oricare po,i6ie din$ 0 atunci +uclafor )e e ecut 5n medie de n2 3 n2 ;2n ori. Timpul e)te deci 5n W n Ei pentru ca,ul mediu.

&entru a m ri vite,a de c utare0 metodadivide et im%era )ugerea, )a l c utam pe x (ie 5n prima um tate a lui$ 0 (ie 5n cea de a doua. Compar ndu l pe x cu elementul dinmi locul ta+loului0 putem decide 5n care dintre um t 6i ) c utam.

#epet nd recur)iv procedeul0 o+6inem urm torul algoritm decăutare binară :

functionbinsearch $ J1 ..nK0 x=c uta +inar pe x n ta+loul$ >

if n 9 For x R$ J1Kt'en return Freturn binrec $ J1 ..nK0 xfunctionbinrec $ Ji .. &K0 x

=c uta +inar pe x 5n )u+ta+loul$ Ji .. &K acea)ta procedurae)te apelata doar c nd$ JiK 9 x R$ J &1K Eii 9 &>if i 9 &t'en return ik ? i &1 div 2if x R$ Jk Kt'en return binrec $ Ji .. k 1K0 xelse return binrec $ Jk .. &K0 x

Algoritmulbinsearch nece)it un timp 5n W logn 0 indi(erent de po,i6ia lui x 5n$ demon)tra6i ace)t lucru0 rev , nd. &rocedurabinrec e ecut doar un )ingur apel recur)iv0 5n(unc6ie de re,ultatul te)tului B x R $ Jk K . Din acea)t cau, 0 c utarea +inar e)te0 mai cur nd0un e emplu de )impli(icare0 dec t de aplicare a tehniciidivide et im%era.

Iat Ei ver)iunea iterativ a ace)tui algoritm:

function iterbin 1 $ J1 ..nK0 x=c utare +inara iterativa>if n 9 For x R$ J1Kt'en return Fi ?1 &? n'ile i R &do=$ JiK 9 x R$ J &1K>

k ? i &1 div 2if x R$ Jk Kt'en &? k 1elsei ? k return i

Ace)t algoritm de c utare +inar pare ine(icient 5n urm toarea )itua6ie: dac la unanumit pa) avem x 9 $ Jk K0 )e continu totuEi c utarea. /rm torul algoritm evita ace)tinconvenient0 oprindu )e imediat ce g )eEte elementul c utat.

function iterbin 2 $ J1 ..nK0 x

=varianta a c ut rii +inare iterative>i( n 9 For x R$ J1Kt'en return Fi ? 1 &? n

12

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 13/54

'ile i R &do=$ JiK 9 x R$ J &1K>k . i & div 2case x R$ Jk K: &? k 1

x 9 $ Jk 1K:i ? k 1

ot'er ise : i0 &? k return i

Timpul pentruiterbin 1 e)te 5n X logn . Algoritmuliterbin 2 nece)it un timp caredepinde de po,i6ia lui x n $ 0 (iind 5n X 1 0 X logn 0 X logn pentru ca,urile cel mai (avora+il0mediu Ei re)pectiv0 cel mai ne(avora+il.

Care din aceEti doi algoritmi e)te oare mai e(icientO &entru ca,ul cel mai (avora+il0iterbin 2 e)te0 evident0 mai +un. &entru ca,ul cel mai ne(avora+il0 ordinul timpului e)te acelaEi0num rul de e ecut ri ale +uclei'ile e)te acelaEi0 dar durata unei +ucle'ile pentruiterbin 2e)te ceva mai mare deciiterbin 1 e)te pre(era+il0 av nd con)tanta multiplicativ mai mic .&entru ca,ul mediu0 compararea celor doi algoritmi e)te mai di(icil : ordinul timpului e)teacelaEi0 o +ucla'ile 5niterbin 1 durea, 5n medie mai pu6in dec t 5niterbin 20 5n )chim+iterbin 1 e ecut 5n medie mai multe +ucle'ile dec t iterbin 2.

/n ar+ore +inr 5n care (iecare ( r( con6ine o valoare numit cheie e)te un ar+ore dec utare0 dac cheia (iec rui v r( neterminal e)te mai mare )au egal cu cheia de)cenden6ilor ) i )t ngi Ei mai mic )au egal cu cheia de)cenden6ilor ) i drep6i. Dac cheile ar+orelui )untdi)tincte0 ace)te inegalit 6i )unt0 5n mod evident0 )tricte.

igura de mai )u) e)te un e emplu de ar+ore de c utare 0 con6in nd cheile A0 0 C0H0Y. v r(urile pot con6ine Ei alte in(orma6ii 5n a(ar de chei0 la care ) avem acce) prinintermediul cheilor. Acea)t )tructur de date e)te util 0 deoarece permitee o c utare e(icienta valorilor 5n ar+ore:

Cu o mul6ime dat de chei0 )e pot con)trui mai mul6i ar+ori de c utare (ig. de )u) .&entru a c uta o cheie Z 5n ar+orele de c utare0 Z va (i comparat la 5nceput cu cheiar d cinei ar+orelui. Dac Z e)te mai mic dec t cheia r d cinii0 atunci )e continu c utarea 5n)u+ar+orele )t ng. Dac Z e)te egal cu cheia r d cinii0 atunci c utarea )e incheie cu )ucce).Dac Z e)te mai mare dec t cheia r d cinii0 atunci )e cotinu c utarea 5n )u+ar+orele drept.<e continu a)t(el recur)iv acce)t proce).

13

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 14/54

7enerăm un ar"ore "inar) conform următoarei metode recursive#r d cina e)te etichetat cu 10ndac un v r( e)te etichetat cu i0 0 i e)te mai mic dec t 0 atunci (iul ) u )t ng va (i etichetatcu i0rJi0 K 1 i (iul ) u drept cu rJi0 K 10v r(urile terminale )unt etichetate cu i0i

plec nd de la ace)t ar+ore0 ar+orele de c utare optim )e o+6ine )chim+ ndetichetele i0 0 iR 0 5n crJi0 K0 iar etichetele i0i 5n ci.

2.2 Branch & Bound

%)te )trategia cea mai )o(i)ticata de proiectare a algoritmilor. %a a aparut datoritae i)tentei pro+lemelor pentru care )olutia de tip +acUtracUing poate nece)ita un timpa)tronomic de rulare a programului. In re,olvarea ace)tor pro+leme apare o a)emenea penuriede in(ormatii incit modelul a+)tract a)ociat pro+lemei gra(ul de cautare a )olutiilor [ nu poate (i preci,at in avan)0 din etapa de anali,a. <ingura )olutie care ramine e)te includereaunui )u+algoritm )uplimentar ce permite con)truirea ace)tui gra( pe parcur)0 din aproape inaproape. Aparitia acelui )u+algoritm )uplimentar da numele metodei: +ranch\+ound.

%)te po)i+ila compararea algoritmului +ranch\+ound cu un ro+ot ce invata )a )edepla)e,e )ingur )i e(icient printr un la+irint. Acel ro+ot va (i o+ligat )a )i con)truia)ca in paralel cu cautarea ie)irii o harta un gra( ] a la+irintului pe care va aplica apoi 0 pa) cu pa)0metode e(iciente de o+tinere a drumului cel mai )curt.

!a )trategia de cautare a )olutiei in )patiul gra(ul de cautare +acUtracUing0 (iecare pa) urma automat unul dupa altul pe +a,a unei reguli incorporate0 in timp ce la)trategia greedy alegerea pa)ului urmator era (acuta pe +a,a celei mai +une alegeri. In ca,ulace)tei )trategii [ +ranch\+ound0 pentru pa)ul urmator algoritmul nu mai e)te capa+il )a (acavreo alegere pentru ca e)te o+ligat mai intii )a )i determine )ingur nodurile vecine ce pot (ivi,itate. 'umele metodei0+ranch9rami(ica )i +ound9delimitea,a0 provine de la cele douaactiuni ce tin locul actiunii de alegere de la )trategiaGreedy. &rima actiune e)te con)truirea )audeterminarea prin rami(icare a drumurilor de continuare0 iar a doua e)te eliminareacontinuarilor ramurilor ine(iciente )au eronate. &rin eliminarea unor ramuri0 portiuni intregiale )patiului de cautare a )olutiei raminind a)t(el dintr o data delimitate )i Bi,olate . Acea)ta)trategie de delimitare din mer) a anumitor Bregiuni ale )patiului de cautare a )olutiilor e)te

14

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 15/54

cea care permite reducerea ordinului de marime a ace)tui )patiu. <olutia acea)ta e)te e(icientadoar daca ci)tigul o(erit prin reducerea )patiului de cautare )ca,ind e(ortul )uplimentar depu) pentru determinarea )i eliminarea din mer) a continuarilor ine(iciente e)te )u+)tantial.

<olutiile de tip +acUtracUing0 avind la +a,a un )chelet atit de general algoritmul detraver)are a gra(ului de cautare a )olutiilor )int relativ )implu de adaptat in re,olvarea unor

pro+leme. &oate ace)ta e)te motivul care a condu) pe unii programatori lip)iti de e perienta laconvingerea (al)a ca B"rice e)te po)i+il de re,olvat prin +acUtracUing .!a ora actuala0 li)ta pro+lemelor pentru care nu )e cuno)c decit )olutii e ponentiale0 totalnere,ona+ile ca durata de e ecutie a programului de )olutionare0 cuprinde citeva )ute de pro+leme0 una mai cele+ra ca cealalta. #eamintim doar de B+anala dar aga)anta &ro+lema a"rarului unei in)titutii de invatamint care nu admite o )olutie +acUtracUing datorita durateia)tronomice de a)teptare a )olutiei.

Datorita totalei lor ine(iciente in e ecutie0 )olutiile +acUtracUing o+tinute dupa oanali,a )i o proiectare Bla prima mina +rute (orce approach0 in lim+a engle,a a ung )a (iereanali,ate din nou cu mai multa atentie. <e con)tata atunci ca modelul a+)tract a)ociat pro+lemei0 (ie e)te prea )arac in in(ormatii pentru determinarea gra(ului de cautare a )olutiilor0(ie conduce la un gra( de cautare avind dimen)iunea nere,ona+ila e ponentiala )au (actoriala0(ata de dimen)iunea n a vectorului de intrare . <ingura )olutie care ramine in acea)ta )ituatiela di)po,itie e)te ca ace)te )olutii )a (ie reproiectate prin metoda +ranch\+ound.

/n e emplu u)or de intele) de Bpro+lema +ranch\+oundB il o(era &ro+lema Generalaa !a+irintului. <pre deo)e+ire de &ro+lema !a+irintului pre,entata anterior care admitea o)olutie de tip +acUtracUing 0 in varianta e tin)a a ace)tei pro+leme0 numarul directiilor po)i+ile de urmat la (iecare pa) poate (i oricit de mare0 iar o+)tacolele pot avea orice (orma )idimen)iune. In ace)t ca,0 )ingura po)i+ilitate e)te con)truirea Bdin mer) a )patiului de cautarea )olutiei. A)t(el0 pentru determinarea unui drum de ie)ire din la+irint )au a drumului cel mai)curt daca e)te po)i+ila determinarea ace)tuia in timp re,ona+il] e)te o+ligatorie adoptarea)trategiei +ranch\+ound.

De)i acea)ta )trategie poate )a crea)ca uneori )urprin,ator de multe(icienta algoritmilor de )olutionare din nere,ona+ili ca timp de e ecutie ei pot a ungere,ona+ili0 datorita reducerii dimen)iunii e ponentiale a )patiului de cautare a )olutiei 0aplicarea ei e)te po)i+ila doar printr un e(ort )uplimentar in etapa de anali,a )i in cea de proiectare a algoritmului. De,avanta ul ma or al ace)tei metode con)ta deci in e(ortul ma or depu) in etapa de anali,a a pro+lemei anali,a care in)a )e va (ace o )ingura data )i +ine] )ie(ortul )uplimentar depu) in etapa proiectarii algoritmului de )olutionare.

Din e perienta practica e)te cuno)cut (aptul ca0 pentru a anali,a o pro+lema di(icila unanali)t poate avea nevoie de )aptamini )au chiar luni de ,ile de anali,a0 in timp ce algoritmulde )olutionare proiectat va dura0 ca timp de e ecutie0 doar citeva ,eci de minute. Daca

programul o+tinut nu e)te nece)ar a (i rulat decit o data0 acea)ta e)te prea putin pentru Ba )eamorti,a co)tul mare al anali,ei )i proiectarii )ale. In acea )ituatie0 )olutia +ranch\+ounde)te nerenta+ila )i0 pro+a+il ca ar (i mai ie(tina )trategia +acUtracUing de )olutionare0 chiar )icu ri)cul de a o+tine o e ecutie )ingura de alt(el a programului cu durata de o )aptaminaceea ce poate )a in)emne totu)i economie de timp .

2.3 Ar$orii $inari de c!utare tip data

7ntr o prim apro imare0 ar+orele +inar e)te un tip de dat )imilar tipului li)t .Q r(urile )unt compu)e din in(orma6ie cheie Ei leg turi0 iar ar+orele propriu ,i) e)te complet preci,at prin adre)a v r(ului r d cin .

15

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 16/54

7n ca,ul ar+orelui de c utare0 nu mai e)te nece)ar o a)t(el de generalitate0 deoarecevom implementa direct opera6iile )peci(ice. 7n mare0 ace)te opera6ii )unt 5p r6ite 5n:

C ut ri. !ocali,area v r(ului cu o anumit cheie0 a )ucce)orului )au predece)orului) u0 precum Ei a v r(urilor cu cheile de valoare ma im 0 re)pectiv minim .

$odi(ic ri. Ar+orele )e modi(ic prin Etergerea )au in)erarea unor v r(uri.

"rgani, ri. Ar+orele nu e)te con)truit prin in)erarea elementelor0 ci glo+al prin)ta+ilirea unei leg turi unice 5ntre v r(uri. /n ca, particular al ace)tei opera6ii e)tereorgani,area ar+orelui dup o perioad )u(icient de mare de utili,are.

2." Ar$orele optim

Qom re,olva pro+lema o+6inerii ar+orelui optim 5n cel mai )implu ca, po)i+il. Av nd5n vedere )peci(icul di(erit al opera6iilor de organi,are (a6 de celelalte opera6ii e(ectuatea)upra gra(urilor0 am con)iderat util ) 5ncap)ul m optimi,area 5ntr o cla) pe care o vomnumi )tructura pentru optimi,area ar+orilor.

Func/ionalitatea ei constă :n#ini6iali,area unui ta+lou cu adre)ele v r(urilor 5n ordinea cre)c toare a

pro+a+ilit 6ilor cheilor.)ta+ilirea de noi leg turi5ntre v r(uri0 a)t(el 5nc t ar+orele ) (ie optim.

$rinci%ala cau;ă %entru care a fost aleasăaceastă im%lementare este că sunt necesaredoar o%era/ii de modificare a le!ăturilor. De%lasarea unui v<rf :nseamnă nu numai

de%lasarea c'eii) ci (i a informa/ieiasociate.

Căutarea în arbore&rincipala opera6ie e(ectuat prin intermediul ar+orilor +inari de c utare e)te reg )irea

in(orma6iei a)ociate unei anumite chei. Actuali,area pro+a+ilit 6ilor cheilor din ar+ore0 dup(iecare c utare0 e)te cea mai delicat 0 deoarece impune )ta+ilirea importan6ei evalu rilor e i)tente 5n raport cu re,ultatul c ut rilor. De (apt e)te vor+a de un proce) de inv 6are care porneEte de la cunoEtin6e de a e i)tente 5n memorie. &ro+lema e)te de a )ta+ili gradul deimportan6 al cunoEtin6elor e i)tente 5n raport cu cele nou do+ ndite.

Modificarea arborelui

16

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 17/54

$odi(icarea )tructurii ar+orelui de c utare0 prin in)erare )au Etergerea unor v r(uritre+uie reali,at a)t(el 5nc t proprietatea de ar+ore de c utare ) nu )e altere,e. Cele dou

opera6ii )unt di(erite 5n privin6a comple it 6ii. ^tergerea e)te mai di(icil Ei mult mai di(eritde opera6iile o+iEnuite.Comple itatea (unc6iei de Etergere e)te tipic pentru )tructurile de c utare. Ace)te )tructuritind ) devin at t de compacte 5nc t Etergerea (iec rei chei nece)it repara6ii de)tul decomplicate. De aceea )e pre(er de cele mai multe ori o Etergere leneE 0 prin care v r(ul e)tedoar marcat ca (iind Eter)0 Etergerea (i,ic reali, ndu )e cu oca,ia unor reorgani, ri periodice.

Capitolul 36 A7)8RI%5I '* PR8)RA5AR*'INA5IC*

3.1 %rei Principii &undamentale ale Program!rii 'inamice

17

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 18/54

&rogramarea dinamic 0 ca Ei metoda divide et impera0 re,olv pro+lemele com+in nd)olu6iile pro+lemelor. Dup cum am v ,ut0 algoritmii divide et impera parti6ionea, pro+lemele 5n )u+pro+leme independente0 re,olv pro+lemele 5n mod recur)iv0 iar apoicom+in )olu6iile lor pentru a re,olva pro+lema ini6ial . Dac )u+pro+lemele con6in

)u+pro+leme comune0 5n locul metodei divide et impera e)te mai avanta oa) de aplicat tehnica program rii dinamice.&rogramarea dinamic e)te o metod de ela+orare a algoritmilor care )e aplic 5n

general pro+lemelor pentru care )e cere determinarea unui optim 5n urma adopt rii unor deci,ii.

'u e i)t un criteriu pe +a,a c ruia ) identi(ic m cu )iguran6 o pro+lem pentrure,olvarea c reia tre+uie ) utili, m metoda program rii dinamice0 dar putem (ormula dou propriet 6i care )ugerea, o )olu6ie prin programare dinamic .

&ro+lema dat poate (i de)compu) 5n )u+pro+leme Ei )olu6ia optim a pro+lemeidepinde de )olu6iile optime ale )u+pro+lemelor )ale.

Ace)t criteriu nu indic neap rat o )olu6ie prin programare dinamic 0 ar putea (i Ei un indiciuc )e poate aplica metoda Greedy )au metoda _Divide et Impera .

<u+pro+lemele pro+lemei date nu )unt independente0 ci )e )uprapun.Datorit (aptului c )u+pro+lemele pro+lemei date )e )uprapun0 deducem c o a+ordare

prin metoda _Divide et Impera ar (i de,a)truoa) din punctul de vedere al timpului dee ecu6ie datorit (aptului c pro+lemele )e )uprapun )e a unge la re,olvarea repetat aaceleiaEi )u+pro+leme . &rin urmare0 vom re,olva )u+pro+lemele o )ingur 0 dat 0 re6in ndre,ultatele 5ntr o )tructur de date )uplimentar de o+icei un ta+lou . #e,olvarea unei pro+leme prin programare dinamic pre)upune urm torii paEi:1. <e identi(ic )u+pro+lemele pro+lemei date.2. <e alege o )tructur de date )uplimentar 0 capa+il ) re6in )olu6iile )u+pro+lemelor.3. <e caracteri,ea, )u+)tructura optimal a pro+lemei printr o rela6ie de recuren6 .4. &entru a determina )olu6ia optim 0 )e re,olv rela6ia de recuren6 5n mod +ottom up )ere,olv )u+pro+lemele 5n ordinea cre)c toare a dimen)iunii lor . 7n cele ce urmea, vom e empli(ica pa) cu pa) modul de re,olvare a pro+lemelor prinmetoda program rii dinamice.

Qaria+ilele0)au (unc6iile care de)criu (iecare etap tre+uie ) (ie 5n aEa (el de(inite 5nc t )

de)crie complet un proce)0deci pentru ace)t lucru va tre+ui ) r )pundem la dou 5ntre+ ri:1 care e)te etapa ini6ial ca, 5n care avem de a (ace cu un proce) deci,ionalde)cendent )au caree)te etapa (inal ca, 5n care avem de a (ace cu un proce)deci,ional a)cendent

2 care e)te regula dup care trecem dintr o etap 5n alta O De o+icei acea)t regul e)tee primat printr o recuren6 .

Deoarece0 avem de a (ace cu o pro+lem care )e re,olv 5n mai multe etape0 nu nemai r m ne dec t) vedem cum lu m deci,iile dintr o etap 5n alta. 'u m re(er aici la orela6ie de recuren6 de care amvor+it mai )u)0 ci la (aptul c (oarte pro+a+il apare po)i+ilitateaca la un anumit moment ) putem alegedin mai multe deci,ii. De e emplu0 pro+lemacalculului numerelor lui i+onaci )e 5ncadrea, 5n categoria program rii dinamice deoarece:

− e)te un proce) 5n etape− (iec rei etape U 5i core)punde calculul celui de al U lea num r i+onacci

18

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 19/54

− e i)t o )ingur deci,ie pentru a trece la o etap )uperioar Determinarea unui drum celeag dou oraEe A Ei Ei care trece printr un num r minim de alteoraEe e)te toto pro+lem de programare dinamic deoarece:

− e)te un proce) 5n etape0− (iec rei etape U 5i core)punde determinarea unui drum de lungime U ce pleac din

oraEul A− dar e i)t mai multe deci,ii pentru trecerea la drumul de lungimea U 1

Dac anali, m natura pro+lemelor care au (o)t re,olvate prin programare liniar )au prin teoria gra(urilor0 con)tat m c proce)ul economic pe care doream ) 5l optimi, m )ede)( Eura 5ntr o )ingur (a, etap )au perioad . `in nd cont de (aptul c e i)t numeroa)e pro+leme de optimi,are care modelea, proce)e economice care )e de)( Eoar 5n mai multe perioade Ei la (iecare perioad tre+uie ) )ta+ilim )olu6ia optim 0 vi,iunea )tatic poatecon)titui un nea un). %)te evident (aptul c )ucce)iunea de )olu6ii nu )e poate determina6in nd )eama numai de parametrii (iec rei perioade anali,ate 5n parte0 Ei c e)te nece)ar )identi(ic m o )ucce)iune de )olu6ii care optimi,ea, 5ntregul proce) anali,at. &ro+lemeleeconomice care reclam o )uit de deci,ii )ecven6iale )e caracteri,ea, prin (aptul c o deci,iecare adoptat 5ntr o anumit perioad are at t un e(ect economic imediat0 c t Ei unul de lungdurat 0 care in(luen6ea, Ei a)upra celorlalte etape.

"ptimi,area proce)elor )ecven6iale )e o+6ine prin metodele unei teorii matematicerelativ recent con)tituite Ei care )e numeEte programare dinamicã . Creatorul ace)tei teorii e)te#ichard ellman0 iar lucrarea )a (undamental e)te Dynamic 'rogramming ap rut 5n anul1V*-. &rogramarea dinamic are un c mp larg de aplica6ie 5n cercetarea opera6ionalorgani,area produc6iei0 ge)tiunea )tocurilor0 re5nnoirea echipamentelor 0 precum Ei 5n altedomenii naviga6ie co)mic 0 proce)e cu cone iune inver) etc. . < pre)upunem un proce))ecven6ial a c rui de)( Eurare 5n timp depinde de o varia+il care poate lua o mul6ime devalori 5n (iecare etap . 'e putem decide pentru o valoare determinat a varia+ilei 5n (iecareetap Ei din acea)t cau, ea )e numeEte varia+il de deci,ie )au de control. " )ucce)iuneoarecare de deci,ii con)tituie o politic Ei cea care ne intere)ea, e)te politica optim 0 de pildaceea care conduce la un co)t total minim al proce)ului.

Deo)e+im dou tipuri principale de proce)e )ecven6iale:a determini)te0 c nd la (iecare (a, proce)ul e)te controlat 5n 5ntregime de deci,ia pe care olu m + )toha)tice0 atunci c nd evolu6ia proce)ului )e de)( Eoar )u+ du+la in(luen6 a deci,iilor Ei aha,ardului.

<e numeEte politic optim acea )ucce)iune de deci,ii care optimi,ea, proce)ul 5nan)am+lu lui0 (iind vor+a de un proce) determini)t. 7n ca,ul unui proce) )toha)tic0 )e (olo)eEte

5n mod core)pun, tor no6iunea de )trategie optim .&roce)ele dinamice pot (icontinue )au discrete . /n e emplu de proce) di)cret e)teurm torul: o 5ntreprindere tre+uie ) Ei 5ntocmea)c planul de aprovi,ionare anual pentru unanumit material )e con)ider 12 perioade luni Ei pentru (iecare perioad )e )ta+ileEtecantitatea de aprovi,ionat0 a)t(el ca pe 5ntregul an ) re,ulte un co)t total minim. &roce)eledinamice di)crete pot aveaorizontul limitat 5n e emplu de mai )u) 12 perioade )aunelimitat .

3.2 Programarea dinamic! comparat! cu te(nica )R**'+

At t programarea dinamic 0 c t Ei tehnica greedy0 pot (i (olo)ite atunci c nd )olu6iaunei pro+leme e)te privit ca re,ultatul unei )ecven6e de deci,ii. Deoarece principiuloptimalit 6ii poate (i e ploatat de am+ele metode0 ) ar putea ) (im tenta6i ) ela+or m o)olu6ie prin programare dinamic 0 acolo unde e)te )u(icient o metod greedy0 atunci c nde)te nece)ar de (apt aplicarea program rii dinamice.

19

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 20/54

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 21/54

● sc#ed$ er$ imp ementea%ă $n a &oritm de p ani'care (sc#ed$ in&a &orit#m)● acest a &oritm permite a e&erea $neia din procese e a*ate +n starearead, -i marcarea acesteia ca 'ind acti!● d$pă a e&ere sc#ed$ er$ rea i%ea%ă sc#im area conte/t$ $i +ntre

proces$ care a ost acti! -i ce care este marcat să de!ină acti!

".2 Criteriile plani#c!rii

● &airness " 'ecare proces să oc$pe procesor$ +n mod cinstit● e#cient " să men ină $ti i%area c t mai aproape de 100● timp de r!spuns " minim● turnaround " minimi%are timp$ $i de a-teptare

● t(roug(put " ma/imi%area n$măr$ $i de o $ri pe oră

".3 Pro$lemele plani#catorului

● criterii e s$nt contradictorii de e/. pentr$ a minimi%a timp$ de răsp$ns ar tre $i r$ ate c t mai

p$ ine procese● o comp ica ie pre%intă apt$ că 'ecare proces este $nic -i impredicti i $ne e procese petrec oarte m$ t timp a-tept nd opera ii O: a te e potr$ a ore +ntre&i ără a-teptare a acti!area $n$i proces sc#ed$ er$ n$ poate să -tie c t timp !a r$ a

proces$ +nainte de a se oca

"." Strategiile plani#catorului

● strate&ii de p ani'care preemti!e" permit s$spendarea temporară aprocese or care r$ ea%ă a 'ecare +ntrer$pere de ceas se r$ ea%ă sc#ed$ er$ care decide dacăproces$ c$rent contin$ă să r$ e%e sa$ n$: dacă n$ proces$ !a 's$spendat -i contro $ dat a t$i proces● strate&ii de p ani'care non;preempti!e" procese e r$ ea%ă p nă c nd +-itermină e/ec$ ia sa$ se !or oca +n a-teptarea $nei opera ii O a ape $ sistem de terminare sa$ ce ocant se r$ ea%ă sc#ed$ er$

"., -irst Come -irst Served Sc(eduling

● p ani'carea cea mai simp ă● !a ' a ocat procese or +n ordinea +n care acestea se pornesc

21

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 22/54

● procese e contin$ă p nă a terminare sa$ ocare: moment +n care$rmător$ proces din istă !a ' p ani'cat● se poate imp ementa oarte $-or c$ $n < <O● este o p ani'care non;preempti!ă

import a!a.$ti .=ector>

public class FCFS{ protected int[] arrivalTime; protected int[] burstTime; protected int[] job; protected int[] jobIdle; protected int numberOfProcess; protected int[] waitin Time; protected int[] finis!edTime; protected int avera e"T#avera eTTsum;

protected int jobs;

p$ ic < <S (int?@ aA:int?@ A:int?@ o :int n$m) B arri!a Aime C aA> $rstAime C A> t#is. o C o > n$m erO rocess C n$m> Daitin&Aime C neD int?n$m erO rocess@> 'nis#edAime C neD int?n$m erO rocess@> o s C 0> E

p$ ic !oid < <S()B int 'rst ome:tempFrri!a Aime:tempG$rst>

or (int i C 0> i H (n$m erO rocess ; 1)> iII)B

or (int C (i I 1)> H n$m erO rocess> II) B i (arri!a Aime? @ H arri!a Aime?i@)

B

'rst ome C o ? @> o ? @ C o ?i@> o ?i@ C 'rst ome> tempFrri!a Aime C arri!a Aime? @> arri!a Aime? @ C arri!a Aime?i@> arri!a Aime?i@ C tempFrri!a Aime> tempG$rst C $rstAime? @> $rstAime? @ C $rstAime?i@> $rstAime?i@ C tempG$rst>

E

E

E S,stem.o$t.print n(JKnCCLisp a,in& Aa e o Mo s Sorted Fccordin& to Frri!a AimeCCJ)> disp a,Sorted()>

22

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 23/54

S,stem.o$t.print n(JCCCCCCL S NF PQ QFPAA RF ACCCCCCJ)> so !eTaitin&Aime()> so !eF!era&eAime()>

E

p$ ic !oid so !eF!era&eAime()B //ATT or(int i C 0>iHn$m erO rocess>iII) a!era&eAAs$m C a!era&eAAs$mI('nis#edAime?i@;arri!a Aime?i@)> //AWT or(int C0> Hn$m erO rocess> II) a!era&eTA C a!era&eTAI(Daitin&Aime? @ ; arri!a Aime? @)>

do$ e aAA C (*oat)a!era&eAAs$mUn$m erO rocess> do$ e aTAC(*oat)a!era&eTAUn$m erO rocess> S,stem.o$t. ormat(JFAA" .2 J:aAA)> S,stem.o$t.print n(JJ)> S,stem.o$t. ormat(JFTA" .2 J:aTA)>E

p$ ic !oid so !eTaitin&Aime()B int ctrC0> =ectorH nte&erV id eTA C neD =ectorH nte&erV()> =ectorHGoo eanV id e C neD =ectorHGoo eanV()> or(int % C 0> % H n$m erO rocess> %II)

B i (ctr V arri!a Aime?%@)

Bid e.add(Goo ean.A W)>or(int X C 0> X H $rstAime?%@> XII)B

ctrII>

E o sII>

Ee seB

D#i e(ctr HC arri!a Aime?%@)B

i (ctr CC arri!a Aime?%@)B o sII>

or(int C arri!a Aime?%@> H (arri!a Aime?%@ I $rstAime?%@)> II) B

ctrII>

E id e.add(Goo ean.A W)>

Ee seB

o sII>

ctrII>id e.add(Goo ean.<FNSW)>E

23

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 24/54

E

E

'nis#edAime?%@ C ctr>i (%CC0)

id eTA.add(0)>e se id eTA.add(ctr)>E Daitin&Aime?0@ C 0> or(int % C 1>%Hn$m erO rocess>%II) B

Daitin&Aime?%@ C 'nis#edAime?%@ ; $rstAime?%@>

E

S,stem.o$t.print n(JJIid eTA.toStrin&())>S,stem.o$t.print n(JJIid e.toStrin&())>S,stem.o$t.print n(JMo s" JI o s)>int ctr2 C 0>

or(int , C 0> , H n$m erO rocess> ,II)B

i (id e.e ementFt(ctr2)CC a se)B i (ctr2CC0)BS,stem.o$t.print(JY JI(Daitin&Aime?,I1@)IJ YJ)> ctr2II>Ee se B

S,stem.o$t.print(JY JI(id eTA.e ementFt(,);Daitin&Aime?,@)IJ YJ)> ctr2II> E

E S,stem.o$t.print(JY JI o ?,@IJ(JI $rstAime?,@IJ)JIJ YJ)>

ctr2II> E

S,stem.o$t.print n(JJ)>

or(int / C 0>/Hn$m erO rocess>/II) B i (id eTA.e ementFt(/) CC 0) S,stem.o$t.print(JJIDaitin&Aime?/@)> e se S,stem.o$t.print(J JIDaitin&Aime?/@I J JIid eTA.e ementFt(/))> E S,stem.o$t.print n(JJ)>

Ep$ ic !oid disp a,Sorted()B S,stem.o$t.print n(JKn;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;J)>

S,stem.o$t.print n(J rocess Y Frri!a Aime Y G$rst J)>

or(int , C 0> , H n$m erO rocess> ,II)B

S,stem.o$t.print n(J J I o ?,@ I JKtKtJ I arri!a Aime?,@ IJKt J

I $rstAime?,@)> E

24

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 25/54

S,stem.o$t.print n(J;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;KnJ)> E

E

". Round Ro$in Sc(eduling

e)te unul din cele mai vechi i )impli algoritmi de plani(icare preemptiveș (iec rei proce) i )e atri+uie un interval de timp numit cuant 0 5n care proce)ul )e poatee ecuta dac proce)ul nu i termin e ecu ia p n la e pirarea cuantei de timp alocate0 el va (iș ț5ntrerupt iar C&/ e)te alocat altui proce) dac proce)ul termin 5nainte de e pirarea cuantei0 )e va plani(ica alt proce) ( r a )ea tepta e pirarea cuanteiș

import a!a.$ti .Frra,Nist>import a!a.$ti . terator>import a!a.$ti .Nist>

import $nit. rameDorX.Aest ase>

c ass o in Bpri!ate int i>

p$ ic o in(int i) Bt#is.i C i>E

p$ ic int ca () Bret$rn i>EE

c ass o$nd o in Bpri!ate teratorH o inV it>pri!ate NistH o inV ist>

p$ ic o$nd o in(NistH o inV ist) Bt#is. ist C ist>it C ist.iterator()>

Ep$ ic int ne/t() B

i (Zit.#asPe/t()) Bit C ist.iterator()>Eo in ro in C it.ne/t()>

ret$rn ro in.ca ()>EE

p$ ic c ass o$nd o inAest e/tends Aest ase BNistH o inV items C neD Frra,NistH o inV()>o$nd o in ro$nd>

25

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 26/54

p$ ic !oid testOne() Bitems.add(neD o in(1))>ro$nd C neD o$nd o in(items)>assertW[$a s(1: ro$nd.ne/t())>assertW[$a s(1: ro$nd.ne/t())>E

p$ ic !oid testADo() Bitems.add(neD o in(1))>items.add(neD o in(2))>ro$nd C neD o$nd o in(items)>assertW[$a s(1: ro$nd.ne/t())>assertW[$a s(2: ro$nd.ne/t())>assertW[$a s(1: ro$nd.ne/t())>assertW[$a s(2: ro$nd.ne/t())>E

p$ ic !oid testA#ree() Bitems.add(neD o in(1))>items.add(neD o in(2))>items.add(neD o in(3))>ro$nd C neD o$nd o in(items)>assertW[$a s(1: ro$nd.ne/t())>assertW[$a s(2: ro$nd.ne/t())>assertW[$a s(3: ro$nd.ne/t())>assertW[$a s(1: ro$nd.ne/t())>assertW[$a s(2: ro$nd.ne/t())>assertW[$a s(3: ro$nd.ne/t())>EE

"./ Round Ro$in

● a &oritm$ este $-or de imp ementat p ani'cator$ !a men ine o istă a procese or ce pot ' r$ ate (read,) a e/pirarea c$antei: proces$ acti! !a ' trec$t a s r-it$ istei: iar

$rmător$ proces din istă !a o ine ● mean t$rnaro$nd time de e/. procese e F:G: :L c$ timpi de e/ec$ ie 4:2:5:3:mttC10.75> iar pentr$ 6:1:4:2: mttC8.25

".0 Alegerea cuantei

● o pro emă importantă +n proiectare este a e&erea c$antei● com$tarea procese or necesită $n an$mit inter!a de timp pentr$sa !area -i +ncărcarea re&istre or: act$a i%area ta e e or -i iste or: etc.● de e/. c$antă 20ms: timp de com$tare 5ms tCV o!er#ead de 20 pentr$ a mări e'cien a tre $ie mic-orat o!er#ead$ : de e/. c$antă

495ms: o!er#ead 1 dar c$ c$anta mare timp$ de răsp$ns cre-te" de e/. 10 $ti i%atori apasăWnter: $ tim$ !a tre $i să a-tepte 5s

26

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 27/54

● sta i irea $nei c$ante mici !a cond$ce a com$tări m$ te scă% nde'cien a ● sta i irea $nei c$ante mari ca$%ea%ă $n timp de răsp$ns mare pentr$$ti i%ator● !a ori e $%$a e pentr$ c$ante s$nt 1;100ms

● in orma ii despre e'cien ăUprocUcp$in oUprocUstatUprocUsc#edstat

". Priorit sc(eduling

● +n ca%$ o$nd o in: procese e a!ea$ aceea-i prioritate● $neori +nsă !a tre $i să inem cont de priorită i e +n re%o !area $norpro eme● 'ecărei proces i se a ocă o prioritate● a $n moment dat !a ' r$ at proces$ ce mai prioritar● pentr$ a pre!ine r$ area inde'nită a procese or prioritare sc#ed$ er$poate descre-te prioritatea proces$ $i acti! a 'ecare +ntrer$pereFtri $ireapriorită i or● atri $ire statică prioritate constantă de'nită pentr$ $n proces sa$ pentr$ $ti i%ator$ careporne-te proces$● atri $ire dinamică modi'care a priorită ii +n timp$ r$ ării de e/. comanda nice permite $n$i $ti i%ator să;-i descrească prioritateapentr$ a ' dră&$ c$ cei a i SO poate acorda prioritate mai mare $n$i proces care a-teaptă oartem$ t pentr$ O -i $ti i%ea%ă oarte p$ in

$include%stdio&!' struct proc

{int id ;int pri ;int arrival ;int burst ;int rem ;int wait ;int start ;int finis! ;int turnaround ;float ratio ;

( process [)*]# temp ;

int c!+process ,int-;int ne.tprocess ,-;void displa/ ,-;

27

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 28/54

int no # n ; main ,-{

int i # a # j # + #time0*;

printf,1 \n \n 222P3IO3IT4 SC56789I: 222 \n \n 1-;printf,1 \n \n 6nter t!e number of processes< 1-;scanf,1=d1# >n -;

for, i 0 ); i %0 n ; i ??-{

process [ i ] &id 0 i ;

printf,1 \n\n 6nter t!e arrival time for process =d< 1# i -;scanf,1=d1# >, process [ i ] &arrival--;

printf,1 \n 6nter t!e burst time for process =d< 1# i -;scanf,1=d1# >, process [ i ] &burst--;

printf,1 \n 6nter t!e priorit/ of t!e process =d<1# i -;scanf,1=d1# > , process [ i ] &pri--;

process [ i ] &rem 0 process [ i ] &burst;

(

for, i 0 ); i %0 n ; i ??-{

for, j 0 i ? ); j %0 n ; j ??-{

if, process [ i ] &arrival ' process [ j ] &arrival-{

temp 0 process [ i ];process [ i ] 0 process [ j ];process [ j ] 0 temp ;

((

(

no 0 *;j 0 );

printf,1 \n \n C!oices<1-;printf,1 \n \n )&Preemptive Priorit/ Sc!edulin 1-;printf,1 \n \n @&:on Preemptive Priorit/ Sc!edulin 1-;

printf,1 \n \n 6nter /our c!oice<1-;scanf,1=d1# >a -;

switc!, a - { case )<

{w!ile, c!+process , n - 00 )-{

if, process [ no ? )] &arrival 00 time-{

no ??;

if, process [ j ] &rem00*- process [ j ] &finis!0time;

j 0 ne.tprocess ,-;(

28

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 29/54

if, process [ j ] &rem A0 *-{

process [ j ] &rem22;for, i 0 ); i %0 no ; i ??-{

if, i A0 j >> process [ i ] &rem A0*-

process [ i ] &wait??;(

(else{

process [ j ] &finis! 0 time;j 0 ne.tprocess ,-;time 22;+ 0 j ;

(

time??;(process [ + ] &finis! 0 time;

(

case @< {

process [)] &start 0 process [)] &arrival;

w!ile, c!+process , n - 00 )-{

if, process [ no ? )] &arrival 00 time-no ??;

if, process [ j ] &rem A0 *-{

process [ j ] &rem22;for, i 0 ); i %0 no ; i ??-{

if, i A0 j >> process [ i ] &rem A0*-

process [ i ] &wait??;(

(else{

process [ j ] &finis! 0 time;j 0 ne.tprocess ,-;time 22;process [ j ] &start 0 time ? );

(

time??;(process [ j ] &finis! 0 time;

((

displa/ ,-;

(

int c!+process ,int s -

29

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 30/54

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 31/54

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 32/54

● dacă toate procese e pot ' p ani'cate" mt tC 4.4

import a!a.io.^>c ass s Bp$ ic static !oid main (Strin& ar&s?@)t#roDs OW/ceptionBint i: :temp>G$_ered eader C neD G$_ered eader(neD np$tStreameader(S,stem.in))>S,stem.o$t.print n(JWnter no. o processesJ)>int pC nte&er.parse nt( .readNine())>int $rst?@CneD int?p@>S,stem.o$t.print n(JWnter t#e $rst time or eac# processJ)>or(iC0>i $rst? I1@)BtempC $rst? I1@>$rst? I1@C $rst? @>$rst? @Ctemp>EEEint ar!?@ C neD int?p@>S,stem.o$t.print n(JWnter arri!a time or eac# processJ)>or(iC0>i ar!?i@C nte&er.parse nt( .readNine())>int Dait?@ C neD int?p@>S,stem.o$t.print n(JTait time or eac# process "J)>S,stem.o$t.print n(J rocess 0 JIDait?0@IJ $nitsJ)>or(iC1>i BDait?i@Car!?i;1@I $rst?i;1@IDait?i;1@;ar!?i@>S,stem.o$t.print n(J rocess JIiIJ JIDait?i@IJ $nitsJ)>EEE

Plani#care garantat!

● o a ordare di erită de p ani'care" se ace promisi$ni $ti i%ator$ $i e&at de mărimea timp$ $i atri $it

32

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 33/54

de e/emp $ dacă s$nt n $ti i%atori o&a i +n sistem: 'ecare !a primi 1Undin timp$ ● sistem$ ca c$ ea%ă mere$ c t timp a $ti i%at 'ecare $ti i%ator -i

+mparte c$ n: apoi ca c$ ea%ă raport$ +ntre timp$ $ti i%at -i timp$ de a$ tim$ ca c$

● r$ ea%ă tot timp$ proces$ c$ ce mai mic raport

$olitici i mecanismeș

● nici $n$ din a &oritmii pre%enta i n$ accepta$ in orma ii de a procese e$ti i%ator: pe care să e o osească +n $area deci%ii or sc#ed$ er$ n$ !a $a +ntotdea$na deci%ia cea mai $nă

● so $ ia este separarea mecanism$ $i p ani'cării de po itica p ani'cării● mecanism$ este rea i%at de Xerne : dar po itica este sta i ită deproces$ $ti i%ator● a &oritm$ de p ani'care este parametri%at +ntr;$n an$me mod ast e

+nc t parametrii să pot ' seta i de procese e $ti i%ator Xerne $ o ose-te priorit, sc#ed$ in& -i asi&$ră $n ape sistem prin care$n proces poate seta priorită i e procese or 'i: ast e proces$ părinte !acontro a p ani'carea procese or 'i

T o>level sc'edulin!● p nă ac$m am pres$p$s că procese e read, se a*ă +n memorie● dacă +nsă n$ disp$nem de s$'cientă memorie: $ne e din procese read,!a tre $i p asate pe disc● com$tarea procese or de pe disc !a $a $n timp m$ t mai mare dec tce or din memorie● !om $ti i%a $n sc#ed$ er c$ 2 ni!e eADo; e!e sc#ed$ in&● ini ia o s$ m$ ime a procese or read, !or ' +ncărcate +n memorie● sc#ed$ er$ !a p ani'ca n$mai aceste procese pentr$ o perioadă de

timp● periodic $n sc#ed$ er de ni!e +na t este $ti i%at pentr$ a e iminaprocese e din memorie (care s$nt de m$ t timp aco o) -i a +ncărca procesenoi de pe disc● apoi se o ose-te sc#ed$ er$ de ni!e os pentr$ p ani'care +ntre acesteprocese noi riterii e o osite de sc#ed$ er$ de ni!e +na t● c t de m$ t a stat $n proces +n memorie sa$ pe disc● c t timp a $ti i%at proces$● c t de mare este proces$● care este prioritatea proces$ $i

import a!a.$ti .NinXedNist>

c ass Aest B p$ ic static !oid main(Strin& ar&s?@) B

33

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 34/54

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 35/54

,.1 5odelul pro$lemei de plani#care

Elemente de teoria ordonanţei " pro+lem de ordonan6are con)t 5n )ta+ilirea unei ordini de e(ectuare a opera6iilor activit 6ilor unui proiect0 a)t(el ca interdependen6ele dintre ele ) (ie re)pectate 5n cadrulre)ur)elor di)poni+ile Ei durata total de e ecu6ie a ace)tuia ) (ie minim .

&entru a putea concreti,a de(ini6ia de mai )u)0 tre+uie clari(icate no6iunile de proiect0

opera6ii activit 6i ale ace)tuia0 interdependen6e 5ntre opera6ii Ei re)ur) a proiectului.&rin%roiect vom 5n6elege o ac6iune de mare amploare )au un proce) comple de)tinat

atingerii unui )cop +ine preci,at. !a un proiect deo)e+im urm toarele caracteri)tici: uno+iectiv care poate (i un produ)0 o cantitate de in(orma6ii )au un re,ultat de naturorgani,atoric 0 un an)am+lu de activit 6i )u+ac6iuni0 )u+proce)e0 opera6ii 0 corelate logic Eitehnologic0 a c ror reali,are permite atingerea )copului propu) Ei un proce) tehnologic princare )e preci,ea, intercondi6ion rilor 5ntre activit 6i0 intere) nd 5n )pecial ordinea de e ecu6ie

a ace)tora.&entru a permite o anali, am nun6it a de)( Eur rii lui0 o alegere a variantelor optime

de e ecu6ie Ei un control continuu al evolu6iei )ale0 tre+uie ) de)compunem proiectul 5n p r6icomponente la un nivel care ) permit tratarea unitar a (iec rei p r6i Ei )ta+ilireacone iunilor 5ntre ace)tea. Ace)te componente )e nume)c opera6ii )au activit 6i.

" activitate e)te o parte di)tinct dintr un proiect0 un )u+proce) preci) determinat0 carecon)um timp Ei re)ur)e. Qom pre)upune 5n continuare c activit 6ile au urm toarele

propriet 6i: (iecare activitate e)te indivi,i+il nu )e mai de)compune 5n )u+activit 6i 0 (iecareactivitate are o durat cuno)cut Ei0 odat 5nceput 0 nu mai poate (i 5ntrerupt .

Dintre intercondi6ion rile interdependen6ele dintre activit 6i0 ne intere)ea, 0 5n)pecial0 cele temporale0 numite rela6ii de preceden6 0 care pot (i de trei tipuri:

1. #ela6ii de preceden6 de tip(terminare ) nceput( ) Ace)t tip e)te cel mai (recvent5nt lnit Ei )punem c o activitate A precede activitatea printr o interdependen6 detip bterminare [ 5nceputb dac activitatea nu poate 5ncepe dec t dup un interval detimp tA de la terminarea activit 6ii A. Ace)t interval poate (i egal Ei cu ,ero0 ca, 5ncare )punem c activitatea A precede direct activitatea .

35

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 36/54

2. De tip( nceput ) nceput( [ Ace)t tip e)te (recvent 5nt lnit Ei )punem c o activitate A precede activitatea printr o interdependen6 de tip b5nceput [ 5nceputb dacactivitatea nu poate 5ncepe dec t dup un interval de timp tA de la 5ncepereaactivit 6ii A. Ace)t interval poate (i chiar mai mare dec t durata activit 6ii A0 ca, 5ncare avem de (apt o dependen6 de tipul bterminare [ 5nceputb0 put nd chiar privi primul tip ca un ca, particular al celui de al doilea.

3. De tip bterminare [ terminareb. <punem c o activitate A precede activitatea printr ointerdependen6 de tip bterminare [ terminareb dac activitatea nu )e poate terminadec t dup un interval de timp tA de la terminarea activit 6ii A )au c activitatea Atre+uie terminat cu cel pu6in tA unit 6i de timp 5naintea termin rii activit 6ii .

&rin durat total de e ecu6ie a unui proiect 5n6elegem intervalul de timp 5n care )ee(ectuea, toate activit 6ile ace)tuia0 re)pect nd toate interdependen6ele dintre activit 6i.

A programa un proiect 5n)eamn a )ta+ili termenele de 5ncepere pentru (iecareactivitate 5n parte0 6in nd )eama de re)tric6iile impu)e de proce)ul tehnologic0 durateleactivit 6ilor Ei re)ur)ele di)poni+ile. &entru un proiect dat0 e i)t un num r enorm de program ri admi)i+ile. /n intere) deo)e+it pre,int programul optim0 adic acel programcare0 pe de o parte0 )ati)(ace re)tric6iile impu)e iar0 pe de alt parte0 optimi,ea, un anumit

criteriu de e(icien6 economic .Criteriul de optimi,are nu e)te acelaEi pentru toate proiectele0 el e)te )ta+ilit pentru

(iecare ca, 5n parte Ei de(ineEte o+iectivele ma ore ale conducerii proiectului. 7n (unc6ie deace)te o+iective0 criteriul poate (i durata total minim 0 co)tul total minim0 (olo)irea c t maiuni(orm a re)ur)elor )au o )inte, a ace)tora. Deci0 programul optim e)te acea de)( Eurare a proiectului0 preci,at prin termenele de 5ncepere ale activit 6ilor0 care conduce la o e(icien6ma im . JVK

&ro+lema plani(ic rii implic utili,area unui gra( orientat0 aciclic0 care ) con6in ocolec6ie de activit 6i Ei datele re(eritoare la rela6iile lor de preceden6 . <copul plani(ic riiactivit 6ilor e)te de a elimina momentele din proiect ( r activit 6i Ei de a optimi,a organi,areaactivit 6ilor0 a)t(el 5nc t rela6iile de preceden6 ) )e 5ndeplinea)c 0 iar timpul total de e ecu6ie) (ie minim. J1FK 7n general0 pro+lema plani(ic rii re)ur)elor e)te de dou tipuri: )tatic Eidinamic .

7n plani(icarea )tatic 0 caracteri)ticile pro+lemei0 cum ar (i durata unei activit 6i0

leg turile0 preceden6ele )au )incroni,area )unt cuno)cute 5nainte de a (i e ecutate. &e de alt parte0 5n plani(icarea dinamic 0 )unt cuno)cute pu6ine activit 6i Ei deci,iile cu privire la

36

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 37/54

ace)tea )unt luate pe pacrur). 7n continuare e)te pre,entat modelul )tatic de programare are)ur)elor. J11K

Analiza resurselor Dac din punct de vedere al condi6ion rilor de tip preceden6 temporale e i)ten6a

activit 6ilor paralele e)te corect din punct de vedere logic0 put nd e i)ta oric te activit 6i care)e de)( Eoar 5n acelaEi timp0 dac nu )e intercondi6ionea, 5ntre ele0 nee i)t nd nici odi(eren6 5ntre ,ilele proiectului0 din punct de vedere practic0 e)te clar c o ,i 5n care )ede)( Eoar 5n acelaEi timp 1F activit 6i e)te mult mai inten) din punct de vedere al organi, riiEi aprovi,ion rii cu re)ur)e dec t o ,i 5n care )e de)( Eoar o )ingur activitate. Deci0 dac )e

6ine cont doar de condi6ion rile temporale pot ap rea de,echili+re (oarte mari 5n de)( Eurarea proiectului Ei;)au pot ap rea ,ile 5n care nece)arul de re)ur)e ar (i mai mare dec t di)poni+ilulace)tora.

Din cele )pu)e mai )u)0 )e de)prinde (aptul c e i)t cel pu6in dou pro+lemeimportante legate de re)ur)ele unui proiect:

%ro"lema alocării resurselor0 5n care )e 5ncearc programarea activit 6ilor 5n aEa (el5nc t 5n nici o ,i ) nu )e dep Eea)c di)poni+ilul din nici o re)ur)

%ro"lema nivelării resurselor0 5n care )e 5ncearc programarea activit 6ilor 5n aEa(el 5nc t 5n toate ,ilele ) )e (olo)ea)c cam aceiaEi cantitate de re)ur)e )au0 alt(el )pu)0 )umavaria6iilor de la o ,i la alta ) (ie minim .

Anali,a 5n cele dou pro+leme de mai )u) )e (ace 5n general pentru re)ur)e re(olo)i+ile0care nu )e con)um 5n timp0 adic cele care0 dup terminarea activit 6ii la care au (o)t alocate0)e pot (olo)i la alt activitate. #e)ur)ele de ace)t tip )unt 5n principal (or6a de munc EimaEinile Ei utila ele. JVK

,.2 'escrierea matematic! a pro$lemei/n proiect va con)ta 5ntr un )et de activit iț * + ,-. /. 000. n! . Activitatea- i activitateaș

n repre,int 5nceputul proiectului0 re)pectiv )( r itul proiectului.ș

37

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 38/54

&entru (iecare activitate &vom nota cu 'red & mul imea activit ilor care tre+uie ) )eț ț

(inali,e,e 5nainte ca & ) 5nceap . %lementele mul imiiț 'red & )unt numite predece)ori direc i aiț

lui &. A)t(el0 e)te adev rat urm toarea a(irma ie generali,at :ț

" activitate i e)te numit predece)oare activit iiț & dac e i)t

.Activitateai e)te un )ucce)or imediat al activit iiț & dac & e)te un predece)or imediat

al activit iiț i. $ul imea tuturor )ucce)orilor o vom nota cuț Suc &. A)t(el0 activitatea- va (i predece)or pentru toate activit ile0 re)pectiv activitateaț n va (i )ucce)or pentru toateactivit ile proiectului.ț

/n alt tip de re)tric ie )e re(er la re)ur)e. <unt de(inite un num r deț 1 tipuri dere)ur)e re(olo)i+ile. " cantitate limitat din U re)ur)e0 notat cu 2 k 0 e)te di)poni+il 5n (iecareunitate de timp. 7n timpul de)(a ur rii unei activit iș ț &0 )unt nece)arer &k unit i de re)ur)ț

. pe parcur)ul (iec rei perioade te timp de duratd & e i)t un )ingur mod dede)( urare a activit ilor . <e con)ider 0 de a)emenea0 ca activit ile nu pot (i oprite o dat deț ț ț

au 5nceput.&arametri 2 k 00 r k 0 d & )e pre)upun a (i cuno)cu i )au determina i0 de tip 5ntreg. Deț ț

a)emenea0r -k 9 r nk 9 F iș d -& 9 d n& 9 F0 pentru to iț .&ro+lema plani(ic rii acivit ilor i re)ur)elor )e poate re,olva dac timpul de 5nceputț ș

)au timpul de )( r it a (iec rei activit i )ati)(ace re)tric iile de preceden i cele re(eritoareș ț ț ț ș

la re)ur)e0 a)t(el 5nc t timpul total de de)( urare al proiectului ) (ie minim.J12Kș

/n e emplu de proiect0 de(init pe +a,a nota iilor de mai )u)0 )e reg )e te 5n (igura 3.1.ț ș

Ace)t proiect are n 9 - activit i i U 9 1 re)ur)e reutili,a+ile0 cu 2 unit i capacitate.ț ș ț

38

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 39/54

7n (igura 3.20 o )ecven po)i+il e)te repre,entat cu o durat total de 8 unit i deț ț

timp0 5n timp ce 5n (igura 3.3 e)te repre,entat o aran are a activit ilor ce determin o duratț

total de doar * unit i de timp. Ace)te )ecven e )unt repre,entate cu a utorul diagramei Gantt.ț ț

A a ori,ontal repre,int timpul0 iar a a vertical utili,area re)ur)elor. Dac ar (i e i)tat maimulte tipuri de re)ur)e0 era nece)ar reali,area unei diagrame pentru (iecare re)ur) 5n parte.iecare dreptunghi repre,int o activitate. !ungimea dreptunghiului repre,int durataactivit ii0 iar 5n l imea arat num rul de unit i de re)ur) (olo)it pentru activitate.ț ț ț

39

<i&. 3.1

2U1

1U2

1U1

0U0

2U1

1U2

1

2 3

4 5 6

7

0U0

diUr

:1

i

` C 1: 1

C 2

4, 3

2 6

<i&.3.2

45 3

2

6

<i&.3.3

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 40/54

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 41/54

/n a)t(el de ta+el tre+uie ) con6in cel pu6in urm toarele elemente:→ activit 6i: 5n acea)t coloan )e enumer activit 6ile proiectului0 (iind pu)e 5n eviden6

printr o denumire )au printr un )im+ol codul activit 6ii→

condi6ion ri: )e preci,ea, 0 pentru (iecare activitate0 activit 6ile imediat precedente0 prin )im+olurile lor activit 6ile de )tart nu au activit 6i precedente0 5n c )u6 (iindtrecut o liniu6

→ durata: pentru (iecare activitate )e preci,ea, durata de e ecu6ie0 5ntr o anumit unitate

de m )ur . Durata unei activit 6i e)te o con)tant .

$odelele de anali, a drumului critic )e +a,ea, pe repre,entarea proiectului printr un

gra(0 elementele ta+elului a)ociat ace)tuia (iind )u(iciente pentru a con)trui gra(ulcore)pun, tor.% i)t mai multe moduri de a repre,enta un proiect printr un gra(0 cele mai cuno)cute

(iind pre,entate mai o):

A. Metoda C"M Critical "at# Met#od!$etoda C&$ e)te un procedeu de anali, a drumului critic 5n care )ingurul parametru

anali,at e)te timpul Ei 5n repre,entarea gra(icului re6ea )e 6ine )eama de urm toarele conven6ii:→ (iec rei activit 6i i )e a)ocia, un )egment orientat numit arc0 de(init prin capetele )ale0

a)t(el (iecare activitate identi(ic ndu )e printr un arc→ (iec rui arc i )e a)ocia, o valoare egal cu durata activit 6ii pe care o repre,int

→ condi6ionarea a dou activit 6i )e repre,int prin )ucce)iunea a dou arce adiacente.

'odurile gra(ului vor repre,enta momentele caracteri)tice ale proiectului0 repre,ent nd)tadii de reali,are a activit 6ilor adic terminarea uneia )au mai multor activit 6i Ei;)au5nceperea uneia )au mai multor activit 6i .

&rocedeul C&$ )e +a,ea, pe e i)ten6a unei core)ponden6e +ipartide 5ntre elementeleunui proiect activit 6i0 evenimente Ei elementele unui gra( arce Ei noduri . <e o+6ine orela6ie model o+iect0 care pune 5n eviden6 particularit 6ile de o mare 5n)emn tate practic 0 5n)pecial0 propriet 6ile de )ucce)iune temporal .

&rintre avanta ele metodei C&$ Ei 5n general ale anali,ei drumului critic eviden6iem:→ determinarea cu anticipa6ie a duratei de e ecu6ie a proiectelor comple e→ pe timpul de)( Eur rii proiectului permite un control permanent al e ecu6iei

ace)tuia41

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 42/54

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 43/54

7n practica managementului ac6iunilor economice comple e prim metodele ADC0nivelul de detaliere 5n activit 6i a proiectelor depinde de )copul urm rit coordonare dean)am+lu )au conducere de detaliu 0 de timpul avut la di)po,i6ie pentru ela+orarea gra(urilor0de )pecialiEtii di)poni+ili etc.

Dac gra(ul )umar care )e 5ntocmeEte pentru orientarea general a echipei deconducere a ac6iunii gra( director e)te totdeauna nece)ar0 c nd )e (ace trecerea la conducereade am nunt0 )unt tot at t de nece)are gra(urilor detaliate.

7n general gra(urile detaliate )e (ac pe p r6i din ac6iunea comple 0 numite o+iective)au o+iecte. A)t(el0 dac ne re(erim de e emplul la un proiect de con)truc6ii0 gra(ulcore)pun, tor 5ntregului proiect poate (i divi,at 5n gra(uri pe o+iect0 cum ar (i:

→ gra(ul proiect rii

→ gra(ul organi, rii Eantierului

→ unul )au mai multe gra(uri pentru lucr ri de drumuri

→ mai multe gra(uri pentru lucr ri de re6ele ap 0 canal a+ur0 electrice etc.

→ mai multe gra(uri pentru lucr ri de con)truc6ii monta c te unul pentru (iecare hal

)au cl dire etc.Gra(urile pe o+iect au individualitatea lor Ei )e tratea, ca entit 6i de programare

di)tincte 5n acelaEi timp 5n) 0 tre+uie g ndit coordonarea lor 5n cadrul ac6iunii comple e dincare (ac parte. 7n ace)t )cop0 dup 5ntocmirea )eparat a gra(urilor pe o+iect apare nece)itateaa)am+l rii lor 5ntr un tot0 care con)tituie!raful inte!rat .

7n (oarte multe ca,uri din practic 0 num rul activit 6ilor care re,ult prin integrareamai multor gra(uri pe o+iect e)te con)idera+il0 put nd a unge la ,eci de mii0 ceea ce dep EeEtede multe ori po)i+ilitatea de a le calcula Ei urm ri0 chiar cu a utorul calculatoarelor puternice.

Cu at t mai pu6in ar (i po)i+il cuprinderea )intetic a unui a)emenea gra( la nivelul

conducerii 5ntregii ac6iuni.&entru ace)te motive a (o)t nece)ar g )irea unui mi loc de a reduce gra(ul integrat0 p )tr ndu i 5n acelaEi timp principalele caracteri)tici. Acea)t opera6ie poart numele decondensare iar re,ultatul aplic rii ace)teia a)upra unui gra( )e numeEte!raf condensat.

(. Actualizarea grafurilor ADC

43

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 44/54

7n practica reali, rii ac6iunilor comple e0 )unt numeroa)e ca,urile c nd e)tim rileini6iale de durat ale activit 6ilor nu pot (i re)pectate. Apare a)t(el nece)itatea ca0 periodic0 ))e e amine,e modul cum )e reali,ea, termenele calculate0 5n )copul punerii 5n eviden6 aeventualelor 5nt r,ieri Ei a lu rii m )urilor de recuperare a ace)tora.

Acea)t activitate poart numele de actuali,are a gra(urilor iar noul gra( )e numeEte!raf actuali;at .

). *ptimizări cost+durată%)timarea duratelor ac6iunilor comple e pro+lema ADC;TI$& prin metodele e pu)e

mai 5nainte0 deEi repre,int o pro+lem deo)e+it de important din punct de vedere economic0

nu e)te nici pe departe )ingurul a)pect care poate (i urm rit cu a utorul ace)tor metode." alt pro+lem 5n care pot (i utili,ate in)trumentele ADC )unt cele de anali, a

co)tului e ecu6iei ac6iunilor comple e0 5n (unc6ie de durata de e ecu6ie a ace)teia.%)te evident c 0 5n (unc6ie de preg tirea celor care e(ectuea, lucrarea0 de tehnologia

(olo)it 0 de oportunit 6ile momentului etc0 durata de e ecu6ie a unei ac6iuni comple e poatevaria0 e i)t nd totuEi o durat minim po)i+il Tmin Ei una ma im Tma accepta+il .

%vident0 durata lucr rii are numeroa)e implica6ii a)upra co)tului0 drept pentru care

pre,int un deo)e+it intere) determinarea acelei durate de e ecu6ie0 intermediare lui Tmin EiTma 0 c reia 5i core)punde co)tul minim.

,. &raficul &antt /n in)trument de mare utilitate 5n anali,a drumului critic 5l con)tituie gra(icul

calendari)tic tip Gantt0 ap rut la 5nceputul )ecolului. Gra(icul diagram Gantt e prim la)cara timpului0 prin linii ori,ontale0 durata activit 6ilor0 Ei prin linii 5ntrerupte de e emplu

re,ervele de timp. Gra(icul Gantt pre)upune divi,area ac6iunii comple e pe care o repre,int proiectul0 5n p r6i componente activit 6i Ei eEalonarea ace)tora 5n timp0 6in nd )eama de)ucce)iunea tehnologic 0 termene impu)e0 re)ur)e etc.

Dac e)te 5ntocmit 5n urma unei anali,e temeinice0 gra(icul Gantt o(er in(orma6ii +ogate Ei e trem de )uge)tiv pre,entate0 privind de)( Eurarea lucr rilor0 precum Ei o )erie dein(orma6ii derivate0 privind eEalonarea re)ur)elor (or6 de munc 0 materii prime0 materiale0(onduri + neEti . Ace)te avanta e )cad dac 0 datorit (ie amplorii ac6iunii con)iderate0 (ie

nivelului de detaliere dorit0 num rul activit 6ilor ce compun gra(icul Gantt creEte mult0a ung nd la c teva )ute )au mii.

44

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 45/54

Gra(icul Gantt e prim la )cara timpului un program de ordonan6are. A)t(el0 avemgra(icul Gantt la termenele cele mai devreme )au gra(icul Gantt la termenele cele mai t r,ii.

-. Analiza resurselor Dac din punct de vedere al condi6ion rilor de tip preceden6 temporale e i)ten6a

activit 6ilor paralele e)te corect din punct de vedere logic0 put nd e i)ta oric te activit 6i care)e de)( Eoar 5n acelaEi timp0 dac nu )e intercondi6ionea, 5ntre ele0 nee i)t nd nici odi(eren6 5ntre ,ilele proiectului0 din punct de vedere practic0 e)te clar c o ,i 5n care )ede)( Eoar 5n acelaEi timp 1F activit 6i e)te mult mai inten) din punct de vedere al organi, riiEi aprovi,ion rii cu re)ur)e dec t o ,i 5n care )e de)( Eoar o )ingur activitate. Deci0 dac )e

6ine cont doar de condi6ion rile temporale pot ap rea de,echili+re (oarte mari 5n de)( Eurarea proiectului Ei;)au pot ap rea ,ile 5n care nece)arul de re)ur)e ar (i mai mare dec t di)poni+ilulace)tora.Din cele )pu)e mai )u)0 )e de)prinde (aptul c e i)t cel pu6in dou pro+lemeimportante legate de re)ur)ele unui proiect:%ro"lema alocării resurselor0 5n care )e 5ncearc programarea activit 6ilor 5n aEa (el 5nc t 5n nici o ,i ) nu )e dep Eea)c di)poni+ilul din nici ore)ur) [ iș %ro"lema nivelării resurselor0 5n care )e 5ncearc programarea activit 6ilor 5n aEa(el 5nc t 5n toate ,ilele ) )e (olo)ea)c cam aceiaEi cantitate de re)ur)e )au0 alt(el )pu)0 )uma

varia6iilor de la o ,i la alta ) (ie minim .Tre+uie ( cut Ei o+)erva6ia c anali,a 5n cele dou pro+leme de mai )u) )e (ace 5n

general pentru re)ur)e re(olo)i+ile0 care nu )e con)um 5n timp0 adic cele care0 dupterminarea activit 6ii la care au (o)t alocate0 )e pot (olo)i la alt activitate. #e)ur)ele de ace)ttip )unt 5n principal (or6a de munc Ei maEinile Ei utila ele.

. Metoda "E/0

$etodele C&$ Ei $&$ anali,ate anterior (urni,ea, 0 aEa cum ) a v ,ut0 in(orma6iicare )unt utile 5n proce)ul de conducere0 5n) ele nu 6in )eama de po)i+ilele varia6ii aleduratelor de e ecu6ie ale activit 6ilor.

$etoda &%#T 5ncearc ) corecte,e ace)t lucru. 7n ace)t )cop metoda permitecalcularea timpului mediu de terminare a unui proiect0 identi(icarea activit 6ilor critice0 precum Ei e)timarea pro+a+ilit 6ilor de reali,are a termenelor plani(icate. &entru c 5n practic 0 5n (oarte multe programe din domeniul cercet rii Ei de,volt rii0 duratele activit 6ilor

)unt in)u(icient cuno)cute )au chiar incerte prin con)iderarea conceptelor )tati)tice0 durateleactivit 6ilor )unt con)iderate varia+ile aleatoare caracteri,ate prin media Ei di)per)ia lor. JVK

45

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 46/54

Aplicatie

46

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 47/54

&rogramarea ocuparii unei camere de o per)oana printr un algoritm de tip greedy.Aplicatie reali,ata in ava.

import ava.io.import ava.util.

pu+lic cla)) <chedule=

private Array!i)tR%ventS event) private int num%vent)

pu+lic <chedule=

event) 9 ne Array!i)tR%ventSnum%vent) 9 F

>

pu+lic int get'um%vent)=

return num%vent)>

; incearca )a programe,e un eveniment [ daca )e poate programa e)te pu) in li)ta array cuevenimente ;

pu+lic void )chedule%vent %vente=

intJK con(lict!i)t 9 con(lict e

; i( event e canft +e added0 u)t return ;i( con(lict!i)t 99 null

return

; remove any event) that con(lict ;(or int i9con(lict!i)t.length 1 iS9F i=

event).remove con(lict!i)tJiKnum%vent)>

; add thi) event to the li)t ;event).add enum%vent)

>

; e punerea datelor intr un ta+le ; pu+lic <tring to<tring=

47

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 48/54

int ma %vent!ength0 ma Contact!engthma %vent!ength 9 ma Contact!ength 9 1

; convert array li)t to array0 get ma length) ;%ventJK event)Arr 9 ne %ventJnum%vent)K

(or int i9F iRnum%vent) i=event)ArrJiK 9 event).get ii( event)ArrJiK.get'ame .length S ma %vent!ength

ma %vent!ength 9 event)ArrJiK.get'ame .lengthi( event)ArrJiK.getCoordinator .get'ame .length S

ma Contact!engthma Contact!ength 9

event)ArrJiK.getCoordinator .get'ame .length>; )ort event) +y )tarting time ;Array).)ort event)Arr

<tring ) 9 bb; output ta+le ;) 9 b%ventb(or int i9b%ventb.length iRma %vent!ength 1 i

) 9 b b) 9 b<tart Time %nd Time "rgani,erb(or int i9b"rgani,erb.length iRma Contact!ength 1 i

) 9 b b) 9 bAge nb(or int i9F iRma %vent!ength i

) 9 b b) 9 b b(or int i9F iRma Contact!ength i

) 9 b b) 9 b nb(or int i9F iRnum%vent) i=

) 9 event)ArrJiK.get'ame(or int 9event)ArrJiK.get'ame .length Rma %vent!ength

) 9 b b) 9 b b

<tring.(ormat bNF2db0event)ArrJiK.get<tartTime .getYour) b:b <tring.(ormat bNF2db0event)ArrJiK.get<tartTime .get$inute)

) 9 b b <tring.(ormat bNF2db0event)ArrJiK.get inTime .getYour) b:b <tring.(ormat bNF2db0event)ArrJiK.get inTime .get$inute)

) 9 b b event)ArrJiK.getCoordinator .get'ame(or int 9event)ArrJiK.getCoordinator .get'ame .length

Rma Contact!ength

) 9 b b) 9 b b event)ArrJiK.getCoordinator .getAge) 9 b nb

48

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 49/54

>return )

>

; determinarea unui con(lict intre evenimente ;

private intJK con(lict %vent e=

int thi)<tartTime 9 e.get<tartTime .totalminute)int thi)%ndTime 9 e.get inTime .totalminute)Array!i)tRIntegerS con(lict!i)t 9 ne Array!i)tRIntegerS

(or int i9F iRevent).)i,e i=

int that<tartTime 9 event).get i .get<tartTime .totalminute)int that%ndTime 9 event).get i .get inTime .totalminute)

; i( the event.get i ha) a con(licting time ;i( thi)<tartTime R that<tartTime \\ thi)%ndTime S

that<tartTime thi)<tartTime S9 that<tartTime \\ thi)%ndTime R9

that%ndTime thi)<tartTime R that%ndTime \\ thi)%ndTime S9

that%ndTime thi)<tartTime R9 that<tartTime \\ thi)%ndTime S9

that%ndTime=

; i( thi) event) age i) greater0 add thi) event tocon(lict!i)t ;

i( e.contactI)"lder event).get icon(lict!i)t.add i

el)ereturn null

>>

; put con(lict) in intJK0 return ;

intJK c! 9 ne intJcon(lict!i)t.)i,e K(or int i9F iRc!.length ic!JiK 9 con(lict!i)t.get i

return c!>

; metoda principala ;

pu+lic )tatic void main <tringJK arg) thro ) ile'ot ound% ception=

<canner )tdIn 9 ne <canner <y)tem.in<y)tem.out.print bInput (ileS b<tring (ileIn 9 )tdIn.ne t

49

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 50/54

<canner (In 9 ne <canner ne ile (ileInint n 9 (In.ne tInt(In.ne t!ine ;; u)ed to get rid o( ne line a(ter n<chedule )ched 9 ne <chedule

; programarea evenimentului ;(or int i9F iRn i=

<tring event'ame 9 (In.ne t!ineTime2 )tartTime 9 ne Time2 (In.ne tInt 0(In.ne tInt(In.ne t!ineTime2 (ini)hTime 9 ne Time2 (In.ne tInt 0(In.ne tInt(In.ne t!ine<tring eventContact'ame 9 (In.ne t!ineint a 9 (In.ne tIntint m 9 (In.ne tIntint d 9 (In.ne tIntint phone'um+er 9 (In.ne tIntContact eventContact 9 ne

Contact eventContact'ame0a0phone'um+er0m0di( (In.ha)'e t!ine

(In.ne t!ine)ched.)chedule%vent ne

%vent event'ame0)tartTime0(ini)hTime0eventContact>; output )olution ;<y)tem.out.println )ched

>>

; cla)a %vent0 cla)a ce implementea,a Compara+le ;cla)) %vent implement) Compara+leR%ventS=

private <tring name private Time2 )tart0 (in private Contact coord

; create ne %vent ; pu+lic %vent <tring n0 Time2 )0 Time2 (0 Contact c=

name 9 n)tart 9 )(in 9 (coord 9 c

> pu+lic <tring get'ame=

return name>

50

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 51/54

pu+lic Time2 get<tartTime=

return )tart>

pu+lic Time2 get inTime=return (in

> pu+lic Contact getCoordinator=

return coord>

; veri(icam daca contactul recent e)te mai vechi decat cel din evenimentul e ;

pu+lic +oolean contactI)"lder %vent e=

Contact thi)Contact 9 coordContact thatContact 9 e.getCoordinator

; daca var)ta e)te mai mare ;

i( thi)Contact.getAge S thatContact.getAgereturn true

; returnea,a data recenta ;

Calendar today 9 Calendar.getIn)tanceint thi)$onth 9 today.get Calendar.$"'TY 1 ;; o(()et +y 1 )ince

A'/A# 99 Fint thi)Day 9 today.get Calendar.DA " $"'TY

; veri(icam ce ,ile au trecut ; +oolean thi) day&a))ed0 that day&a))ed thi) day&a))ed 9 that day&a))ed 9 (al)e

i( thi)Contact.get day$onth R thi)$onth thi)Contact.get day$onth 99 thi)$onth \\ thi)Contact.get dayDay R9 thi)Day thi) day&a))ed 9 true i( thatContact.get day$onth R thi)$onth

thatContact.get day$onth 99 thi)$onth \\ thatContact.get dayDay R9 thi)Day that day&a))ed 9 true

; daca var)ta e)te identica corelam programarea la ,ilele de na)tere ;

i( thi)Contact.getAge 99 thatContact.getAge=

; trei ca,uri: 1 amandoua ,ilele au trecut

51

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 52/54

2 nici una din ,ile nu a trecut "+)ervatie [ ca,urile 1 )i 2 reali,ea,a acea)i

veri(icare 3a thi) a trecut0 that nu a trecut 3+ that a trcut0 thi) nu a trecut

;; ca,urile 1 \ 2 ;

i( thi) day&a))ed \\ that day&a))ed ]thi) day&a))ed \\]that day&a))ed

=i( thi)Contact.get day$onth R

thatContact.get day$onthreturn true

i( thi)Contact.get day$onth 99thatContact.get day$onth

i( thi)Contact.get dayDay RthatContact.get dayDay

return true>

; ca,ul 3 [ returnea,a doar daca that day a trecut daca a trecut0 atunci thi) nu a trecut )i e)te mai in var)ta daca nu a trecut0 atunci thi) a trecut )i e)te mai in var)ta ;

el)e=

return that day&a))ed>

>

return (al)e>

; )ortam evenimentele programate ;

pu+lic int compareTo %vent other=i( )tart.getYour) 99 other.get<tartTime .getYour)

return )tart.get$inute) other.get<tartTime .getYour)return )tart.getYour) other.get<tartTime .getYour)

>>

Conclu;iiSisteme e de p ani'care s$nt a &oritmi de re%o !are a pro eme or

care operea%ă c$ repre%entări e/p icite a e stări or \i acti$ni or>52

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 53/54

F &oritmii de p ani'care c$ ordine partia ă s$nt e'cienti mai a esas$pra pro eme or care pot ' descomp$se>

Qra $ri e de p ani'care pot ' $ti i%ate at t ca e$ristici c t \i ca s$portpentr$ e/tra&erea directă a so $tii or de către a &oritmi prec$m Qrap#p an>

R5S i '5S

; $sor de imp ementat pe n$c ee tip comercia : care n$ s$porta in mode/p icit constran&eri de timp pentr$ set$ de procese

; $ti i%at pe scară ar&ă +n practică; de%a!anta " $ti i%area imitată a res$rse or

*'- i 77-

; mai di'ci de imp ementat; o eră o p ani'ca i itate mai $nă; a!anta " $ti i%area a capacitate ma/imă a res$rse or; imp ementat pe cate!a sisteme distri $ite de timp;rea

e/perimenta e" RartiX: S#arX : WriXa : Sprin& : artos

5U-

; mai comp e/ dpd! a imp ementarii ata de S \i WL<

; re%$ tate mai $ne a teste: +nsă necesită res$rse mai mari; detec]ia $nor erori U bratari a timpi or imită +n rea i%area p ani'carii

i"lio!rafie

J1K Ioan #/<0 C lin Adrian C"$%<0 Qeronica D%AC [ "ptimi,area (lu urilor in(ormatice 5ntimp real [ element al re)tructur rii in(ormatice0 /niver)itatea B&etru $aior din T5rgu[$ureE2F1F

53

8/16/2019 Licenta Time Scheduling POPESCU MARIAN ALEXANDRU MIHAI.doc

http://slidepdf.com/reader/full/licenta-time-scheduling-popescu-marian-alexandru-mihaidoc 54/54

J2Khttp:;;ro. iUipedia.org; iUi;"ptimi,are

J3K #omic Tranda(ir0 $odele Ei algoritmi de optimi,are0 %d. AGI#0 ucureEti0 2FF4

J4Khttp:;;ro. iUipedia.org; iUi;Algoritm geneticJ*K Claudia $ihaela $arU [Seria informatică ) Algoritmi 3enetici 0 Timi oara0 2F1Fș

JPK #andy !. Yaupt0 <ue Yellen Yaupt [ 'ractical 3enetic Algorithms 0 ohn jiley \ <on)0Inc.0 Yo+oUen0 'e er)ey0 2FF4

J-K %mil <carlat0 'ora Chirita Ci+ernetica )i)temelor economice0 4ditura A<%0 ucureEti0.2FF3

J8K Yenri !uchian0 $ihaela rea+an [ Algoritmi Genetici0 /niver)itatea _Al. I Cu,a 0 Ia i0ș

2FFP

JVK %. `ig ne)cu0 D. $itru6 [ a,ele cercet rii opera6ionale0 %d. A<%0 ucureEti 1VVV

J1FK A. A+raham0 A.%.Ya))anien0 &. <iarry0 A. %ngel+recht oundation) o( ComputationalIntelligence Qolume 3

J11K .A. "mara and $.$. Ara(a 3enetic Algorithms for $ask Scheduling 'roblem

J12K %.G. ranco0 .T. kurrita0 G.$. Delgadillo [ A 3enetic Algorithm for the 2esource

Constrained 'ro&ect Scheduling 'roblem 0 ogota