← Retour aux Cours 2023-2024

Processus Stochastiques et Files d'Attentes

PARTIE A : GENERALITES

Presentation

Le cours "Processus Stochastiques et Files d'Attentes" etudie les systemes aleatoires evoluant dans le temps et les modeles de files d'attente. Ces outils mathematiques permettent d'analyser et d'optimiser des systemes ou l'aleatoire joue un role central: reseaux de telecommunications, systemes de production, services, trafic routier. La theorie des files d'attente est essentielle pour dimensionner des ressources et predire les performances.

Annee Academique : 2023-2024
Semestre : 8
Categorie : Mathematiques Appliquees / Recherche Operationnelle

PARTIE B : PARTIE DESCRIPTIVE

Details de l'experience

Environnement et contexte

Le cours combinait theorie probabiliste rigoureuse avec applications pratiques via simulations (Python). Nous avons modelise et analyse divers systemes : guichets de banque, serveurs Web, lignes de production, reseaux telephoniques. Les outils developpes permettent de repondre a des questions cruciales: combien de serveurs necessaires? Quel temps d'attente moyen? Quelle probabilite de saturation?

Ma fonction

Dans ce cours, j'ai ete responsable de :

  • Comprendre les processus stochastiques (chaines de Markov, processus de Poisson)
  • Modeliser des systemes par files d'attente (notation de Kendall)
  • Calculer les performances (temps d'attente, longueur de file, taux d'utilisation)
  • Analyser la stabilite des systemes
  • Optimiser le dimensionnement de ressources
  • Simuler des systemes complexes
  • Interpreter les resultats et faire des recommandations

PARTIE C : PARTIE TECHNIQUE

Cette section explore les aspects techniques des processus stochastiques et des files d'attente.

Concepts techniques appris

1. Variables Aleatoires et Lois de Probabilite

Lois Discretes :

Bernoulli : B(p)

  • Succes (1) avec probabilite p, echec (0) avec 1-p

Binomiale : B(n,p)

  • Nombre de succes sur n essais independants
  • E[X] = np, Var(X) = np(1-p)

Geometrique : G(p)

  • Nombre d'essais avant premier succes
  • E[X] = 1/p, propriete sans memoire

Poisson : P(lambda)

  • Nombre d'evenements sur intervalle
  • P(X=k) = (lambda^k e^(-lambda))/k!
  • E[X] = Var(X) = lambda

Lois Continues :

Uniforme : U(a,b)

  • Equiprobable sur [a,b]

Exponentielle : Exp(lambda)

  • Temps entre evenements (processus de Poisson)
  • f(x) = lambda*e^(-lambda*x) pour x>=0
  • E[X] = 1/lambda, Var(X) = 1/lambda^2
  • Propriete sans memoire : P(X>s+t|X>s) = P(X>t)

Normale (Gaussienne) : N(mu, sigma^2)

  • Courbe en cloche
  • Theoreme Central Limite

2. Processus de Poisson

Definition :

Processus de comptage N(t) modelisant arrivees aleatoires.

Proprietes :

  • Stationnaire : taux lambda constant
  • Increments independants
  • Nombre d'arrivees sur [0,t] : N(t) ~ Poisson(lambda*t)
  • Temps inter-arrivees : Exp(lambda)

Applications :

  • Arrivees de clients
  • Pannes d'equipements
  • Appels telephoniques
  • Requetes Web

3. Chaines de Markov

Definition :

Processus stochastique sans memoire (propriete de Markov) :

P(X_(n+1) | X_0,...,X_n) = P(X_(n+1) | X_n)

Matrice de transition P :

P_ij = P(X_(n+1)=j | X_n=i)

Chaine homogene : P constante dans le temps.

Distribution stationnaire pi :

pi = pi * P
Somme(pi_i) = 1

Si chaine irreductible et aperiodique, distribution stationnaire existe et unique.

Classification des etats :

  • Recurrent : reviendra avec probabilite 1
  • Transient : peut ne jamais revenir
  • Absorbant : P(rester) = 1

4. Notation de Kendall

A/S/c/K/N/D :

  • A : loi d'arrivees (M=Markov/exponentiel, D=deterministe, G=general)
  • S : loi de service
  • c : nombre de serveurs
  • K : capacite max (file + service)
  • N : taille population
  • D : discipline (FIFO, LIFO, etc.)

