Modelarea Timpului de Orientare in Sisteme de Asteptare Cu Prioritati

1

UNIVERSITATEA DE STAT DIN MOLDOVA

Facultatea Matematic i Informatic

Catedra Informatic i Optimizare Discret

Cu titlu de manuscris C.Z.U.: 519.872

ANDREI BEJAN

MODELAREA TIMPULUI DE ORIENTARE N SISTEME DE ATEPTARE CU PRIORITI

01.01.09 Cibernetic Matematic i Cercetri Operaionale

Tez de doctor n tiine fizico-matematice

Conductor tiinific:

Gheorghe MICOI m.-cor. al AM,

dr. hab. n t. fiz.-mat., prof. univ.

Autor Andrei BEJAN

Chiinu, 2007

2Cuprins

1 Sisteme de asteptare cu prioritati si timp de orientare si caracteristicile lor. 11

1.1 Clasificarea sistemelor de asteptare cu prioritati si timp de orientare cu o singura

statie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2 Caracteristicile de performanta ale sistemelor

de asteptare cu prioritati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Metode analitice n teoria sistemelor de asteptare cu prioritati 20

2.1 Nota introductiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2 Notiuni preliminarii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.1 Tehnica transformarii Laplace si Laplace-Stieltjes . . . . . . . . . . . . . . . 21

2.2.2 Monotonia completa si teorema Bernstein . . . . . . . . . . . . . . . . . . . 26

2.2.3 Tehnica transformatei-z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3 Sisteme de asteptare cu prioritati si timp de orientare nonzero si fluxuri de intrare

Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.3.1 Caz general: timp de orientare descompus . . . . . . . . . . . . . . . . . . . 31

2.3.2 Caz special: absenta lucrarilor de terminare a servirii . . . . . . . . . . . . . 35

2.3.3 Problema descompunerii timpului de orientare . . . . . . . . . . . . . . . . . 37

2.4 Sisteme de asteptare cu prioritati si timp de orientare zero. . . . . . . . . . . . . . . 48

2.5 Perioada de ocupare si legatura cu alte caracteristici. . . . . . . . . . . . . . . . . . 51

3 Metode numerice pentru sisteme de asteptare cu prioritati 53

3.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.2 Elementele algoritmilor numerici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.2.1 Inversarea transformatei Laplace . . . . . . . . . . . . . . . . . . . . . . . . 54

3.2.2 Examinarea ecuatiei Kendall . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.3 Evaluarea perioadei de ocupare: algoritmi . . . . . . . . . . . . . . . . . . . . . . . 65

3.3.1 Descrierea algoritmilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4 Modelarea imitationala a sistemelor cu prioritati si analiza statistica a caracter-

isticilor lor de performanta 72

34.1 Modelarea imitationala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.1.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.1.2 Modelarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.2 Realizarea: pachetul PQSST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.3 Analiza comparativa a evaluarii perioadelor de ocupare n modelarea timpului de

orientare: rezultatele analitice si numerice . . . . . . . . . . . . . . . . . . . . . . . 75

4.3.1 Analiza statistica a rezultatelor simularii: perioadele de ocupare . . . . . . . 76

4.3.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5 Concluzii, aplicatii si probleme deschise 79

5.1 Concluzii si discutii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.1.1 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.1.2 Problema tipului fluxului de intrare . . . . . . . . . . . . . . . . . . . . . . . 81

5.2 Aplicatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.2.1 Aplicatii n medicina si asistenta medicala . . . . . . . . . . . . . . . . . . . 83

5.2.2 Aplicatii n ingineria si tehnologia retelelor:

tehnologiile QoS si CoS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

5.3 Probleme deschise si lucrul de perspectiva . . . . . . . . . . . . . . . . . . . . . . . 88

A Rezumat teoretic 96

A.1 Proprietati de baza ale repartitiilor exponentiala si Poisson . . . . . . . . . . . . . . 96

B Rezultatele simularilor 99

B.1 Analiza comparativa empirica a sistemelorM3|M3|1 cu timpi de orientare exponentiali:tabele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

C Programe 108

C.1 Programe MATLAB pentru inversarea transformarii Laplace si solutionarea ecuatiei

Kendall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

C.1.1 Sumarea Salzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

C.1.2 Iteratiile euatiei Kendall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

4Prefata

Sisteme de asteptare cu prioritati si timp de orientare

Sistemele de asteptare reprezinta modele adecvate ale fenomenelor din fiecare zi n diverse aspecte

ale vietii noastre.

Azi, teoria asteptarii are un rol special n analiza performantei unui larg spectru de sisteme din

teoria comunicatiilor, logisticii si manufacturii, serviciilor civile.

Sistemele de asteptare cu prioritati formeaza o clasa larga a sistemelor de asteptare n care

cerintele ce intra n sistem se disting dupa importanta lor. Astfel de sisteme reprezinta mod-

ele adecvate ale multor aspecte ale vietii de fiecare zi, cand servirea preferentiala trebuie sa fie

oferita anumitor tipuri de cerinte (cereri, clienti). Sistemele de asteptare cu prioritati si mai

gasesc aplicari importante la modelarea si analiza sistemelor computationale si comunicationale.

Transferul pachetelor si gasirea unei cai mai eficiente pentru livrarea lor n retelele de calculatoare,

repartizarea operatiilor si calculelor (sisteme operationale multiprocesoare, etc.) pot fi modelate

folosind conceptul sistemelor cu prioritati.

Regula generala a servirii n sistemele de asteptare cu prioritati consta n urmatoarele: cerintele

care sunt n sistem si au o prioritate mai nalta trebuie sa fie servite naintea celor ce au o prioritate

mai joasa. Modul de comportare al servirii n astfel de sisteme este esential pentru diversificarea

lor. Pe langa aceasta, sunt sisteme n care serverul are nevoie de careva timp pentru a se orienta

la un alt tip de cerinte. Toate acestea conduc la o varietate de sisteme de asteptare cu prioritati.

In conformitate cu aceste fenomene descrierea si clasificarea sistemelor de asteptare cu prioritati

sunt dezvaluite n teza n caz general. La fel vom prezenta rezultate analitice si vom construi

metodologia de analiza numerica a lor, n special vom aplica metoda modelarii imitationale pentru

studierea acestor sisteme.

5Problema investigata

Sistemele de asteptare cu prioritati sunt studiate pe parcursul a ctorva decenii. In monografiile lui

Jaiswal (1968), Cox si Smith (1961) sunt expuse primele rezultate din acest domeniu. Monografia

lui Gnedenko s. a. (1973) prezinta rezultatele ulterioare, obtinute n urma cercetarilor efectuate n

acest domeniu.

Este imposibil de a face o prezentare succinta a varietatii potentiale a schemelor de cerinte care

au fost analizate n literatura specializata si nespecializata.

In calitate de exemplu a unei lucrari speciale poate servi articolul lui Deng si Tan (2001) care

contine studiul unui sistem cu o singura statie, doua fluxuri de cerinte cu prioritati si timp de

orientare cu valoarea-treshold. Sosirile au lege de repartitie Poisson, servirile si orientarile sunt

exponenttiale. Folosind metodele analitice autorii au obtinut probabilitatea stationara a functiei

generatoare a lungimilor acestor doua siruri de cerinte. Metoda de calculare a mediei lungimii

sirului de cerinte din sirul de asteptare si a mediei timpului de asteptare este asigurata conform

celor discutate.

Un alt exemplu este lucrarea lui Nazarov (1981) n care a fost considerat un flux Poisson de N

diferite tipuri de cerinte. Fiecare din cerintele din acest flux este de tipul i cu o careva probabilitate

pi, astfel ncatNi=1

pi = 1. Timpul de servire al cerintelor de tipul i este o variabila aleatoare Bi. In

sistem este numai un singur sir de asteptare, iar ordinea de servire este FIFO.

O familie foarte speciala, dar si imensa de sisteme de asteptare multi-class este familia de sisteme

polling. Sistemele polling reprezinta sistemele de asteptare cu un singur server care scaneaza

diverse clase de cerinte (diferite siruri de asteptare ale cerintelor), servind cerintele din fiecare clasa

pentru o anumita durata de timp, apoi se reorienteza spre o alta clasa, procedand n acest mod

pna ce sirul de asteptare este gol, sau dupa careva alta regula. De remarcat, ca n aceste sisteme

nu exista notiunea de prioritate, nsa, n acelasi timp ele implica reorientari ntre diferite clase de

cerinte. Cele mai raspndite modele implementeaza polling ciclic, adica serverul serveste cerintele

din sirurile de asteptare n ordinea predefinita (sau ordinea ciclica, cnd sirul de asteptare este

numerotat). Termenul sisteme polling si are originea n industria telefonica. Cartile si articolele

lui Takagi (1986, 1988, 1990, 1997) sunt surse excelente pentru examinarea modelelor, tehnicilor si

rezultatelor din teoria sistemelor polling.

In aceasta teza sunt studiate modele de asteptare ce implica timpul de orientare.

In literatura sunt mentionate multe lucruri despre astfel de sisteme n presupunerea

fluxului de intrare Poisson: n monografiile lui Klimov si Miscoi (1979) si lui Volkovin-

ski si Kabalevski (1981) sunt studiate sistemele de asteptare cu prioritati, cu flux

de intrare Poisson si timp de orientare de o forma speciala. Aceste monografii ex-

tind rezultatele culese si prezentate n Gnedenko s. a. (1973). Instrumentele analitice

6si metodologia folosite n aceste lucrari au fost prezentate si sistematizate de catre

Klimov (1966).

Insa, pentru unele sisteme de asteptare cu prioritati cu fluxuri de intrare Poisson

si timp de orientare de tip general ntre liniile de asteptare ale cerintelor cu diferite

prioritati rezultatele analitice nca nu sunt cunoscute.

Prin urmare este important de a studia problema timpului de orientare de tip

general si de examinat care sunt posibilitatile de extindere a rezultatelor analitice

obtinute mai devreme pentru sistemele similare, dar mai simple.

Cteva din metodele, deja clasice ale studiului analitic al sistemelor cu prioritati,

sunt metoda transformatei Laplace si Laplace-Stieltjes, si metoda catastrofelor aso-

ciata. Aceasta permite a exprima sistemul caracteristicilor de performanta sub forma

unui sistem functional n termenii transformatei Laplace-Stieltjes. Pentru a face o eval-

uare propriu-zisa a caracteristicilor sistemului sunt necesare metode numerice eficiente

de rezolvare a unor astfel de sisteme de ecuatii functionale si apoi inversarea trans-

formatei Laplace a solutiei functionale a acestui sistem. Astfel de metode numerice

pentru sisteme cu timp de orientare de forma speciala sunt dezvoltate n aceasta teza.

Aceste scheme numerice vor fi similare la tratarea oricarui rezultat exprimat n ter-

menii transformatei Laplace-Stieltjes, care ar putea aparea n viitor pentru sistemele

cu timp de orientare n forma generala.

In acesta teza este dezvoltata si propusa clasificarea sistemelor de asteptare cu

prioritati si timp de orientare. Este prezentat si un rezumat al unor rezultate si tehnici

ce se bazeaza pe metoda transformatei Laplace-Stieltjes de studiere a sistemelor de

asteptare.

Se arata n ce mod pot fi obtinute rezultatele analitice pentru sistemele cu timp de

orientare de o forma speciala. Presupunnd ca rezultatele analitice pentru problema cu

timp de orientare de tip general pot fi foarte dificile, se pune problema descompunerii

timpului de orientare si se considera diferite forme ale acestei probleme. Aceasta

este o ntrebare ce tine de viitoarele investigatii: de a stabili relatiile ntre ele si a

determina este oare efectiv de a forma sistemul ce corespunde descompunerii timpului

de orientare (pentru care rezultate analitice exista) pentru a face careva concluzii

despre performanta sistemului cu timp de orientare n forma generala.