Souvent abrege : A/S/c

Exemples :

  • M/M/1 : Poisson/Exp/1 serveur
  • M/M/c : Poisson/Exp/c serveurs
  • M/G/1 : Poisson/General/1 serveur

5. File M/M/1

Systeme :

  • Arrivees : Poisson(lambda)
  • Service : Exp(mu)
  • 1 serveur
  • Capacite infinie

Intensite de trafic :

rho = lambda / mu

Condition de stabilite :

rho < 1  (sinon file explose)

Performances a l'etat stationnaire :

Probabilite de n clients :

pi_n = (1 - rho) * rho^n

Nombre moyen de clients :

L = rho / (1 - rho) = lambda / (mu - lambda)

Nombre moyen en file d'attente :

Lq = rho^2 / (1 - rho) = lambda^2 / (mu * (mu - lambda))

Temps moyen dans le systeme (Little) :

W = L / lambda = 1 / (mu - lambda)

Temps moyen d'attente :

Wq = Lq / lambda = lambda / (mu * (mu - lambda))

6. Loi de Little

Theoreme fondamental :

L = lambda * W

Ou :

  • L : nombre moyen de clients dans systeme
  • lambda : taux d'arrivee
  • W : temps moyen dans systeme

Valable pour :

  • Tout systeme stable
  • Arrivees et services quelconques

Corollaire :

Lq = lambda * Wq

7. File M/M/c

c serveurs en parallele.

Intensite de trafic :

rho = lambda / (c * mu)  (charge par serveur)

Condition de stabilite :

lambda < c * mu  (ou rho < 1)

Formule d'Erlang C (probabilite d'attente) :

P(attente) = C(c, lambda/mu)

Formule complexe, souvent tabulee ou calculee numeriquement.

Performances :

Formules plus complexes que M/M/1, mais meme logique.

Application : centres d'appels, guichets de banque.

8. File M/G/1 (Pollaczek-Khinchin)

Service general (pas forcement exponentiel).

Intensite de trafic :

rho = lambda / mu  (avec mu = 1/E[S])

Formule de Pollaczek-Khinchin :

Lq = (lambda^2 * Var(S) + rho^2) / (2 * (1 - rho))

Implications :

  • Plus variance du service est grande, plus la file est longue
  • Service deterministe (Var=0) minimal

Cas particuliers :

  • M/M/1 : Var(S) = 1/mu^2 → retrouve formule classique
  • M/D/1 : Var(S) = 0 → Lq reduit de moitie

9. Files avec Capacite Limitee

File M/M/1/K :

Capacite max K (file + service).

Arrivees refusees si systeme plein.

Pas de condition de stabilite (rho peut etre >1).

Probabilite de blocage :

P_blocage = pi_K = (1 - rho) * rho^K / (1 - rho^(K+1))  si rho != 1
P_blocage = 1 / (K+1)  si rho = 1

Taux effectif d'arrivee :

lambda_eff = lambda * (1 - P_blocage)

Applications : buffers limites, systemes avec rejet.

10. Reseaux de Files d'Attente

Systemes interconnectes : sortie d'une file = entree d'une autre.

Reseaux ouverts : arrivees externes, departs externes.

Reseaux fermes : nombre fixe de clients circulant.

Theoreme de Jackson :

Pour reseau ouvert de files M/M/· :

  • Chaque file se comporte comme M/M/· independante
  • Distribution produit : pi = pi_1 x pi_2 x ... x pi_n

Simplification majeure : analyse file par file.

Applications : reseaux informatiques, systemes de production.

11. Optimisation de Systemes

Problemes typiques :

  • Combien de serveurs pour temps d'attente acceptable?
  • Trade-off cout serveurs vs cout d'attente clients
  • Quelle capacite de buffer?

Fonction de cout :

C = c_s * c + c_w * W

Ou :

  • c_s : cout par serveur
  • c : nombre de serveurs
  • c_w : cout d'attente par unite de temps
  • W : temps moyen d'attente

Optimisation :

Minimiser C en variant c.

Niveaux de Service :

Exemples :

  • 80% des clients servis en moins de 20s
  • Temps d'attente moyen < 5min

12. Simulation de Files d'Attente