Nu numai se studiaza si se aplica instrumentele analitice, corespunzatoare pentru

studierea sistemelor de asteptare cu prioritati si timp de orientare, ci este folosita si

tehnica de simulare pentru cercetarea unor astfel de sisteme n presupunerea fluxurilor

de intrare si a timpului de orientare de tip general. Necesitatea acestui studiu poate

7fi confirmata de faptul ca pentru unele scheme ale sistemelor cu prioritati nu exista

rezultate analitice sau ele sunt foarte complicate sau ineficiente la efectuarea calculelor.

Astfel de probleme au fost deja studiate, nsa mai cer cercetari noi, vezi e.g. Mishkoy

(1990), Grama si Mishkoy (1993).

In capitolul 1 este prezentata clasificarea sistemelor de asteptare cu prioritati si timp de ori-

entare. La fel, sunt introduse caracteristicile de performanta ale unor astfel de sisteme si analogiile

lor stationare. Este introdusa notiunea de ncarcare a sistemului.

In capitolul 2 sunt analizate metodele analitice de studiere a sistemelor de asteptare cu pri-

oritati bazate pe transformata Laplace, metoda catastrofelor si marcarea cu culori bazata pe

transformata-z. O atentie deosebita se acorda notiunii de monotonie completa si teoremei lui

Bersteintoate acestea sunt importante la cercetarea ulterioara a ecuatiei Kendall. Sunt studiate

sistemele de asteptare cu timp de orientare nenul si flux de intrare Poisson. Timpul de orientare,

n acest context, este considerat de o structura speciala: se presupune ca acest timp poate fi de-

scompus n timpul pentru lucrari legate cu terminarea servirii si timpul pentru unele lucrari de

pregatire a serverului catre servire a cerintelor din alt flux.

Remarcand ca nici un rezultat nu este valabil pentru timpul de orientare n caz general, n

2.3.3 se analizeaza problema descompunerii timpului de orientare cu scopul de a reduce studierea

sistemelor de asteptare cu timp de orientare de tip general la studiul cazului cu timp de orientare

descompus.

In 2.4 sunt analizate rezultatele analitice pentru sistemele cu reorientare nula conform schemei

cu pierderi si sunt prezentate doua exemple care arata ca chiar si n cel mai simplu caz (n termenii

structurii timpului de orientare) rezultatele analitice sunt greu de utilizat.

Capitolul 3 este dedicat studierii metodelor numerice pentru perioada de ocupare ca cea mai

importanta caracterisitica din teoria sistemelor de asteptare. Este prezentata metoda eficienta

de solutionare numerica a ecuatiei Kendall. Aceasta permite descrierea algoritmiilor de evaluare

numerica a transformatei Laplace-Stieltjes pentru peroada de ocupare si coeficientul de ncarcare.

Acesti algoritmi, mpreuna cu metodele numerice avansat dezvoltate, se folosesc la inversarea trans-

formatei Laplace. Aceasta inversare se bazeaza pe functionalele lui Gaver-Stehfest si modificarile

lor, ceea ce permite crearea procedurii de evaluare a functiei densitatii prioadei de ocupare. Algo-

ritmul este implementat n limbajul C++.

In capitolul 4 este descris apletul pachetului Java PQSST ca instrument de modelare imitatio-

nala a sistemelor de asteptatre cu prioritati si timp de orientare. Importanta unei astfel de analize

este cauzata de faptul ca pentru unele sisteme cu prioritati rezultatele analitice nu sunt cunoscute

sau nu pot fi utilizate pentru a descrie complet caracterisiticele de performanta ale sistemului

studiat ca variabile aleatoare. O atentie deosebita se acorda analizei statistice a perioadelor de

8ocupare ca sir de variabile aleatoare identic repartizate.

Capitolul final al tezei cuprinde o lista de concluzii, aplicatii si discutii ale problemelor deschise.

Rezultatele de baza au fost publicate n forma de lucrari stiintifice si comunicari:

Mishkoy s. a. (2007), Bejan (2006), Mishkoy s. a. (2006a), Mishkoy s. a. (2006b), Bejan si

Mishkoy (2004), Bejan (2004), Bejan (2003a), Bejan (2003b), Bejan si Mishkoy (2002), si Botezatu

si Bejan (2006).

Autorul a luat cuvntul de numeroase ori la urmatoarele seminare:

Probleme Actuale n Matematica si Informatica (pe parcursul anilor 2004-2006), Universitatea

de Stat din Moldova (conducator stiintificacademicianul P. Soltan), Young Researchers Semi-

nar Meetings (februarie 2005), Universitatea din Warwick, Facultatea de Statistica, si Actuarial

Mathematics and Statistics Department Seminar (iarna 2006-2007), Universitatea Heriot-Watt,

Edinburgh.

Teza a fost editata n sistemul LATEX.

Recunostinte

Sunt recunoscator Facultatii de Matematica si Informatica a Universitatii de Stat din Moldova si

Departamentului de Statistica, Universitatea din Warwick pentru asigurarea facilitatilor de cerc-

etare.

Exprim sincere multumiri conducatorului meu Profesorului Gheorghe Miscoi pentru ndruma-

rea sa, sfaturi, atentie permanenta si ncurajare la executarea acestei lucrari. Multumiri Dlui Dr.

Arkadii Sementul, Universitatea de Stat din Moldova pentru sustinere si discutii utile.

Profesorul V. Rykov a facut unele observatii utile dupa citirea proiectului acestei teze si eu as

vrea sa-i multumesc pentru critica sanatoasa si utila.

Olesia Groza m-a ajutat mult la traducerea acestei teze n limba romana si acest ajutor precum

si sustinerea permanenta sunt foarte nalt apreciate. Ii multumesc de asemenea colegei mele de la

Universitatea de Stat din Moldova, Olga Benderschi pentru ajutorul oferit si sustinerea permanenta.

Multumiri speciale pentru Ihar Kuchmyenko si Sorin Opincariu pentru discutii interesante si

utile care au avut loc ocazional la aparitia diverselor probleme cand se lucra la teza.

Multumiri studentilor mei si prietenilor mei Botezatu Maxim si Barbul Leonid a caror rapoarte

anuale au contribuit esential la aceasta lucrare.

Suportul bursei OSI/Chevening/Warwick 2004/2005 si grantului SCOPES IB7320-110720 este

de asemenea recunoscut.

In final, este datoria mea de a le fi recunoscator si a le multumi parintilor mei si fratelui meu

pentru ntelegere si ajutorul n toate.

9Notatii si abrevieri

ef= sau := egal dupa definitie sau se atribuie o valoare respectiva

10

abreviere descriere

corresp. correspunzator

i.e. id est

e.g. exempli gratia, de exemplu

c.p. 1 cu probabilitatea 1

r.i.i. repartizate independent si identic

f.c.r. functia cumulativa de repartitie

f.g.p. functia generatoare de probabilitati

v.a. variabila aleatoare

c.m. (functia) complet monotona

eng. engleza

referirea la compartiment;

e.g. 3.2.1 nseamna referirea la paragrafulul 3.2.1 al Capitolui 3.

Urmatoarele cuvinte sunt sinonime:

cerinte, cereri

orientare, schimbare

starea neutra, starea neutrala, starea nula

11

Capitolul 1

Sisteme de asteptare cu prioritati si

timp de orientare si caracteristicile lor.

Acest capitol contine o clasificare formala a sistemelor de asteptare cu prioritati si timp de orientare.

Vom utiliza cuvintele server si statie ca cuvinte cu sens reciproc. Cuvntul orientare este

sinonim pentru cuvntul schimbarechangeover (engleza). In aceasta lucrare este folosit primul

cuvnt.

1.1 Clasificarea sistemelor de asteptare cu prioritati si timp

de orientare cu o singura statie

Consideram sistemul de asteptare cu o singura statie si r clase de cereri care sosesc n sistem; vom

nota aceste clase prin clasa 1, clasa 2, ..., clasa r, fiecare avnd propriul flux de intrare si sir de

asteptare. Cererile fiecarei clase sunt servite dupa una din urmatoarele reguli, proprie fiecarui sir:

primul-intrat-primul-servit (FIFSFIRST-IN-FIRST-SERVED, eng.);

primul-intrat-ultimul-servit (LIFSLAST-IN-FIRST-SERVED, eng.);

aleator (RANDOM, eng.).

Presupunem ca perioadele de timp dintre doua sosiri consecutive a cererilor din clasa i sunt

independente si identic repartizate cu functia cumulativa de repartitie (f.c.r.) Ai(t), i = 1, . . . , r.

Similar, presupunem ca timpul de servire a unei cereri de clasa i este o variabila aleatoare (v.a.)

Bi cu f.c.r. Bi(t), i.e.

P(Bi t) = Bi(t), i = 1, . . . , r.

Pentru simplificare vom denumi cererile de clasa i prin i-cereri. Vom spune ca i-cererile au

o prioritate mai nalta dect j-cererile daca 1 i < j r. Astfel, 1-cereri au cea mai nalta

12

prioritate, n timp ce r-cererile au cea mai mica prioritate. Serverul va da prioritate la servire

cererii cu cea mai nalta prioritate printre cele prezente n sistem.

Vom presupune ca serverul are nevoie de un anumit timp pentru a se orienta de la un flux de

cereri la altul. Acest timp este considerat a fi o variabila aleatoare si vom spune ca Cij este timpul

de orientare de la servirea i-cererii la servirea j-cererii, 1 i r, 1 j r, i 6= j. In plus, nevom referi la Cij ca ij-timp de orientare cu f.c.r. Cij(t).

Uneori este convenabil de privit structura timpului de orientare Cij ca suma a doua perioade

independente:

Cij = Ti + Sj, i 6= j, (1.1.1)

unde Ti este timpul (aleator) ncheierii tuturor procedurilor de servire corespunzatoare clasei i,

si Sj este timpul (aleator) de care are nevoie serverul pentru a se aranja si a ncepe servirea j-

cererilor. Din punct de vedere tehnic, acest fenomen poate fi privit ca trecerea serverului printr-o

stare neutra speciala sau nula n timp ce serverul realizeaza ij-orientare el are nevoie de timp Ti

pentru a veni n stare neutra de la clasa i, si are nevoie de timp Sj pentru a se orienta la servirea

j-cererilor din stare neutra . Vom numi aceasta regula orientare prin stare neutra. In sistemele

cu aceasta regula functiile de repartitie ale variabelor aleatoare {Ti}ri=1 si {Si}ri=1 vor fi functiile{Ti(t)}ri=1 si {Si(t)}ri=1.

Consideram doua discipline de servireambele traditionale n teoria sistemelor de asteptare:

disciplina absoluta de servire si disciplina relativa de servire. In prima disciplina se considera ca

cererea cu prioritatea mai nalta dect a cererii care a nceput sa fie servita ntrerupe procesul de

servire si orienteaza imediat servirea catre aceasta clasa. In cea de a doua disciplina, cererea cu

prioritate mai mica va fi servita complet dupa care serverul va continua orientarea de care are

nevoie. In ambele cazuri, dupa terminarea servirii cererilor dintr-o anumita clasa serverul va fi

pregatit pentru a se orienta la servirea unui alt sir de cereri cu prioritate nalta .

Disciplina absoluta de servire Consideram diferite scheme de servire n raport cu cererea

servirea careia a fost ntrerupta :

1. preemptive resumecererea ntrerupta este servita timp rezidiu dupa ntoarcerea serverului,

i.e. timpul de care serverul ar avea nevoie pentru completarea servirii, daca servirea acestei

cererii n-ar fi fost ntrerupta.

2. repeat again (servirea din nou):

preemptive identical repeat again (servirea identica din nou)cererea cu servire ntre-

rupta va fi servita din nou dupa ntoarcerea serverului. Timpul de servire coincide cu

timpul n care aceasta cerere ar fi servita daca n-ar fi fost ntrerupta servirea.

preemptive non-identical repeat again (servirea neidentica din nou)exact ca si n cazul

13

precedent, doar ca timpul de servire este realizat din nou, n conformitate cu legea

corespunzatoare, i.e. avand f.c.r. Bi(t), daca cererea este din clasa i.

3. preemptive loss (cu pierderi)cererile servirea carora este ntrerupta sunt pierdute si sunt

eliminate din sistem.

Disciplina relativa de servire. Aceasta disciplina presupune ca cererile nu pot fi ntrerupte

de la servire. Insa, dupa completarea servirii cererilor dintr-o anumita clasa serverul este pregatit

sa realizeze orientarea catre fluxul de cereri cu prioritatea cea mai mare, daca n sistem mai sunt

cereri. In loc de termenul relativa se poate folosi, dupa Gaver (1961), alt nume pentru aceasta

disciplinadisciplina postponable priority service.

Aceasta disciplina poate fi de diferite feluriaceasta depinde de regula dupa care se efectueaza

orientarea catre cererile cu prioritate mai nalta:

1. disciplina request postponable priority servicedupa completarea servirii oricarei cerinte

serverul este pregatit sa se orienteze la sirul cu cerinte de prioritate mai nalta (daca aceste

sunt n sistem).

2. disciplina exhaustive postponable priority serviceserverul va fi pregatit sa se orienteze

la sirul cu cerinte de mai nalta prioritate numai dupa completarea servirii tuturor

cerintelor din sirul la care este deja orientat.

disciplina gated postponable priority serviceca si n disciplina precedenta, doar ca vor

fi servite numai acele cerinte din sirul la care este orientat serverul care au sosit n sistem

pana la sosirea primei cerinte cu prioritate mai nalta care cere orientarea serverului la

sirul n care se gaseste.

Orientari. Unele cerinte ce intra n sistem pot gasi serverul orientat la cerinte cu prioritate

mai mica. Din aceste considerente, n mod analogic cu disciplinele de servire, vom considera

urmatoarele discipline de orientare: disciplina orientarea absoluta preemptive switching, disciplina

orientarea absouta cu stare neutra preemptive neutral state switching, disciplina orientarea relativa

non-preemptive switching, disciplina orientarea relativa cu stare neutra non-preemptive neutral state

switching.

Orientare absoluta preemptive. Disciplinele absoluta si absoluta cu starea neutra presupun

ca orice ij-orientare poate fi intrerupta imediat cu venirea k-cererii, numai si numai n cazul k < j,

i.e., cand n sistemul a intrat o cerinta de prioritate mai nalta. Dupa intrerupere se realizeaza o

noua orientare la sirul cu aceste cerinte. Aceste doua discipline difera numai prin absenta/prezenta

starii speciale neutralastare intermediara a serverului n procesul de orientare (vezi definitia starii

neutrala pe p. 12).

14

Uneori este convenabil sa consideram orientarea absoluta descompusacu trecerea prin stare

neutra, formal ca n (1.1.1), unde lucrarile Ti asociate cu terminarea servirii nu pot fi intrerupte.

Vom numi acest tip de orientare orientarea pseudoabsoluta, sau pseudo-preemptive, eng.

Orientare relativa non-preemptive. Acest tip de orientare tot are doua subdiscipline

orientarea relativa non-preemptive si orientarea relativa cu stare neutra, si presupune ca orientarile

nu pot fi intrerupte de cerinte cu prioritatea mai mare. Aceste discipline se deosebesc numai prin

absenta/prezenta starii intermediare, dupa descrierea data mai sus.

In disciplina de orientare non-preemptive cu stare neutra structura procesului de schimbare a

starii serverului consta din doua subprocesecum este definit prin (1.1.1). Presupunem ca serverul

a fost gasit de k-cerinta fiind n procesul de schimbare a starii de la j-cerinte, unde k < j, i.e.

realizand ij-orientarea cu durata Cij. Acest eveniment se poate ntmpla n unul din urmatoarele

momente de timp: cand are loc orientarea spre starea neutra (de lungimea Ti) sau cand are loc

continuarea orientarii dupa parasirea starii neutrale (de lungimea Sj). Aceste posibilitati ne permit

sa consideram urmatoarele subdiscipline:

orientare normalaorientarea la k-cerinte se realizeaza sau dupa terminarea orientarii la

starea neutrala de la i-cerinte (si atunci durata orientarii va fi Sk) sau dupa orientarea de la

starea neutrala la j-cerinte (cu durata Cjk).

orientare postponableorientarea la k-cerinte este posibila numai dupa completarea ij-orien-

tarii (si dureaza Cjk timp).

Serverul n stare vacanta. Vom descrie regimele de comportare ale serverului n starea

vacanta. In primul rnd, independent de regim se presupune ca serverul are nevoie de timp de

ncalzire pentru a efectua orientarea sau servirea primei cerinte care vine n sistemul vacant, i.e.

dupa perioda vacanta. Acest timp de ncalzire este aleator, fiind reprezentat de variabila aleatoare

cu f.c.r. (t). Daca timpul de ncalzire este zero (serverul nu are nevoie de ncalziri), atunci

(t) H(t), unde H(t) este functia Heaviside.Urmnd traditia care si are originea n lucrarea lui Gaver (1963) vom diferentia urmatoarele

moduri de comportare a serverului cand sistemul este vacant:

initializarea la zerodupa completarea servirii ultimei cerinte din sistem serverul se ori-

enteaza imediat la starea neutrala. Daca prima cerinta care apare n sistemul vacant este

i-cerinta, atunci serverul realizeaza orientarea de durata Si. Evident, acest regim este bine

definit pentru sisteme cu stare neutrala. Pe de alta parte, noi putem defini acest regim pentru

sisteme n care servirea si orientarea nu necesita existenta starii neutrale. Pentru aceasta con-

sideram starea neutrala ca stare speciala a relaxarii serverului fiind ramas fara lucru. Atunci

15

timpii adaugatori {Ci}ri=1 de orientare la i-cerinte dupa ncalzirea serverului trebuie sa fiespecificate suplimentar.

se uita nainteserverul si schimba orientarea catre sirul cu 1-cerinte n momentul cnd

sistemul devine vacant.

asteapta si se uitaserverul ramne orientat spre sirul de cerinte din care face parte ultima

cerinta servita.

asteapta cea mai probabilaserverul se orienteaza catre sirul de cerinte care sunt cele mai

asteptate (cele mai probabile) la momenul dat. Vom explica notiunea de flux cu cele mai

asteptate cerinte. Fie ai(t) = Ai(t) densitatea timpilor ntre momentele de sosire a i-

cerintelor, i = 1, . . . , r. Atunci, prin flux cu cele mai asteptate cerinte vom ntelege fluxul de

p-cerinte, unde p = argmaxi

ai(t0+), si

t0 = mini=1,...,r

supai(t)=0

t

Daca p nu poate fi determinat n mod unic, atunci pot fi considerate conditii adaugatoarede

exemplu, p poate fi luat n modul urmator:

p = min{argmaxi

ai(t0+)}. (1.1.2)

Este descrisa o larga clasa de sisteme de asteptare cu prioritati. Aceasta clasa cuprinde sisteme

care pot fi definite prin urmatoarea informatie si identificatori:

fluxuri de intrarerepartitia perioadelor de timp dintre doua sosiri consecutive (pentru fiecare

flux);

timpii de servirerepartitia timpului de servire (pentru fiecare flux);

timpii de orientarespecificarea tipului orientarii (stare neutra sau nu) si repartitia timpilor

de orientare;

timpii de ncalzirerepartitia timpului de ncalzire;

ordinea servirii n interiorul unui sir (FIFS, LIFS, RANDOM);

disciplina de servire;

disciplina de orientare;

comportamentul serverului n starea de asteptare.

16

Vom folosi generalizarea notatiei lui Kendall (1953) 1 Ar|Br|1 pentru asa sisteme, adaugndinformatia suplimentara despre identificatorii descrisi mai sus. Subscriptia r indica numarul liniilor

de prioritate n sistem.

Exemplu 1.1.1 Sistemele de asteptare cu flux de intrare Poisson au o mare importanta n teorie

si practica. In acest caz timpul dintre doua sosiri consecutive are repartitie exponentiala, i.e.

Ai(t) = 1 eit, i = 1, . . . , r, unde 1, 2,..., r sunt niste numere reale pozitive, cu semnificatiafizica de rata a fluxului de intrare. Sistemul tipic cu flux de intrare Poisson poate fi caracterizat

prin urmatoarele: sistem de asteptare FIFS Mr|Gr|1 cu stare neutrala-disciplina de servirerequest postponable-orientare absoluta si cu regimul serverului asteapta cea mai

probabila cerinta. Aici cele mai probabile cerinte sunt p-cerinte, unde p este determinat din

(1.1.2), i.e. p = min{arg maxi=1,...,r

i}, si are un sens fizic clarp este egal cu cel mai nalt nivel deprioritate a cerintelor printre cele care au cea mai nalta rata de sosire.

1.2 Caracteristicile de performanta ale sistemelor

de asteptare cu prioritati

Putem specifica mai multe procese stocastice ce iau parte la descrierea sistemelor de asteptare.

Anumite caracteristici ale proceselor stocastice snt de un interes special si pot servi ca caracteristici

de performanta ale sistemului.

Vom ncepe cu notiunea de perioada de ocupare si perioada de asteptare (sau perioada vacanta).

Vom numi perioada de ocupare perioada de timp n care serverul este ocupat cu servirea cerintelor

sau cu orientarea. Notiunea de perioada de ocupare este intuitiv absolut clara. Putem numi

perioada de timp alternanta perioadei de ocupare perioada de asteptare. Este clar ca perioada de

ocupare urmeaza unei perioade de asteptare si vice versa.

Fie = {(1),(2), . . .} perioadele de ocupare consecutive n sistem.

Observatie 1.2.1 Sirul al perioadelor de ocupare consecutive din sistemele de asteptare cu

prioritati Mr|Gr|1 n toate disciplinele cu exceptia asteapta si se uita este un sir de variabilealeatoare independente si identic repartizate cu f.c.r. (t). Perioadele de asteptare n sistemele cu

mod de orientare a serverului n starea vacanta asteapta si se uita sunt independente din cauza

ca fluxurile de cerinte sunt Markoviene. Insa nu avem un raspuns la ntrebarea daca perioadele

de ocupare consecutive n astfel de sisteme sunt repartizate identic. Totusi putem presupune ca o

ipoteza ca aceasta are loc (Presupunerea 1.2.2).

1A si B simbolizeaza urmatorii identificatori: Mrepartitia exponentiala (flux de intrare Poisson), F sau Drepartitia constanta, Urepartitia uniforma, Ekrepartitia Erlang, Grepartitia generala (data prin f.c.r. saudensitatea de repartitie, etc.)

17

Presupunerea 1.2.2 Perioadele de ocupare n sistemele Mr|Gr|1 cu regimul serverului asteaptasi se uita sunt independente si identic repartizate.

De aceea, vom nota variabilele aleatoare care au f.c.r. (t) prin si ne vom referi la ele ca la

perioade de ocupare. Subliniem ca repartitia lui (t) nu depinde de ordinea de servire a cererilor

(FIFS, LIFS).

Starea sistemului la momentul t este descrisa de vectorul m(t) = {m1(t),m2(t), . . . ,mr(t)} Nr, unde mi(t) este numarul de i-cereri n sistem la momentul t (sau exact lungimea sirului i la

momentul t). Aici N ef= N {0}. Notam prin m(t) numarul de cereri n sistem la momentul t.Astfel,

m(t) =ri=1

mi(t).

Introducem de asemenea urmatoarele notatii pentru functiile cumulative ale m si m:

Pm(t)ef= P(exact mi i-cereri se gasesc n sistem la momentul t),

unde m = (m1, . . . ,mr), si

Pm(t)ef= P(exact m cereri se gasesc n sistem la momentul t).