Simulation a evenements discrets :

Evenements :

  • Arrivee client
  • Debut service
  • Fin service

Algorithme :

  1. Initialiser (file vide, t=0)
  2. Generer evenements futurs (arrivees aleatoires)
  3. Traiter evenement le plus proche dans le temps
  4. Mettre a jour etat systeme
  5. Generer nouveaux evenements si necessaire
  6. Repeter jusqu'a temps final

Generateurs aleatoires :

  • Exponentiel : -ln(U)/lambda ou U~Uniforme(0,1)
  • Autres lois : methodes de transformation

Analyse resultats :

  • Phase transitoire vs regime stationnaire
  • Intervalle de confiance (simulations multiples)

Avantages simulation :

  • Systemes complexes (lois non standard, priorites, etc.)
  • Validation modeles analytiques

PARTIE D : PARTIE ANALYTIQUE

Connaissances et competences mobilisees

  • Probabilites et statistiques
  • Processus stochastiques (Poisson, Markov)
  • Modelisation de systemes par files d'attente
  • Calcul de performances (formules analytiques)
  • Analyse de stabilite
  • Optimisation (dimensionnement)
  • Simulation (Python)
  • Interpretation et communication de resultats

Auto-evaluation

Ce cours a ete mathematiquement exigeant mais tres enrichissant. La theorie des files d'attente offre des outils puissants pour analyser des systemes courants dans l'industrie et les services.

Les processus de Poisson et la loi exponentielle sont omnipresents en modelisation. Leur propriete sans memoire les rend mathematiquement maniables et souvent realistes pour modeliser arrivees aleatoires.

La file M/M/1, bien que simple, introduit tous les concepts essentiels. Comprendre intuitivement pourquoi L = rho/(1-rho) explose quand rho tend vers 1 est important. Quand le systeme est proche de la saturation, les files deviennent tres longues.

La loi de Little (L = lambda*W) est remarquablement generale et utile. C'est une des rares relations valables quel que soit le systeme (tant qu'il est stable).

Les files M/M/c et les formules d'Erlang sont pratiques pour dimensionner des centres d'appels ou guichets. La question "combien de serveurs pour un temps d'attente acceptable?" est tres concrete.

La formule de Pollaczek-Khinchin (M/G/1) montre l'impact de la variabilite du service. Reduire la variance (standardiser les processus) ameliore les performances meme a charge egale.

Les reseaux de files (theoreme de Jackson) permettent d'analyser des systemes complexes. La simplification (comportement independant) est puissante mais repose sur hypotheses fortes (Markov).

Les simulations sont necessaires quand les modeles analytiques deviennent intractables (files avec priorites, distributions generales, politiques complexes). Coder des simulations m'a donne une comprehension profonde de la dynamique des files.

L'optimisation cout/performance est au coeur des decisions industrielles. Les outils de ce cours permettent de quantifier les trade-offs et prendre des decisions eclairees.

Mon avis

Ce cours fournit des outils essentiels pour l'ingenieur confronte a des systemes avec alea et congestion. Les applications sont omnipresentes.

Points forts :

  • Rigueur mathematique
  • Modeles analytiques elegants (formules fermees)
  • Applications variees et concretes
  • Simulation pour systemes complexes

Points a ameliorer :

  • Plus d'etudes de cas industriels
  • Lien avec theorie du controle (controle admission, regulation)
  • Files d'attente dans contexte Big Data et cloud

Reflexions personnelles :

La theorie des files d'attente a ete developpee il y a un siecle (Erlang pour reseaux telephoniques) mais reste d'actualite. Les problemes fondamentaux (dimensionnement, optimisation) sont les memes, seul le contexte change.

Les limites des modeles doivent etre comprises :

  • Hypotheses (Poisson, exponentiel) pas toujours realistes
  • Regime stationnaire suppose systeme stable longtemps
  • Modeles simplifies vs realite complexe

Cependant, meme approximatifs, les modeles donnent des ordres de grandeur et intuitions precieux. "All models are wrong, but some are useful."

Applications modernes :

  • Cloud computing : dimensionnement serveurs, auto-scaling
  • Reseaux : routeurs, buffers, QoS
  • E-commerce : gestion stocks, livraisons
  • Sante : urgences, blocs operatoires
  • Transport : trafic, parkings