Urmatoarele notiuni, mai curnd abstracte, ca timp virtual de asteptare si timp virtual de aflare

n sistem sunt foarte importante n teoria sistemelor de asteptare si aplicarile lor. Consideram

i-cereri si ne ntrebam: ct timp trebuie sa astepte i-cererea pna a ncepe sa fie servita daca ea

soseste n sistem la momentul t? Aceasta perioada de timp, n mod evident, poate fi considerata

ca o variabila aleatoare, pe care o vom nota prin W(i)t si o vom numi timp virtual de asteptare a

i-cererii. Notam f.c.r. a W(i)t prin W

(i)(t, ), i.e.

W (i)(t, ) = P(W (i)t ).

Analogic, timpul pe care i-cererea l va petrece n sistem daca ea intra n sistem la momentul t este

o variabila aleatoare notata prin V(i)t cu f.c.r. V

(i)(t, ), i.e.

V (i)(t, ) = P(V (i)t ).

De notat ca timpul virtual de asteptare si timpul de aflare n sistem n mod esential depind de

ordinea servirii cererilor (FIFS, LIFS).

Folosim notatia Pi(t) pentru probabilitatea ca vom gasi serverul orientat la sirul i n momentult. Analogic, notam prin S(t) probabilitatea ca vom gasi serverul orientat n momentul t. In modevident,

S(t) = 1ri=1

Pi(t).

18

Notam prin P0(t) probabilitatea ca serverul este orientat catre starea neutrala si sistemul estevacant pentru regimul initializarea la zero. Atunci

S(t) = 1ri=0

Pi(t).

Stationaritatea. Notiunea de stationaritate (sau, mult mai general, stabilitate) este foarte

importanta n studierea sistemelor stocastice care evolueaza n timp. De obicei sistemul este con-

siderat a fi stationar daca starile sale devin stabile si, ntr-un anumit sens, regulate. Mai multe

caracteristici ale sistemului au asemanari stationare si deseori acestea sunt foarte convenabile la

descrierea comportamentului stabilit al unui sistem dupa o perioada anumita de timp (care poate

fi de lunga durata). Mai multe comentarii generale referitor la notiunea de stabilitate n sistemele

de asteptare pot fi gasite n Stidham (2001).

Mai multe mijloace formale pentru studierea stationaritatii n familia sistemelor considerate

aici sunt mprumutate din teoria proceselor regeneratoare si a proceselor Markoviene incluse. La

dezvoltarea si aplicarea astfel de metode n teoria asteptarii au contribuit Kendall, Cox, Smith si

Klimov. Metodologia generala a acestei tehnici este de a evidentia un proces inclus, numit lant

Markov continuu, ntr-un proces stocastic principal, descris, de exemplu, prin vectorul m(t), si

apoi de a impune niste restrictii la parametrii sistemului pentru a obtine conditia de stationaritate.

Deseori asemenea conditie este doar suficienta si de obicei ea poate fi formulata n termenii unei

cantitati care este numita coficient de trafic. Forma standarda de exprimare a stationaritatii

sistemului este inegalitatea de urmatoarea forma:

< 1. (1.2.1)

Putem formal defini analoagele stationaritatii pentru toate caracteristicile introduse mai sus.

Totusi, se supune verificarii ca aceste definitii ne dau obiecte bine definite. Vom continua acum pe

o cale formala:

pmef= lim

tPm(t), (1.2.2)

pmef= lim

tPm(t), (1.2.3)

W (i)()ef= lim

tW (i)(t, ), (1.2.4)

V (i)()ef= lim

tV (i)(t, ), (1.2.5)

Pi ef= limt

Pi(t), (1.2.6)

S ef= limt

S(t). (1.2.7)

Consideram de asemenea notiunile de timp mediu de asteptare si timp mediu de aflare n sistem.

Notam prinW i timpul mediu de asteptare dintre sosirea si nceperea servirii pentru i-cereri n regim

19

stationar. Formal, W i este primul moment al repartitiei stationareW(i)(). In mod analog, numim

timpul mediu de aflare n sistem a i-cererii primul moment V i al repartitiei stationare V(i)().

Remarca 1.2.3 In sistemul Mr|Gr|1 cu fluxurile de sosire 1, 2, . . . , r pentru i-cereri are locformula lui Little:

Emi = iV i, i = 1, . . . , r ,

undemi este lungimea sirului din i-cereri n regim stationar si repartitia lor este gasita din repartitia

marginala obtinuta din {pm}mNr . Pentru varianta unidimensionala a formulei lui Little vezisursa originala n Little (1961) sau unele referinte standarde a bazei teoriei sistemelor de asteptare.

Demonstratia noastra pentru cazul clasic este bazata pe tehnica transformatei-z si este data de

Teorema 2.2.36.

In sfrsit, introducem notiunea de probabilitate de pierdere. Aceasta poate servi ca una dintre

cele mai principale si importante masuri de performanta a lucrului sistemului de asteptare cu

prioritati n regim de servire absoluta cu pierderi. Intr-o analogie deplina cu notiunea similara

pentru sistemele de asteptare cu clienti nerabdatori, probabilitatea de pierdere a i-cererii P(i)loss este

definita prin

P(i)loss := numarul relativ a clientilor care nu au beneficiat de o servire completa. (1.2.8)

In mod formaldaca I(i)k este o functie-indicator a evenimentului: a k i-cerinta nu a fost

servita complet (si de aceea a fost pierduta), atunci definim probabilitatea de pierdere a i-cerintei

dupa cum urmeaza

P(i)loss := lim

K

Kk=1

I(i)n+k

K, i = 1, . . . , r, (1.2.9)

unde n este numarul suficient de mare.

20

Capitolul 2

Metode analitice n teoria sistemelor de

asteptare cu prioritati

2.1 Nota introductiva

Instrumentele analitice din teoria asteptarii includ metodele clasice bazate pe procese markoviene,

teoria traficului intens, teoria martingalelor, metodele bazate pe transformari integrale, metode

matriciale si multe altele.

Stidham (2002) a efectuat un rezumat deplin despre istoria analizei si proiectarii sistemelor de

asteptare si retelelor, si, n particular, a sistemelor de asteptare cu prioritati, sistemelor polling, si

a sistemelor de asteptare cu locuri vacante.

Este imposibil de a examina si utiliza toate sau macar o parte din metodele existente de analiza

a sistemelor de asteptare cu prioritati. Ne vom limita la rezultatele analitice bazate pe tehnica

transformatei Laplace-Stieltjes.

2.2 Notiuni preliminarii

Vom discuta interpretarea probabilistica a transformatei Laplace (TL) (sau a transformatei Laplace-

Stieltjes (TLS) a functiei cumulative de repartitie) a densitatii variabilei aleatoare nenegative. Vom

interpreta TL si TLS a variabilelor aleatoare ca probabilitatea evenimentelor speciale. Aceasta

formeaza ideea metodei catastrofelor. O interpretare similara este posibila pentru transformata-z

a variabilelor aleatoare discrete.

21

2.2.1 Tehnica transformarii Laplace si Laplace-Stieltjes

Transformata Laplace este o tehnica puternica n mai multe ramuri ale matematicii si fizicii. Ea

are multe aplicari n optica, ingineria electrica, procesele de semnal, calculul operational, anal-

iza functionala si teoria probabilitatii. Transformata este numita n cinstea matematicianului si

astronomului francez Pierre-Simon Laplace. Initial, transformata Laplace a fost descoperita de

Leonard Euler.

Transformatele Laplace si Laplace-Stieltjes

Definitia 2.2.1 Fie f(t) valoarea complexa a functiei de argument real ce satisface urmatoarele

conditii: (i) f(t) = 0 t < 0, (ii) este o funcctie de variatie marginita pe orice segment [0, T ], (iii)s0, A R asa ca |f(t)| Aes0t. Transformata Laplace a functiei f(t) este notata prin L[f(t)](s)sau f(s) si este definita prin

L[f(t)](s) = f(s) ef=0

estf(t)dt, (2.2.1)

unde s C : s0.

Aceasta este o definitie generala. Conditiile (i)-(iii) sunt necesare pentru corectitudinea si

existenta transformatei. Transformata Laplace este analitica n semiplanul s0. Infimultuturor s pentru care transformata Laplace exista se numeste abscisa convergentei si se noteaza

prin 0. Transformata Laplace pentru valoarea reala a functiei este definita n mod automat de

Definitia 2.2.1.

Transformata Laplace este unica, n sensul ca, fiind date doua functii f1(t) si f2(t) cu aceeasi

transformata, i.e. L[f1(t)] L[f2(t)], integralaT0

N(t)dt

functiei nule N(t)ef= f1(t) f2(t) este egala cu zero pentru toti T > 0 (teorema Lerch pentru

transformarile integrale).

Transformata Laplace este liniara:

L[af(t) + bg(t)] = aL[f(t)] + bL[g(t)]. (2.2.2)

Transformata Laplace a convolutiei f(t) g(t) =0

f(t )g()d este data de

L[f(t) g(t)] = L[f(t)]L[g(t)] (2.2.3)

22

Definitia 2.2.2 Transformata Laplace-Stieltjes a valorii reale a functiei F (t) de argument real este

notata prin LS[F ] sau F (s) si este data de

LS[F ] = F (s) ef=0

estdF (t), (2.2.4)

unde s C, cnd aceasta integrala exista. Aici integrala este luata n sens Lebesgue-Stieltjes.

Deseori s este o variabila reala, si atunci TLS este o functie reala. Daca F (t) este diferentiabila,

i.e. dF (t) = f(t)dt, atunci transformata Laplace-Stieltjes a F (t) este exact transformata Laplace a

derivatei sale.

Urmatoare identitate poate fi demonstrata prin integrarea prin parti:

LS[F (t)] = sL[F (t)] F (0). (2.2.5)

Fie X o variabila aleatoare cu f.c.r. FX(t), i.e.

FX(t) = P(X t),

atunci, transformata LS[FX(t)] este numita transformata Laplace-Stieltjes a lui X. Daca X este ovariabila aleatoare absolut continua cu densitatea fX(t), atunci transformata L[fX(t)] se numestetransformata Laplace a lui X. Obtinem LS[FX(t)] = L[fX(t)]. Putem scrie simplu L[X] si LS[X]pentru TL si TLS a variabilei aleatoare X.

Teorema 2.2.3 (Unicitatea) Doua repartitii probabilistice diferite au diferite transformate Laplace-

Stieltjes.

Demonstratie. vezi Feller (1971)

Remarca 2.2.4 Urmatoarea formula de inversare are un important interes teoretic, dar nu este

foarte utila n practica:

F (t) = lims

nst

(1)n sn

n!(n)(s).

unde (s) = LS[FX(t)] (din nou, vezi Feller (1971)).

Teorema 2.2.5 (Continuitatea) Fie Fn(t) o functie de repartitie cumulativa cu TLS n(s), n =

1, 2, . . .. Daca Fn F , unde F este o repartitie, posibil improprie, cu TLS (s), atunci n(s)(s) s > 0. Dimpotriva, daca sirul {(s)} converge la (s) pentru careva s > 0, atunci esteTLS a repartitiei (posibil improprii) F , asa ca Fn F . Repartitia limita F va fi proprie daca(s) 1 cnd s 0.

23

Demonstratie. vezi Feller (1971).

Momentul de ordinul n al variabilei aleatoare nenegative X cu densitatea fX(t) poate fi obtinut

din transformata Laplace n urmatorul mod:

E[Xn] = (1)nf (n)X (s)|s=0 (2.2.6)

De mentionat, ca transformata Laplace-Stieltjes a variabilei aleatoare X poate, formal, fi scrisa

ca

LS[X] = E[esX ].

Daca variabila aleatoare X este nenegativa, atunci n virtutea (2.2.5), TL si TLS snt legate n

urmatorul mod: L[X] = sLS[X].

Exemplu 2.2.6 Fie X o variabila aleatoare nenegativa, constanta, i.e. variabila aleatoare care ia

o anumita valoare 0 cu probabilitatea unu. Atunci TLS este egala cu

LS[X] =0

estdH(t ) =0

est(t )dt = es .

Aici H(t) si (t) sunt functia Heaviside si, respectiv, delta functia Dirac.

Exemplu 2.2.7 Fie X U[a, b], unde 0 a < b. Atunci

LS[X] = 1b a

ba

estdt =1

b a(esa esb).

Exemplu 2.2.8 Fie X Exp(). Atunci LS[X] =0

estetdt = +s

.

Exemplu 2.2.9 Fie X Er(n, ). Densitatea lui X este fX(x;n, ) = kxk1ex(k1)! . Totusi, nueste necesar de a aplica transformata Laplace direct la aceasta functie. Prin utilizarea inductiva a

(2.2.3) LS[X] = ( +s

)n, deoarece variabila aleatoare Erlang cu parametrii n si este o suma de

n variabile aleatoare independente, repartizate exponential, cu rata .

Exemplu 2.2.10 Fie X Pareto(a, b), i.e. FX(x) = 1 ba(b+x)a , fX(x) = aba

(b+x)a+1, a, b > 0, astfel

ncat transformata Laplace a acestei variabile aleatoare este

LS[X] =0

aba exp(sx)(b+ x)a+1

dx,

care poate fi reformulata n termenii gama functiei incomplete complimentare:

(a, x) =

x

ta1 exp(t)dt,

24

sau n termenii functiei Whittaker W, =x+1/2 exp(x/2)

(+1/2)0

t1/2(1 + t)+1/2 exp(xt)dt :

LS[X] = a(bs)a exp(bs)(a, bs) a(bs)(a1)/2 exp(bs/2)W(a+1)/2,a/2(bs),

vezi Nadarajah si Kotz (2006).

Abate si Whitt (1996) au studiat operatorii functionali care pun n corespundere unei repartitii

(sau mai multor repartitii) pe axa nenegativa reala alta repartitie folosind transformatele Laplace-

Stieltjes ale lor. In final vom nota ca LS[X](s) [0, 1]. Aceasta poate conduce la ideea de a nereferi la TLS a variabilei aleatoare nenegative ca la probabilitatea unui oarecare eveniment.

Metoda catastrofelor

Transformata Laplace a densitatii unei variabile aleatoare este probabilitatea ca variabila aleatoare

corespunzatoare este mai mica dect variabila aleatoare exponentiala cu rata particulara. Aceasta

interpretare, n mod esential, ne ajuta sa stabilim legatura dintre datele care definesc sistemele de

asteptare (repartitia timpului dintre cererile sosite, repartitia timpului de servire, etc.)

Urmatoarea teorema este baza metodei catastrofelor.

Teorema 2.2.11 Fie X si Y variabile aleatoare independente. Presupunem ca Y este repartizata

exponential, i.e. Y Exp(s), si densitatea variabilei X este fX(t). Atunci

P(X < Y ) = L[fX(t)](s) = LS[X].

Demonstratie. Fie f(t, y) functia densitatii comune a lui X si Y . Deoarece aceste variabile

aleatoare sunt independente, functia probabilitatii lor comune se descompune n factori n modul

urmator:

f(t, y) = fX(t)sesy.

De aceea,

P(Y > X) =0

t

f(t, y)dydt

=

0

t

fX(t)sesydydt

=

0

fX(t)estdt

= L[fX(t)](s) = LS[X](s).

25

Ca o derivata alternativa a acestui rezultat, vom considera urmatorul:

P(X Y ) =0

(1 FX(t))d(1 est)

= s

0

(1 FX(t))estdt

= 1 sL[FX(t)](s)= 1 LS[X],

i.e. P(Y < X) = LS[X], si teorema este demonstrata.

Exemplu 2.2.12 (descrierea metodei catastrofelor) Presupunem ca timpul de viata a unui

element este o variabila aleatoare X. Presupunem de asemenea ca observam un proces independent

N(t) a catastrofelor Poisson(st). Atunci, din Proprietatea A.1.4 timpul dintre doua catastrofe

consecutive are repartitie exponentiala cu parametrul s. Probabilitatea ca pe durata timpului de

viata a unui element nu vor fi catastrofe este exact LS[X](s) (Teorema 2.2.11).

Vom continua cu un exemplu de aplicare directa a metodei catastrofelor.

Exemplu 2.2.13 (Ecuatia Kendall) Consideram sistemul M |G|1 cu fluxul de intrare Poisson(t)si timp de servire aleator B cu f.c.r. B(t). In primul rnd, observam ca perioadele de ocupare n

astfel de sisteme sunt variabile aleatoare independente si identic repartizate cu careva functie de

repartitie (t). In ce masura (t) depinde de B(t) si ? Fie (s)ef= LS[B(t)] si pi(s) ef= LS[(t)].

Vom arata acum, folosind metoda catastrofelor, ca pi(s) satisface urmatoarea ecuatie functionala:

pi(s) = (s+ (1 pi(s))). (2.2.7)

Mentionam ca n sistemul M |G|1 ordinea servirii nu este importanta pentru evaluarea perioadelorde ocupare. De aceea, pentru comoditate, consideram ca servirea are loc n ordine inversa. Aso-

ciata fiecarei cereri sosite n sistem, perioada de ocupare reprezinta perioada de timp de la sosirea

acestei cereri si pna n momentul cnd sistemul devine vacant. Presupunem ca se observa un pro-

ces independent al catastrofelor cu rata s. Numim o cerere nefericita daca n timpul perioadei

asociate de ocupare a avut loc cel putin o catastrofa. Atunci, fluxul de cerinte nefericite este Pois-

son cu parametrul (1 pi(s)) (Proprietatea A.1.7). Probabilitatea ca nu va avea loc catastrofe ntimpul perioadei de ocupare a sistemului este probilitatea ca nu vor avea loc evenimente din fluxul

compus din catastrofe si cereri neferecite n timpul de servire a primei cereri cu care se ncepe

perioada de ocupare. Acest flux compus este Poisson cu rata s+ (1 pi(s)). Astfel, pi(s) satisfaceecuatia (2.2.7).

26

Ecuatia (2.2.7) este numita ecuatia Kendall, ea fiind pentru prima data obtinuta de matemati-

cianul britanic D.G. Kendall (1951). Aceasta ecuatie este echivalenta cu ecuatia integrala Takacs:

(t) =n=1

t0

(u)n1

n!eudBn(t), t 0,

unde Bn(t) este convolutia de n-ori a functiei B(t) cu ea nsuai.

Interpretarea probabilistica a transformatei Laplace a fost pentru prima data introdusa n lit-

eratura n 1949 de catre van Dantzig (1949). Scopul sau initial a fost de a gasi o interpretare a

transformatei-z (functia generatoare de probabilitati). Aceasta interpretare a fost numita metoda

marcarilor colective si este descrisa de catre Runnenburg (1965, 1979). In aceste lucrari au fost

reliefate aplicatiile din teoria asteptarii. Tehnica a gasit dezvoltare n lucrarile de mai trziu din

domeniile aplicarii probabilitatii si ale teoriei sistemelor de asteptare. In mod particular, ea a

fost utilizata la studierea sistemelor de asteptare n lucrarile lui Klimov (1966), Jaiswal (1968),

Gnedenko s. a. (1973), Klimov si Mishkoy (1979).

2.2.2 Monotonia completa si teorema Bernstein

Vom introduce acum o notiune importanta pentru urmatoarele noastre consideratiinotiunea de

monotonie completa.

Definitia 2.2.14 O functie de valoare reala pe [0,) se spune ca este complet monotona (c.m.)daca

(1)n(n)(s) 0 n N {0} s (0,). (2.2.8)

Exemplu 2.2.15 Functiile s, es ( 0), 11+s

, 1ssunt functii complet monotone. Functia

(a+ bs) este complet monotona cnd (s) este complet monotona (a 0, b > 0).

In expunerea noastra ulterioara vom utiliza urmatoarea proprietate importanta a functiilor

complet monotone. Functiile si sunt considerate a fi definite pe R+.

Proprietate 2.2.16 Daca si sunt doua functii complet monotone, atunci combinatia lor lin-

eara + este o functie complet monotona (2 + 2 > 0)1.

Demonstratie. Afirmatia decurge direct din definitia functiei complet monotone.

Proprietate 2.2.17 Daca si sunt doua functii complet monotone, atunci produsul lor este

o functie complet monotona.

1aceasta cerinta este redundantaidentitatea zero este o functie complet monotona.

27

Demonstratie. Vom folosi metoda inductiei matematice pentru a arata ca

(1)n()(n) 0 n = 0, 1, 2, ... (2.2.9)

Presupunem mai nti ca semnul primelor n derivate a alterneaza. Vom mentiona la nceput

ca este nenegativa si functiile si sunt functii complet monotone. Astfel, (i) () = 0 corespunde cazului n = 1 (baza inductiei), si (ii) putem aplica ipoteza inductieipentru produsul si . Dar de aici rezulta imediat ca pentru derivatele produsului semnul alterneaza de n + 1 ori. Conform principiului inductiei matematice proprietatea a fost

demonstrata.

Proprietate 2.2.18 Daca este complet monotona si este o functie nenegativa, astfel nct

este o functie complet monotona, atunci () este complet monotona.

Demonstratie. Mai nti vom mentiona ca () este o functie nenegatia pe R+. Apoi subliniem ca

() si sunt functii complet monotone. Aceasta face ca ((s)) = () sa fie completmonotona(Proprietatea 2.2.17). Am demonstrat ca [()] este o functie complet monotona, i.e.() este n mod cert complet monotona. Proprietatea este demonstrata.

Transformatele Laplace a masurilor Borel pozitive pe R+ sunt complet caracterizate de teorema

Bernstein n termenii monotoniei complete.

Teorema 2.2.19 (Bernstein (1928)) Functia este complet monotona daca exista o unica masura

Borel nenegativa pe [0,], astfel nct ([0,]) = (0+) si s > 0 (s) =0

esx(dt). Aici

[0,] este o compacticitate a intervalului [0,).

Remarca 2.2.20 Teorema spune ca clasa functiilor complet monotone (s) pe semidreapta R+,

astfel nct (0+) 1 coincide cu transformatele Laplace-Stieltjes a functiilor de repartitie cumu-lative.

Exemplu 2.2.21 (Exemplu 2.2.13 continuare) Am aratat mai sus ca TLS a perioadelor de ocupare

n sistemulM |G|1 satisface ecuatia Kendall. Se poate arata (Feller (1971), Gnedenko s. a. (1971)),ca ecuatia Kendall determina o functie unica pi(s) care este analitica n semi-planul complex 0. Mai mult dect att, daca coeficientul de trafic = (0)

1, atunci pi(0) = 1, si f.c.r. (t)

este o functie cumulativa de repartitie proprie.

Momentele perioadelor de ocupare n sistemul M |G|1 pot fi usor calculate folosind (2.2.6).De exemplu, calculnd prima si a doua derivata a lui pi(s) n punctul zero n (2.2.7), se obtine:

E[] = pi(0) = (0)

1 =E[B]1 ,

E[2] = pi(0) =E[B2](1 )3 ,

28

astfel nct

var[] = E[2] E[]2 = E[B2] E[B]2 + E[B]2

(1 )3 .

Totusi, pentru a obtine o informatie completa despre perioada de ocupare este necesar de a

inversa pi(s). Aceasta poate fi obtinuta n mod analitic sau prin evaluarea numerica a lui pi(s) si

inversarea ulterioara.

In cazul cnd > 1, au loc urmatoarele: pi(0) < 1, si (t) este o f.c.r. improprie, i.e. limt

(t) N),

unde p(z) este transformata-z a lui N .

Demonstratie. Vom folosi formula probabilitatii totale pentru a demonstra afirmatia:

P(M > N) =n=0

pnP(M > n)

=n=0

pnzn

= p(z). (2.2.13)

In conditiile Teoremei 2.2.31, daca N reprezinta numarul de pasi pna are loc un careva eveni-

ment, putem considera procesul discret geometric al catastrofelor, unde numarul de pasi M pna

la urmatoarea catastrofa este geometric cu parametrul 1 z. Probabilitatea ca nu vor fi catastrofepna are loc un eveniment este p(z).

30

Putem vedea ca transformata-z are o interpretare analogica cu cea a transformatei Laplace-

Stieltjes.

Sa mentionam ca repartitia geometrica este singura repartitie discreta care poseda proprietatea

de absenta a memorieieste analogul discret al repartitiei exponentiale.

Marcarea cu culori

Este o interpretare probabilistica alternativa a transformatei-z care vine din teoria marcarilor

colective, vezi van Dantzig (1949). Fie {pn}=0 repartitia care sta la baza unui proces numericaleator pe N. Presupunem ca vom marca (colora) fiecare item, dintr-o multime de N itemi, cu rosu

cu probabilitatea z si n albastru cu probabilitatea 1z. Atunci, transformata-z a repartitiei lui Neste probabilitatea ca toti itemii considerati sunt de culoare rosie. Acest fapt rezulta din definitia

transformatei-z, care este n acest caz formula probabilitatii totale pentru evenimentul toti itemii

sunt marcati.

Exemple de utilizare a transformatei-z

Vom obtine acum niste rezultate clasice care arata puterea tehnicii transformatei-z.

Teorema 2.2.32 Fie N(t) un proces numeric Poisson cu rata , i.e. N(t) Poisson(t). Fie Xlungimea intervalului aleator cu f.c.r. F (x). Atunci, daca p(z) este transformata-z a lui N(X),

p(z) = F ((1 z)) = LS[F (x)]((1 z)). (2.2.14)

Demonstratie. Pentru a demonstra teorema consideram marcarea evenimentelor cu probabil-

itatea z din N(t) . Atunci, conform Proprietatii A.1.7, procesul evenimentelor nemarcate este

Poisson cu rata (1 z). Probabilitatea p(z) ca toate evenimentele reprezentate de N(X) suntnemarcate este egala cu probabilitatea ca n perioada de timp de lungime X nu vor fi evenimente

(catastrofe) din acest proces, care este F ((1 z)). Formula (2.2.14) este corecta si teorema estedemonstrata.

O serie de rezultate clasice pot fi obtinute imediat pentru sistemul M |G|1.

Corolar 2.2.33 Daca N este numarul de sosiri n timpul perioadei de ocupare si (t) este f.c.r.

a lungimii perioadei de ocupare, atunci

p(z) = ((1 z)),


Corolar 2.2.34 Daca N este numarul de sosiri n timpul perioadei de servire B si B(t) este f.c.r.

a lungimii perioadei de servire, atunci

p(z) = B((1 z)),


31

Corolar 2.2.35 Daca Q este numarul de cereri sosite n timpul V al aflarii cererii n sistem si

V (t) este f.c.r. a lungimii timpului aflarii n sistem, atunci

q(z) = V ((1 z)), (2.2.15)

unde q(z) este transformata-z a lui Q.

Teorema 2.2.36 (Legea lui Little)

E[M ] = E[V ],

undeM este variabila aleatoare ce evalueaza numarul de cereri n sistemulM |G|1 n regim stationar.

Demonstratie. Vom ncepe cu (2.2.15) si vom calcula derivatele n punctul z = 1:

q(z) = V ((1 z))

q(1) =d

dzV ((1 z))|z=1

q(1) = V (0)

E[Q] = E[V ].

Insa, a fost aratat, ca E[Q] este doar lungimea sirului E[L] a sistemului M |G|1 n regim stationar(vezi Kleinrock (1975)). Obtinem legea lui Little.

2.3 Sisteme de asteptare cu prioritati si timp de orientare

nonzero si fluxuri de intrare Poisson

Din cte cunoaste autorul nu sunt prezentate n literatura de specialitate rezultate analitice pentru

sistemele de asteptare cu prioritati cu tip general al timpului de orientare. Vom considera un

tip special de sisteme cu prioritati cu timp de orientare descompus pentru a arata niste concepte

generale a metodelor de analiza ale acestor sisteme.

2.3.1 Caz general: timp de orientare descompus

Consideram sistemul de asteptare Mr|Gr|1 unul din tipurile introduse n Capitolul 1. Fluxurile deintrare sunt de tip Poisson cu parametrii 1, ..., r, si structura timpului de orientare este data

conform (1.1.1):

Cij = Ti + Sj, i 6= j, (2.3.1)

Din cauza posibilelor ntreruperi ale orientarii, introducem variabilele aleatoare Ti si Sj, i, j =

1, . . . r, care reprezinta timpul real al orientarii intermediare n sistem. Astfel, se poate vedea ca

32

Ti Ti si Sj Sj. Egalitatea are loc n orice din aceste inegalitati numai si numai daca o partecorespunzatoare a orientarii-ij nu a fost intrerupta.

Notiunea de perioada de servire permite analiza diferitor discipline de prioritate ntr-un cadru

analitic unificat.

Definitia 2.3.1 Notam prin k-perioada de servire timpul care ncepe cnd k-cererea intra n server

si sfrseste cnd serverul este gata de a servi urmatoarea k-cerere din linia de asteptare respectiva.

Notam lungimea k-perioadei de servire prin Hk.

De mentionat ca, deoarece 1-cererile au cea mai mare prioritate, timpul S1 si B1 nu poate fi

ntrerupt. Prin urmare, H1 = B1 si S1 = S1. Timpul de ncalzire al sistemului de asemenea nu

poate fi ntrerupt.

Prin k-sir izolat vom ntelege procesul de servire al k-cererilor unde timpul de servire Bi este

substituit prin perioada de servire Hk corespunzatoare. Perioada de timp necesara pentru a servi

i-cererile n k-sirul izolat va fi notata prin P ik, si prin Pk cnd i este aleator si necunoscut.

Vom introduce notiunea de k-clasa de cereri. Aceasta va fi clasa tuturor cererilor prioritatea

carora nu depaseste k.

In analiza caracteristicilor de performanta ale sistemului de asteptare notiunea de perioada de

ocupare joaca un rol crucial.

Structura perioadei de ocupare

Scopul urmatoarei expuneri este de a obtine formula pentru perioada de ocupare n sistemele

considerate, presupunnd ca se cunoaste cum sunt repartizate perioadele Hi, Si, Ti, i = 1, . . . , r.

Definitia 2.3.2 Prin k-perioada de ocupare vom numi perioada de timp care ncepe cu sosirea

i-cererii n sistemul vacant, unde i k, si sfrseste cnd n sistem nu mai sunt cereri de tip i siserverul a terminat complet lucrul legat de servirea acestor cereri. Notam k-perioada de ocupare

prin k.

Putem reprezenta structura 1-perioadei de ocupare prin urmatoarea diagrama:

Diagrama 2.3.3 1 : 1 99K S1 99K P1 99K T1

Astfel, 1 = 1 + S1 + P1 + T1 si densitatea lui 1 este convolutia densitatilor lui 1, S1, P1, T1.

Transformata Laplace corespunzatoare este egala cu produsul transformatelor Laplace a acestor

variabile aleatoare.

Sunt patru realizari posibile ale 2-perioadei de ocupare.

33

Diagrama 2.3.4

2 : (a) 1

(b) 1 99K S2 99K P2 99K T2(c) 1 99K S2 99K P2 99K T2(d) 1 99K S1 99K P1 99K T1 99K S2 99K P2 99K T2

Prin introducerea notiunii de timp generalizat de ncalzire putem reprezenta ultimile diagrame

(c) si (d) n Diagrama 2.3.4 printr-o diagrama unica. Adica, notam partea 2-perioadei de ocupare

care precede orientarea S2 prin 2 si o numim 2-timp de ncalzire. Astfel, diagramele (c) si (d) din

Diagrama 2.3.4 pot fi reprezentate ca

Diagrama 2.3.5

2 : (e) 2 99K S2 99K P2 99K T2

Aici, 2 sau coincide cu 1 sau are urmatoarea structura: 1 99K S1 99K P1 99K T1, astfel nct2-perioada de ocupare, 2 are urmatoarea structura.

Diagrama 2.3.6

2 : (a) 1

(b) 1 99K S2 99K P2 99K T2(c) 2 99K S2 99K P2 99K T2

In general, notam partea k-perioadei de ocupare care precede orientarii Sk prin k si o numim

k-timp de ncalzire. Sa divizam k-clasa de cereri n doua clase: clasa de k-cereri si (k 1)-clasade cereri. Utiliznd notiunea de k-timp de ncalzire generalizat, k-perioada de ocupare poate fi

reprezentata ntr-o analogie deplina cu 2 (vezi Diagrama 2.3.6).

Urmatoarea diagrama descrie structura perioadei de ocupare k (k = 2, . . . , r).

Diagrama 2.3.7

k : (a) k1

(b) k1 99K Sk 99K Pk 99K Tk(c) k 99K Sk 99K Pk 99K Tk

34

Transformata Laplace a perioadei de ocupare

De subliniat, ca perioada de ocupare este nimic altceva decat r-perioada de ocupare r. Vom

obtine transformata Laplace a perioadei de ocupare prin inductie.

Lema 2.3.8 Fie S si X variabile aleatoare nenegative, N(S) Poisson(S). Fie

F (t) := P(S +N(S)i=1

Xi t),

atunci

F (s) = S(s+ [1 X(s)]). (2.3.2)

Demonstratie.

F (t) = P

S + N(S)i=1

Xi t = t

0

P

N(S)i=1

Xi t s dS(s)

=

t0

k=0

(s)k

k!esXk(t s)dS(s), (2.3.3)

undeXk(ts) este convolutia de k ori a luiX(ts) cu ea nsasi. Calcularea directa a transformateiLaplace-Stieltjes a (2.3.3) ne da (2.3.2).

Din Lema 2.3.8, Diagrama 2.3.3 si din observatiile care succed dupa diagrama urmeaza ca

1(s) = P1(s)1(s+ 1[1 P1(s)])S1(s+ 1[1 P1(s)]) T1(s), (2.3.4)

undeT1(s) = LS[T1](s),

si P1(s) satisface urmatoarea ecuatie Kendall:

P1(s) = B1(s+ 1[1 P1(s)]).

Pentru transformata Laplace-Stieltjes a k-perioadei de ocupare se obtine (Diagrama 2.3.7):

k(s) =k1k

[k1(s+ k) + (k1(s+ k[1 Pk(s)]) k1(s+ k))

Sk(s+ k[1 Pk(s)]) Tk(s)]+

+kk

Pk(s)k(s+ k[1 Pk(s)]) Sk(s+ k[1 Pk(s)]) Tk(s), (2.3.5)

unde

Pk(s) = Hi(s+ k[1 Pk(s)]), (2.3.6)

35

si

k :=ki=1

i, k = 2, . . . , r.

Timpul de ncalzire generalizat k+1 satisface urmatoarea ecuatie n termenii transformatei inte-

grale Laplace-Stieltjes:

(s) =(s+ k)+

+ (k(s+ k[1 Pk(s)]) k(s+ k)) Sk(s+ k[1 Pk(s)]) Tk(s). (2.3.7)

Formule (2.3.4)-(2.3.7) pot fi folosite pentru evaluarea perioadei de ocupare a sistemului, i.e.

r-perioadei de ocupare r. Cu toate acestea, de notat ca aceasta este posibil daca sunt cunoscute

repartitiile lui Hi, Ti, Si. Acestea pot fi gasite pentru fiecare schema a sistemului individual,

utiliznd metoda catastrofelor. Conditiile de stationaritate ct si multe caracteristici ale sistemelor