L'explosion du trafic Internet et du cloud a renouvele l'interet pour ces theories. Les data centers utilisent massivement la theorie des files pour optimiser ressources.

Le lien avec l'IA :

Le Machine Learning peut predire les arrivees (lambda variable dans le temps) et adapter dynamiquement les ressources. Combiner modeles stochastiques classiques avec apprentissage automatique est une voie prometteuse.

En conclusion, ce cours sur les processus stochastiques et files d'attente fournit des outils puissants pour modeliser et analyser l'incertitude, les dependances temporelles et les performances des systemes. C'est une complementation essentielle aux cours de signal (aleatoire) et un prerequis pour comprendre beaucoup de problemes d'ingenierie reels.

Documents de Cours

Polycopie Processus Stochastiques

Cours complet : chaines de Markov, processus de Poisson, files d'attente et analyse de performance.

Telecharger

Chaines de Markov a Temps Discret

DTMC : matrices de transition, probabilites stationnaires, classification d'etats et ergodicite.

Telecharger

Theorie des Files d'Attente

Modeles M/M/1, M/M/c, formules de Little, temps d'attente, taux d'occupation et optimisation.

Telecharger

Stochastic Processes and Queueing Theory

PART A: GENERALITIES

Presentation

The "Stochastic Processes and Queueing Theory" course studies random systems evolving over time and queueing models. These mathematical tools allow us to analyze and optimize systems where randomness plays a central role: telecommunications networks, production systems, services, and road traffic. Queueing theory is essential for sizing resources and predicting performance.

Academic Year: 2023-2024
Semester: 8
Category: Applied Mathematics / Operations Research

PART B: DESCRIPTIVE PART

Experience Details

Environment and Context

The course combined rigorous probabilistic theory with practical applications through simulations (Python). We modeled and analyzed various systems: bank counters, Web servers, production lines, and telephone networks. The tools developed allow us to answer crucial questions: how many servers are needed? What is the average waiting time? What is the probability of saturation?

My Function

In this course, I was responsible for:

  • Understanding stochastic processes (Markov chains, Poisson processes)
  • Modeling systems using queueing theory (Kendall notation)
  • Computing performance metrics (waiting time, queue length, utilization rate)
  • Analyzing system stability
  • Optimizing resource sizing
  • Simulating complex systems
  • Interpreting results and making recommendations

PART C: TECHNICAL PART

This section explores the technical aspects of stochastic processes and queueing theory.

Technical Concepts Learned

1. Random Variables and Probability Distributions

Discrete Distributions:

Bernoulli: B(p)

  • Success (1) with probability p, failure (0) with 1-p

Binomial: B(n,p)

  • Number of successes over n independent trials
  • E[X] = np, Var(X) = np(1-p)

Geometric: G(p)

  • Number of trials before first success
  • E[X] = 1/p, memoryless property

Poisson: P(lambda)

  • Number of events over an interval
  • P(X=k) = (lambda^k e^(-lambda))/k!
  • E[X] = Var(X) = lambda

Continuous Distributions:

Uniform: U(a,b)

  • Equally probable over [a,b]

Exponential: Exp(lambda)

  • Time between events (Poisson process)
  • f(x) = lambda*e^(-lambda*x) for x>=0
  • E[X] = 1/lambda, Var(X) = 1/lambda^2
  • Memoryless property: P(X>s+t|X>s) = P(X>t)

Normal (Gaussian): N(mu, sigma^2)

  • Bell curve
  • Central Limit Theorem

2. Poisson Process

Definition:

Counting process N(t) modeling random arrivals.

Properties:

  • Stationary: constant rate lambda
  • Independent increments
  • Number of arrivals on [0,t]: N(t) ~ Poisson(lambda*t)
  • Inter-arrival times: Exp(lambda)

Applications:

  • Customer arrivals
  • Equipment failures
  • Telephone calls
  • Web requests

3. Markov Chains

Definition:

Memoryless stochastic process (Markov property):

P(X_(n+1) | X_0,...,X_n) = P(X_(n+1) | X_n)

Transition matrix P:

P_ij = P(X_(n+1)=j | X_n=i)

Homogeneous chain: P constant over time.

Stationary distribution pi:

pi = pi * P
Sum(pi_i) = 1

If the chain is irreducible and aperiodic, the stationary distribution exists and is unique.

State classification:

  • Recurrent: will return with probability 1
  • Transient: may never return
  • Absorbing: P(staying) = 1

4. Kendall Notation

A/S/c/K/N/D:

  • A: arrival distribution (M=Markov/exponential, D=deterministic, G=general)
  • S: service distribution
  • c: number of servers
  • K: maximum capacity (queue + service)
  • N: population size
  • D: discipline (FIFO, LIFO, etc.)

Often abbreviated: A/S/c

Examples:

  • M/M/1: Poisson/Exp/1 server
  • M/M/c: Poisson/Exp/c servers
  • M/G/1: Poisson/General/1 server

5. M/M/1 Queue

System:

  • Arrivals: Poisson(lambda)
  • Service: Exp(mu)
  • 1 server
  • Infinite capacity

Traffic intensity:

rho = lambda / mu

Stability condition:

rho < 1  (otherwise queue explodes)

Steady-state performance:

Probability of n customers:

pi_n = (1 - rho) * rho^n

Average number of customers:

L = rho / (1 - rho) = lambda / (mu - lambda)

Average number in queue:

Lq = rho^2 / (1 - rho) = lambda^2 / (mu * (mu - lambda))

Average time in system (Little):

W = L / lambda = 1 / (mu - lambda)

Average waiting time:

Wq = Lq / lambda = lambda / (mu * (mu - lambda))

6. Little's Law

Fundamental theorem:

L = lambda * W

Where:

  • L: average number of customers in system
  • lambda: arrival rate
  • W: average time in system

Valid for:

  • Any stable system
  • Any arrival and service distributions

Corollary:

Lq = lambda * Wq

7. M/M/c Queue

c servers in parallel.

Traffic intensity:

rho = lambda / (c * mu)  (load per server)

Stability condition:

lambda < c * mu  (or rho < 1)

Erlang C formula (probability of waiting):

P(wait) = C(c, lambda/mu)

Complex formula, often tabulated or computed numerically.

Performance:

Formulas more complex than M/M/1, but same logic.

Application: call centers, bank counters.

8. M/G/1 Queue (Pollaczek-Khinchin)

General service (not necessarily exponential).

Traffic intensity:

rho = lambda / mu  (with mu = 1/E[S])

Pollaczek-Khinchin formula:

Lq = (lambda^2 * Var(S) + rho^2) / (2 * (1 - rho))

Implications:

  • The greater the service variance, the longer the queue
  • Deterministic service (Var=0) is minimal

Special cases:

  • M/M/1: Var(S) = 1/mu^2 → recovers the classical formula
  • M/D/1: Var(S) = 0 → Lq is halved

9. Queues with Limited Capacity

M/M/1/K Queue:

Maximum capacity K (queue + service).

Arrivals rejected if system is full.

No stability condition (rho can be >1).

Blocking probability:

P_blocking = pi_K = (1 - rho) * rho^K / (1 - rho^(K+1))  if rho != 1
P_blocking = 1 / (K+1)  if rho = 1

Effective arrival rate:

lambda_eff = lambda * (1 - P_blocking)

Applications: limited buffers, systems with rejection.

10. Queueing Networks

Interconnected systems: output of one queue = input to another.

Open networks: external arrivals, external departures.

Closed networks: fixed number of customers circulating.

Jackson's Theorem:

For an open network of M/M/· queues:

  • Each queue behaves as an independent M/M/· queue
  • Product-form distribution: pi = pi_1 x pi_2 x ... x pi_n

Major simplification: queue-by-queue analysis.

Applications: computer networks, production systems.

11. System Optimization

Typical problems:

  • How many servers for an acceptable waiting time?
  • Trade-off between server cost vs customer waiting cost
  • What buffer capacity?

Cost function:

C = c_s * c + c_w * W

Where:

  • c_s: cost per server
  • c: number of servers
  • c_w: waiting cost per unit of time
  • W: average waiting time

Optimization:

Minimize C by varying c.

Service Levels:

Examples:

  • 80% of customers served in less than 20s
  • Average waiting time < 5min

12. Queueing Simulation

Discrete-event simulation:

Events:

  • Customer arrival
  • Service start
  • Service end