cu prioritati si timp de orientare descompus pot fi gasite la Volkovinski si Kabalevski (1981).

Vom studia sistemele cu prioritati Mr|Gr|1 si timp de orientare zero n Paragraful 2.4.

2.3.2 Caz special: absenta lucrarilor de terminare a servirii

Presupunem ca Cij Cj := Sj, i.e. serverul nu are nevoie de ceva timp pentru lucrarile de terminarea servirii. Presupunem de asemenea, pentru simplitate, ca timpul initial de ncalzire are repartitie

Heaviside H(t), i.e. este constanta zero.

Pentru unele scheme din clasificarea noastra, sistemele corespunzatoare au fost studiate de

Klimov si Mishkoy (1979). Vom da acum rezultate analitice pentru perioadele de ocupare ale

sistemelor din unele din aceste scheme.

Vom ntroduce mai nti notiunea de perioada de orientare Nk, numita perioada de timp nceputa

de la orientarea la linia k-cererilor si sfrsita cnd serverul este gata de a servi k-cererile. Este evident,

ca Nk Ck, fiindca orientarea poate fi ntrerupta n scheme cu discipline de orientare absoluta.Urmatorul rezultat are loc pentru schemele servirii si orientarii absolute (schemele corespunza-

toare sunt specificate).

Teorema 2.3.9 Pentru schemele de servire resume, servire din nou, cu pierderi are loc

urmatoarea ecuatie:

Nk(s) = Ck(s+ k1)(1 k1

s+ k1[1 Ck(s+ k1)k1(s)]

)1. (2.3.8)

Pentru schema servire neidentica din nou are loc urmatoarea ecuatie:

Hk(s) = B(s+ k1)(1 k1

s+ k1[1 Bk(s+ k1)]k1(s)Nk(s)

)1. (2.3.9)

36

Pentru schema cu pierderi are loc urmatoarea ecuatie:

Hk(s) = Bk(s+ k1) +k1

s+ k1[1 Bk(s+ k1)]k1(s)Nk(s). (2.3.10)

Pentru schema resume are loc urmatoarea ecuatie:

Hk(s) = B(s+ k1[1 k1(s)Nk(s)]). (2.3.11)

Demonstratie. Vom arata ca (2.3.8) si (2.3.10) ntr-adevar au loc, i.e. vom lucra n conditiile

schemei cu pierderi. Mai nti consideram structura k-perioadei de servire Hk si structura k-

perioadei de orientare Nk:

Hk : (a) Bk

(b) k1 99K Nk

Nk : (a) Ck

(b) k1 99K Nk

Aplicnd metoda catastrofelor obtinem:

Hk(s) = Bk(s+ k1) +k1

s+ k1[1 Bk(s+ k1)]k1Nk(s), (2.3.12)

Nk(s) = Ck(s+ k1) +k1

s+ k1[1 Ck(s+ k1)]k1Nk(s), (2.3.13)

si rezolvnd pentru Hk(s) si Nk(s) vom obtine (2.3.10) si (2.3.8), corespunzator. Alte scheme pot

fi analizate n acelasi mod, prin construirea diagramelor realizarilor posibile si aplicarea metodei

catastrofelor.

Introducem acum notiunea de perioada k. Prin aceasta ntelegem perioada de timp, ncepnd

din momentul sosirii k-cererii, cnd nu avem i-cereri (i < k) n sistem si sfrsind cnd sistemul este

liber de k-cereri.

Urmatorul rezultat si demonstrarea lui, bazata pe metoda catastrofelor, pot fi gasite la Klimov

si Mishkoy (1979).

Teorema 2.3.10 Pentru sistemele de asteptare considerate transformata Laplace-Stieltjes a pe-

rioadei de ocupare r poate fi gasita din urmatorul sistem de ecuatii:

k(s) =k1k

k1(s+ k)

+k1k

(k1(s+ k[1 k(s)]) k1(s+ k)

)Nk(s+ k[1 k(s)])

+kk

Nk(s+ k[1 k(s)])k(s),

k(s) =Hk(s+ [1 k(s)]), k = 1, . . . , r.

37

Conditia de stationaritate pentru schema cu pierderi este urmatoarea:

=r

k=1

kbk < 1, (2.3.14)

unde b1 =E[B1]+E[C1]1+1E[C1] , si bi pot fi gasiti din

bi = 1 . . .i11

i1Ci(i1)

(1

Bi(i1) 1), (2.3.15)

1 = 1,i = 1 +i i1i1(i)

i1

(1

Ci(i1) 1), i = 2, . . . , r. (2.3.16)

Primul moment al perioadei de ocupare poate fi usor gasit din rezultatele Teoremei 2.3.10

prin diferentierea transformatei Laplace-Stieltjes corespunzatoare si evaluarea ei la zero, cum este

descris n (2.2.6).

Sa mentionam ca conditia de stationaritate (2.3.14) este obtinuta considernd procesul starilor

m(t), care este un proces regenerativ aperiodic cu puncte de regenerare care coincid cu nceputurile

perioadelor de ocupare ale sistemului. Ciclul de regenerare este suma perioadei de ocupare si a

perioadei libere. Conform teoremei proceselor regenerative a lui Smith conditia suficienta pentru

ca m(t) sa fie ergodic este marginirea mediei ciclului regenerativ. Aceasta este exact echivalenta

cu (2.3.14).

Este posibil de a judeca daca sistemul este stationar cnd suntem capabili de a evalua transfor-

mata Laplace-Stieltjes a perioadei de ocupareeste necesar de a calcula . Mai mult dect att,

multe alte caracteristici de performanta ale sistemului sunt strns legate cu perioada de ocupare,

asa ca extragerea informatiei complete despre perioada de ocupare este o problema foarte impor-

tanta. Mai jos vom arata aceasta dnd un rezultat pentru lungimea sirului stationar. Amnam

aceasta expunere pentru Paragraful 2.5.

2.3.3 Problema descompunerii timpului de orientare

Dupa cum am mentionat mai sus, nu sunt cunoscute rezultate analitice pentru cazul cnd timpul de

orientare este de forma generala. Insa, analiza matematica a comportarii sistemului este posibila

n cazul descompunerii timpului de orientare (1.1.1), dupa cum s-a mentinat n 2.3.1.

Ca o perspectiva, n loc de cautarea rezultatelor analitice pentru sistemele cu orien-

tarea de tip general, noi putem ncerca de a reduce studiul acestor sisteme la studiul

sistemelor cu orientarea de structura specialade exemplu, cu starea neutrala.

Deci consideram urmatoarea problema a descompunerii timpului de orientare. Presupunem

ca este dat un set de r(r 1) variabile aleatoare nenegative independente C = {Cij}ri,j=1;i6=j care

38

reprezinta timpii de orientare n sistemul de asteptare cu prioritati. Apare ntrebarea: cnd acest

set de variabile aleatoare C admite reprezentarea de forma (1.1.1)? Astfel ne ntrebam daca existaseturi T = {Ti}ri=1 si S = {Sj}rj=1 de variabile aleatoare nenegative independente, astfel nct auloc urmatoarele:

Cijdist= Ti + Sj, i 6= j. (2.3.17)

Daca C este asa nct sa nu existe o descompunere exacta de forma (2.3.17), apare ntrebareadespre o reprezentare aproximativa.

Consideram urmatorul exemplu.

Exemplu 2.3.11 Consideram sistemul M3|G3|1 cu repartitia exponentiala a timpului de orientare{Cij}3i,j=1, i 6=j:

Cij Exp(ij), i, j = 1, . . . , 3, si i 6= j,

unde 112 = 12, 113 = 13,

123 = 7,

121 = 10,

131 = 12,

132 = 20. Fie

C12dist= T1 + S2, (2.3.18)

C13dist= T1 + S3, (2.3.19)

C21dist= T2 + S1, (2.3.20)

C23dist= T2 + S3, (2.3.21)

C31dist= T3 + S1, (2.3.22)

C32dist= T3 + S2; (2.3.23)

Rezolvam (2.3.18-2.3.23) pentru timp exponential Ti Exp((T )i ) si Sj Exp((S)j ) n urmatoareaforma echivalenta

112 = ((T )1 )

1 + ((S)2 )1, (2.3.24)

113 = ((T )1 )

1 + ((S)3 )1, (2.3.25)

121 = ((T )2 )

1 + ((S)1 )1, (2.3.26)

123 = ((T )2 )

1 + ((S)3 )1, (2.3.27)

131 = ((T )3 )

1 + ((S)1 )1, (2.3.28)

132 = ((T )3 )

1 + ((S)2 )1. (2.3.29)

Sistemul de ecuatii (2.3.24-2.3.29) nu admite solutie exacta. De aceea se pune urmatoarea prob-

lema:

2 =3

i,j=1, i 6=j(1ij ((T )i )1 ((S)j )1)2 min, (2.3.30)

39

unde toti (T )i si

(S)j sunt numere reale nenegative. Problema (2.3.30) pentru valorile particulare

ale lui lambda date n acest exemplu are urmatoarea solutie

SOL = {((T )1 )1 = t, ((T )2 )1 = t 2, ((T )3 )1 = 4 + t,(

(S)1 )

1 = 10 t, ((S)2 )1 = 14 t, ((S)3 )1 = 11 t},

unde t [2, 10]. Aceasta solutie pentru setul particular a lui {ij} poate fi obtinuta din solutiagenerala a sistemului (2.3.24-2.3.29):

SOL = {(T )1 = t,(

(T )2 )

1 =1

3(3t 2113 112 + 121 + 2123 131 + 132 ),

((T )3 )

1 =1

3(3t 113 2112 121 + 123 + 131 + 2132 ),

((S)1 )

1 =1

2(2t+ 113 + 112 + 121 123 + 131 132 ),

((S)2 )

1 =1

6(6t+ 113 + 5112 + 121 123 131 + 132 ),

((S)3 )

1 =1

6(6t+ 5113 + 112 121 + 123 + 131 132 )}, (2.3.31)

unde t este ales corespunzator, astfel nct toate ratele de orientare sunt nenegative, daca aceasta

este posibil.

Valoarea corespunzatoare a lui 2 este urmatoarea

2min =1

6(112 113 + 123 121 + 131 132 )2,

astfel conditia descompunerii exacte este urmatoarea:

112 + 123 +

131 =

113 +

132 +

121 . (2.3.32)

In acest caz

SOL = {((T )1 )1 = t,(

(T )2 )

1 = t 113 + 123 ,(

(T )3 )

1 = t 112 + 132 ,(

(S)1 )

1 = t+ 113 + 121 123 ,(

(S)2 )

1 = t+ 112 ,(

(S)3 )

1 = t+ 113 }, (2.3.33)

unde

t (max{0, 113 123 , 112 132 },min{112 , 113 , 113 + 121 123 }),

numai daca acest interval nu are lungime negativa. In acest caz reparametrizam solutia.

40

Din exemplu s-a observat ca pentru un sistem G3|G3|1 cu timp de orientare exponential acestanu admite descompunere exacta de forma (1.1.1). Totusi, descompunerea aproximativa n aceeasi

clasa a sistemelor cu timp de orientare exponential este posibila n sensul problemei (2.3.30).

Ce se ntmpla daca timpul de orientare nu este repartizat exponential?

Imposibilitatea descompunerii exacte a timpului de orientare conduce la o problema aproxima-

tiva care poate fi formulata ntr-o forma destul de generala.

Presupunem ca {Ti}ri=1 sunt variabile aleatoare nenegative si independente cu functiile derepartitie {Ti(t)}ri=1, si {Sj}rj=1 sunt variabile aleatoare nenegative si independente cu functiilede repartitie {Sj(t)}rj=1. Notam functia de repartitie a sumei lui Ti si Sj prin Wij(t), i.e. Wij(t)este convolutia Stieltjes a functiilor Ti(t) si Sj(t):

Wij(t) = Ti(t) Sj(t) =t

0

Ti(t x)dSj(x) =t

0

Sj(t x)dTi(x).

Acum punem urmatoarea problema:

=

i,j=1,...,r;i6=j||Wij(t) Cij(t)|| min, (2.3.34)

pentru setul dat de f.c.r. {Cij(t)}. Aici || || denota norma maxt[0,)

|F (t)| n familia functiilormarginite pe R+. La fel pot fi considerate si alte norme.

Pare rezonabil de a discretiza problema(2.3.34) n urmatorul mod. Consideram partitia pe R+:

= {0 = t0 < t1 < t2 < . . . < tn < . . .},

si consideram Wij(t) de forma urmatoare:

Wij(t) =

n:t(tn1,tn]k=0

Ti(t tk)Sj(tk),

pentru fiecare consideram analogul problemei (2.3.34):

=

i,j=1,...,r;i6=j||Wij(t) Cij(t)|| min, (2.3.35)

unde norma || || este definita acum n urmatorul mod:

||F (t)|| = maxt

|F (t)|.

Trebuie sa cerem ca sa fie o multime de puncte de crestere pentru functiile {Ti(t)}ri=1 si {Sj}rj=1.Expunem acum o varianta a formalizarii problemei de descompunere efectiva a timpului de

orientare n urmatorul mod. Pentru orice eveniment elementar rezolvam urmatoarea problema

de optimizaren

i,j=1;i6=j(Cij() Ti() Sj())2 min, (2.3.36)

41

unde, la fel ca mai sus, Ti si Sj sunt variabile aleatoare nenegative. Problema (2.3.36) se reduce la

urmatorul sistem de ecuatii liniare:(n 1)In UnUn (n 1)In

T()S()

= C(), (2.3.37)unde

C() =

nj=2

C1j()

nj=1,j 6=2

C2j()

. . .n1j=1

Cnj()

ni=2

Ci1()

ni=1,i6=2

Ci2()

. . .n1i=1

Cin()

, (2.3.38)

si

T() =(T1() T2() . . . Tn()

)T,

S() =(S1() S2() . . . Sn()

)T.

Matricea In n (2.3.37) este o matrice identica n n si Un este o matrice n n de urmatoareaforma:

Un =

0 1 . . . 1

1 0 1... . . .

. . ....

1 1 . . . 0

,i.e., matricea unitatilor cu zerouri pe diagonala principala.

Matricea coeficientilor pentru partea stnga a (2.3.37) este degenerata cu determinantul egal cu

zero si aceasta matrice nu este de rang complet. De aceea, putem folosi matricea inversa Moore-

Penrose la rezolvarea sistemului. Aceasta matrice poseda urmatoare proprietate:

norma ||AXC|| este minimizata,

unde

A =

(n 1)In UnUn (n 1)In

si X =TS

.

42

Fiind rezolvat n sensul indicat, sistemul (2.3.37) ne da expresiile pentru {Ti()}ni=1 si {Sj()}nj=1n termenii {Cij()}ni,j=1;i6=j. Astfel, repartitiile lui Ti si Sj care fac parte din descompunere aditiva(n mod aproximativ cerut de (2.3.36)) a timpilor Cij sunt doar convolutii ale lui {Sj}nj=1.

Cum poate fi usor vazut, unele elemente ale matricei inverse la matricea din partea stanga

a ecuatiei (2.3.37) sunt negative, ceea ce rezula n faptul ca multimi de suport ai lui Cij() vor

intersecta semiaxa reala negativa Raceasta nseamna, ca, n general, problema relaxata nu ne

da solutia admisibila la problema originala. Insa, daca partile negative ale repartitiilor Ti si

Sj sunt de masa relativ mica, masele acestor parti pot fi transferate n partea pozitiva. Asa

repartitii noi formate pot servi ca aproximari la solutie.

Matricea A este matricea-bloc simetrica doi-pe-doi. Formulele de inversare a astfel de matrici

pot fi gasite n Jo s. a. (2004). Acesti autori prezinta formulele pentru inversarea matricelor-bloc

simetrice de rang complet cu ajutorul complimentarilor Schur si decompozitiei bloc-triunghiulare.

Insa, matricea A nu este o matrice de rang complet, dupa cum deja s-a mentionat. Pentru a

gasi matricea inversa Moore-Penrose a matricei A noi folosim metoda descompunerii dupa valori

singulare. Aceasta spune, ca matricea pseudoinversa Moore-Penrose a matricei reale A, care are

descompunere dupa valori singulare n forma A = UV T , este egala A+ = V UT . Aici, este

matricea de valori singulare ale lui A pe diagonala principala si este matricea inversa a matricei

T . Reamintim, ca este matricea n n, din ce rezulta, ca 1.

Exemplu 2.3.12 Acest exemplu arata ca solutia la problema relaxata de descompunere a timpi-

lor de orientare, obtinuta cu ajutorul matricei pseudoinverse Moore-Penrose poate sa nu fie buna

pentru transferul maselor, si ca consecinta, pentru solutionarea problemei de descompunere.

Consideram 6 timpi de orientare repartizate exponental cu parametrii care satisfac (2.3.32), si

anume, fie

112 = 1, 113 = 3,

121 = 4, 123 = 2.5,

131 = 5, 132 = 1.5.

Matricea inversa respectiva Moore-Penrose pentru rezolvarea problemei (2.3.36) n acest exemplu

este urmatoare:

A+ =

0.4861 0.1806 0.1806 0.2639 0.0694 0.06940.1806 0.4861 0.1806 0.0694 0.2639 0.06940.1806 0.1806 0.4861 0.0694 0.0694 0.26390.2639 0.0694 0.0694 0.4861 0.1806 0.18060.0694 0.2639 0.0694 0.1806 0.4861 0.18060.0694 0.0694 0.2639 0.1806 0.1806 0.4861

.

43

Solutia la problema relaxata de descompunere poate fi reprezentata cu ajutorul histogramelor

pentru variabile aleatoare T1, T2, T3, S1, S2, S3, care se gasesc din formula:TS

= A+C,unde C este definit prin (2.3.38).

Aceste variabile sunt reprezentate n Figura 2.1. Intersectarile suporturilor acestor variabile cu

semiaxa negativa sunt foarte esentiale pentru ca sa fie ignorate.

10 5 0 5 10 15 200

20

40

60

80

100

120

140

160

180Sampling distribution of T1

(a) Histograma pentru T1

15 10 5 0 5 10 15 20 25 300

50

100

150

200

250


(b) Histograma pentru T2

10 5 0 5 10 15 20 25 30 350

50

100

150

200

250

300


(c) Histograma pentru T3

10 5 0 5 10 15 20 25 300

50

100

150

200

250Sampling distribution of S1

(d) Histograma pentru S1

15 10 5 0 5 10 150

50

100

150

200


(e) Histograma pentru S2

10 5 0 5 10 15 20 250

50

100

150

200


(f) Histograma pentru S3

Figura 2.1: Solutiile pentru T1, T2, T3, S1, S2, S3.

Problemele (2.3.34)-(2.3.37) cu restrictia T > 0, S > 0 pot fi rezolvate numeric. Cu toate

acestea, legatura dintre solutiile acestor probleme este obiect de studiu pentru viitoarele cercetari.

Exista nca cel putin o metoda de tratare a problemei de decompozitie efectiva a timpilor de

orientare. Urmatoarea expunere este bazata pe o frumoasa proprietate a cumulantilor.

Metoda cumulantilor

Problema descompunerii (2.3.17) conduce n mod natural la o problema aproximativa, deoarece

solutia exacta nu este ntotdeauna posibila. Mai mult, sunt diferite moduri de a ntelege avantajul

acestei aproximari.

Reamintim, ca repartitia poate fi caracterizata prin momentele sale, desi nu ntotdeauna ntr-un

mod unic. Cu toate acestea, algebra variabilelor aleatoare, n special cnd sunt variabile aleatoare

independente, poate fi eficient efectuata si analizata cu ajutorul cumulantilorcaracteristici alter-

native ale variabilelor aleatoare si ale functiilor de repartitie.

Reamintim ca cumulantii {p}k=1 repartitiilor F (t) sunt coeficientii extinderii seriei logaritmului

44

functiei caracteristice a lui F (t). In mod caracteristic, daca

(u) =

eiutdF (t) =

eiutf(t)dt,

este functia caracteristica a repartitiei F (t), atunci {p}p=1 face parte din urmatoarea extindere:

K(u) = ln(u) =p=1

pp!(iu)p,

astfel nct

p = ipK(p)(0) = ip

dp ln(0)

dup.

Proprietatile functiilor caracteristice.

Functiile caracteristice satisfac urmatoarele proprietati:

1. ntotdeauna exista, deoarece densitatile sunt absolut integrabile;

2. densitatea corespunzatoare anumitei functii caracteristice poate fi gasita folosind urmatoarea

formula inversa:

p(x) =1

2pi

(u)eiuxdu.

Totusi, aceasta integrala nu este numaidect convergenta. Daca nu este, atunci convenim sa

ntelegem prin valoarea sa valoarea principala a integralei improprii corespunzatoare;

3. (0) = 1;

4. (u) C1;

5. |(u)| (0);

6. (u) = (u);

7.

(u)eiuxdu 0.

Ultimele trei proprietati ale functiilor caracteristice mpreuna cu faptul ca sunt nenegative la

zero arata ca functiile caracteristice sunt functii pozitiv definite.

Teorema 2.3.13 (Bochner-Khintchin) Pentru ca functiile continui (u), cu proprietatea (0) = 1,

sa fie functii caracteristice a carorva repartitii este necesar si suficient ca (u) sa fie pozitiv definite.

Legatura dintre cumulanti si momente.

Introducem notatia:

()n < n >:=+

xnp(x)dx, (2.3.39)

45

si

()n :=< ( < >)n >, (2.3.40)unde n este momentul de ordinul n si n este momentul central de ordinul n al variabilei aleatoare

. In mod particular,

()1 =< >= E [] = m,

si

()2 < ( < >)2 >= E

[( E)2] = V[] = 2 = V.

Vom omite scrierea si scriem n si n pentru simplitate.

Este binecunoscuta legatura dintre momente si momentele centrale ale variabilei aleatoare:

n =n

p=0

Cpnp1np (2.3.41)

n =n

p=0

(1)pCpnp1np. (2.3.42)

Legatura dintre momente si cumulanti este urmatoarea:

1 = 1 = m (2.3.43)

2 = 2 21 = V (2.3.44)3 = 3 312 + 231 (2.3.45)4 = 4 322 413 + 12212 641 (2.3.46)5 = 5 512 1023 + 20213 + 30122 60312 + 2451 (2.3.47). . .

si

1 = 1 (2.3.48)

2 = 2 + 21 (2.3.49)

3 = 3 + 312 + 31 (2.3.50)

4 = 4 + 322 + 413 + 6

212 +

41 (2.3.51)

5 = 5 + 514 + 1023 + 10312 + 151

22 +

51 (2.3.52)

. . .

Legatura dintre cumulanti si momentele centrale poate fi usor obtinuta din (2.3.43)-(2.3.47).

Semnificatia primelor patru cumulanti este urmatoarea:

1 = meste media;

2 = Veste variatia;

46

3asimetria repartitiei (este diferita de zero doar pentru repartitiile care sunt nesimetrice

fata de medie);

4excesul repartitiei (4 > 0repartitia este amagitoare, mai slaba dect Gauss, altfel

4 < 0).

Momentele si cumulantii repartitiei comune (cazul a 2 variabile)

Repartitia vectorului aleator (, ) este data complet, de exemplu, de functia densitatii comune

p,(x, y), ce safisface identitatile:

p,(x, y) = p(x)p(x|y) = p(y)p(y|x),

unde p(x) si p(y) s

Modelarea Timpului de Orientare in Sisteme de Asteptare Cu Prioritati

Documents

Transcript of Modelarea Timpului de Orientare in Sisteme de Asteptare Cu Prioritati