Algorithm:

  1. Initialize (empty queue, t=0)
  2. Generate future events (random arrivals)
  3. Process the nearest event in time
  4. Update system state
  5. Generate new events if necessary
  6. Repeat until final time

Random generators:

  • Exponential: -ln(U)/lambda where U~Uniform(0,1)
  • Other distributions: transformation methods

Results analysis:

  • Transient phase vs steady state
  • Confidence intervals (multiple simulations)

Advantages of simulation:

  • Complex systems (non-standard distributions, priorities, etc.)
  • Validation of analytical models

PART D: ANALYTICAL PART

Knowledge and Skills Mobilized

  • Probability and statistics
  • Stochastic processes (Poisson, Markov)
  • System modeling using queueing theory
  • Performance computation (analytical formulas)
  • Stability analysis
  • Optimization (resource sizing)
  • Simulation (Python)
  • Interpretation and communication of results

Self Evaluation

This course was mathematically demanding but very rewarding. Queueing theory provides powerful tools for analyzing common systems in industry and services.

Poisson processes and the exponential distribution are ubiquitous in modeling. Their memoryless property makes them mathematically tractable and often realistic for modeling random arrivals.

The M/M/1 queue, although simple, introduces all essential concepts. Intuitively understanding why L = rho/(1-rho) explodes as rho approaches 1 is important. When the system is close to saturation, queues become very long.

Little's law (L = lambda*W) is remarkably general and useful. It is one of the rare relationships valid regardless of the system (as long as it is stable).

M/M/c queues and Erlang formulas are practical for sizing call centers or bank counters. The question "how many servers for an acceptable waiting time?" is very concrete.

The Pollaczek-Khinchin formula (M/G/1) shows the impact of service variability. Reducing variance (standardizing processes) improves performance even at equal load.

Queueing networks (Jackson's theorem) allow analyzing complex systems. The simplification (independent behavior) is powerful but relies on strong assumptions (Markov).

Simulations are necessary when analytical models become intractable (queues with priorities, general distributions, complex policies). Coding simulations gave me a deep understanding of queue dynamics.

Cost/performance optimization is at the heart of industrial decisions. The tools from this course allow quantifying trade-offs and making informed decisions.

My Opinion

This course provides essential tools for engineers facing systems with randomness and congestion. The applications are ubiquitous.

Strengths:

  • Mathematical rigor
  • Elegant analytical models (closed-form formulas)
  • Varied and concrete applications
  • Simulation for complex systems

Areas for improvement:

  • More industrial case studies
  • Connection with control theory (admission control, regulation)
  • Queueing theory in the context of Big Data and cloud

Personal reflections:

Queueing theory was developed a century ago (Erlang for telephone networks) but remains current. The fundamental problems (sizing, optimization) are the same; only the context changes.

The limitations of models must be understood:

  • Assumptions (Poisson, exponential) are not always realistic
  • Steady state assumes the system has been stable for a long time
  • Simplified models vs complex reality

However, even when approximate, models provide valuable orders of magnitude and intuitions. "All models are wrong, but some are useful."

Modern applications:

  • Cloud computing: server sizing, auto-scaling
  • Networks: routers, buffers, QoS
  • E-commerce: inventory management, deliveries
  • Healthcare: emergency rooms, operating theaters
  • Transportation: traffic, parking

The explosion of Internet traffic and cloud computing has renewed interest in these theories. Data centers massively use queueing theory to optimize resources.

The connection with AI:

Machine Learning can predict arrivals (time-varying lambda) and dynamically adapt resources. Combining classical stochastic models with machine learning is a promising avenue.

In conclusion, this course on stochastic processes and queueing theory provides powerful tools for modeling and analyzing uncertainty, temporal dependencies, and system performance. It is an essential complement to signal processing courses (random signals) and a prerequisite for understanding many real engineering problems.

Course Documents

Stochastic Processes Lecture Notes

Complete course: Markov chains, Poisson processes, queueing theory and performance analysis.

Download

Discrete-Time Markov Chains

DTMC: transition matrices, stationary probabilities, state classification and ergodicity.

Download

Queueing Theory

M/M/1, M/M/c models, Little's formulas, waiting times, utilization rates and optimization.

Download

← Retour aux Cours 2023-2024