Re ue In e na ionale de la Reche che Scien i ique
(Re ue-IRS)
ISSN: 2958-8413
Vol. 3, No. 6, Décemb e 2025
This is an open access a icle unde he CC BY-NC-ND license.
h p://www. e ue-i s.com
7028
P oblème d’a ec a ion de âches e équilib age de cha ge dans un en i onnemen
mul i- ile d’a en e
NGINDU MULUMBA Pascal1, NTUMBA BADIBANGA Simon2, KASENGEDI MUTOMBE Pie e3,
KANKU MUBENGA BANTU Eddy Michel4, KALONJI SHIKAYI Syl ain5.
1. Che de T a aux à Ins i u supé ieu de Techniques Médicales de Kananga (ISTM)
2. P o esseu O dinai e à Uni e si é de Kinshasa (UNIKIN)
3. P o esseu à Ins i u Supé ieu des Techniques Appliquées (ISTA)
4. Che de T a aux à l’Ins i u Supé ieu de dé eloppemen Ru al (ISDR-Tshibashi)
5. Assis an à l’Académie mili ai e de Kananga (ACAMIL)
En République Démoc a ique du Congo (RDC).
Abs ac : The issue o ask alloca ion and load managemen in a mul i-queue amewo k aims o op imize he
dis ibu ion o asks among mul iple se e s o compu ing esou ces, each ha ing i s own queue. The main
objec i e is o educe wai ing imes and esponse imes, o a oid o e loading ce ain se e s o p e en
conges ion and imp o e he o e all use o esou ces, while conside ing he mo emen o nodes and
communica ion cons ain s. This p oblem is pa icula ly ele an in dis ibu ed con ex s such as cloud
compu ing, ad hoc ne wo ks, o pa allel compu ing sys ems. I equi es he de elopmen o cle e decision-
making mechanisms ha can ake in o accoun he s a e o he queues, he capaci ies o he esou ces, and he
speci ici ies o he asks. The sugges ed op ions o en ely on queue managemen models, op imiza ion
algo i hms, heu is ics, o lea ning-based me hods, wi h he aim o ensu ing supe io se ice quali y, imp o ed
e iciency, and be e sys em adap abili y. This issue is o c ucial impo ance o he e iciency and quali y o
se ices p o ided by con empo a y dis ibu ed sys ems. Dynamic load balancing echniques, such as he
imp o ed Round-Robin algo i hm, Leas -Loaded Fi s , o machine lea ning-based app oaches, ha e all
demons a ed hei limi a ions ega ding ask alloca ion and he managemen o mul iple queues. The
de elopmen o a new me hod o ask dis ibu ion and load balancing, as well as he inco po a ion o hese
h ee pa adigms (Cloud compu ing, ad-hoc ne wo k, web se ice) in o an unp eceden ed a chi ec u al s uc u e,
ep esen s a signi ican con ibu ion o his challenge.
Keywo ds: Task alloca ion, Load balancing, Mul i-queueing, Op imiza ion, Cloud compu ing.
Résumé: La ques ion de l'a ibu ion des âches e de la ges ion de la cha ge dans un cad e mul i- ile d'a en e
ise à op imise la dis ibu ion des âches en e plusieu s se eu s ou essou ces in o ma iques, chacun ayan sa
p op e ile d'a en e. L'objec i p incipal es de édui e les délais d'a en e e les emps de éponse, d'é i e la
su cha ge de ce ains se eu s pou p é eni l'engo gemen e amélio e l'u ilisa ion globale des essou ces, ou
en considé an le mou emen des nœuds e les con ain es en ma iè e de communica ion. Ce p oblème es
pa iculiè emen pe inen dans les con ex es dis ibués els que le cloud compu ing, les éseaux ad hoc, ou
enco e les sys èmes in o ma iques pa allèles. Il equie l'élabo a ion de disposi i s décisionnels as ucieux qui
peu en p end e en comp e l'é a des iles d'a en e, les capaci és des essou ces e les spéci ici és des missions.
Les op ions suggé ées eposen sou en su des modèles de ges ion des iles d'a en e, des algo i hmes
d'op imisa ion, des heu is iques ou des mé hodes ondées su l'app en issage, dans le bu de ga an i un se ice
de quali é supé ieu e, une e icaci é amélio ée e une meilleu e capaci é d'adap a ion du sys ème. Ce e
p obléma ique es d'une impo ance c uciale pou l'e icaci é e la quali é des p es a ions des sys èmes dis ibués
con empo ains. Des echniques d'équilib age de cha ge dynamique, comme l'algo i hme Round-Robin
amélio é, le Leas -Loaded Fi s ou des app oches basées su l'app en issage au oma ique, ou es ces echniques
Re ue In e na ionale de la Reche che Scien i ique (Re ue-IRS) - ISSN : 2958-8413
h p://www. e ue-i s.com
7029
on démon é leu s limi es en ce qui conce ne l'a ibu ion de âches e la ges ion des iles d'a en e mul iples.
Le dé eloppemen d'une nou elle mé hode de épa i ion des âches e d'équilib age de la cha ge, ainsi que
l'inco po a ion de ces ois pa adigmes (Cloud compu ing, éseau ad-hoc, se ice web) dans une s uc u e
a chi ec u ale inédi e cons i uen une con ibu ion signi ica i e à ce challenge.
Mo s-clés : A ec a ion de âches, Équilib age de cha ge, Mul i- ile d’a en e, Op imisa ion, Cloud compu ing.
Digi al Objec Iden i ie (DOI): h ps://doi.o g/10.5281/zenodo.18049291
1. In oduc ion
1.1. Con ex e de la eche che e p obléma ique
Dans des con ex es in o ma iques ac uels comme le cloud compu ing, les éseaux mobiles ad hoc e
les cen es de ai emen décen alisés, l'adminis a ion e icace des âches ep ésen e un dé i s a égique c ucial.
L'un des enjeux les plus impo an s es la ques ion de l'a ibu ion des âches liée à l'équilib age de cha ge dans un
sys ème a ec plusieu s iles d'a en e. Ces disposi i s se composen de di e ses iles d'a en e, chaque ile é an liée
à un ou plusieu s se eu s ou uni és de ai emen . L’e icaci é globale es o emen in luencée pa la açon don
les âches son dis ibuées en e ces iles.
Dans un con ex e comme celui-ci, une mau aise dis ibu ion des âches peu p o oque l'engo gemen de
ce aines iles d'a en e, pendan que d'au es son à peine exploi ées, ce qui ampli ie le délai moyen de éponse,
diminue l'e icience des essou ces e me en pé il la quali é du se ice (QoS). Pou épond e à ce dé i, on u ilise
des mé hodes d'a ibu ion dynamique e des algo i hmes de épa i ion de cha ge.
L'objec i es de dé eloppe un algo i hme d’a ec a ion e équilib age de cha ge e pa allélise de âches
de mul iple ile d’a en e su n se eu s, pou édui e le emps d'a en e moyen, d'op imise le aux d'exploi a ion
des essou ces e de ga an i une dis ibu ion équilib ée du a ail.
1.2. P obléma ique e hypo hèse
Les app oches suggé ées dans les éc i s di è en en onc ion des p ésupposés : cen alisa ion ou
décen alisa ion, ca ac è e s a ique ou dynamique du sys ème, uni o mi é ou di e si é des se eu s, e c. Les
mé hodes adi ionnelles comme Round-Robin, Leas -Loaded Fi s ou celles basées su la héo ie des iles d'a en e
son équemmen associées à des echniques con empo aines elles que l'app en issage au oma ique, la
p og amma ion linéai e ou enco e les app oches heu is iques e mé aheu is iques on mon e leu limi en . E à ce
jou , l’in ég a ion de plusieu s echniques pou de mé hodes hyb ides sa eu s indispensable.
Pa conséquen , l'examen de la ques ion de l'a ibu ion des âches e de la épa i ion de la cha ge dans
un cad e mul i- ile d'a en e ep ésen e un champ d'é udes dynamique e c ucial pou assu e la capaci é
d'é olu ion, la iabili é e l'e icaci é des in as uc u es dis ibuées con empo aines.
La ques ion ondamen ale es celle de sa oi : Commen gé e les con li s des equê es dans ce sys ème dis ibué
e main eni le sys ème en équilib e ?
A ce e p obléma ique, u le limi e cons a é dans l’u ilisa ion des mé hodes adi ionnelles de ges ion de
con li s e épa i ion de cha ge, nous suggé ons l’hypo hèse selon laquelle la concep ion d’un algo i hme u ilisan
une nou elle app oche d’a ec a ion e o donnancemen de âches ( equê es) su plusieu s se eu s en pa allèle
pou ai ê e une solu ion pou é i e la conges ion, les explosions e la su cha ge pou main eni le sys ème en
équilib e.
2. Sys ème mul i- ile d’a en e
Aujou d'hui, les iles d'a en e se p ésen en sous di e ses o mes e dans de nomb eux domaines, de enan
ainsi un phénomène cou an que l'on encon e éguliè emen . Voici quelques illus a ions pa mi une mul i ude
d'au es : l'in o ma ique en nuage, les éseaux mobiles ad hoc, les cen es de ai emen décen alisés,
l'engo gemen à un poin de se ice, la conges ion du a ic ou ie ou d'un éseau de élécommunica ion, la ges ion
d'un in en ai e de p oduc ion, l'en e ien d'un ma é iel in o ma ique, le déplacemen de popula ions, les p é isions
mé éo ologiques, e ainsi de sui e. Il exis e une mul i ude de modèles s ochas iques, basés su des hypo hèses
ajus ées au con ex e spéci ique. Nous allons examine le modèle M/M/c, considé é comme une spéci ici é du
p ocessus s ochas ique, e qui s'adap e au sys ème que nous souhai ons ep ésen e dans une ile d'a en e mul iple.
2.1. Le Modèle M/M/c
E lang p opose le modèle M/M/c qui es un modèle de ile d'a en e qui déc i un sys ème a ec c se eu s
(ou canaux) où les appels a i en selon un p ocessus de Poisson (a i ées aléa oi es a ec un aux cons an ) e la
Re ue In e na ionale de la Reche che Scien i ique (Re ue-IRS) - ISSN : 2958-8413
h p://www. e ue-i s.com
7030
du ée des appels sui une dis ibu ion exponen ielle ( emps de se ice aléa oi e mais a ec un aux cons an ). C'es
un modèle ès cou an dans les cen es d'appel e d'au es sys èmes de se ice en ile d'a en e.
Le modèle M/M/1 e M/M/c on la même logique de base su les mêmes hypo hèses ondamen ales :
✓ M (p emie M) : A i ées selon un p ocessus de Poisson (aléa oi es) a ec un aux λ,
✓ M (deuxième M) : Du ée de se ice exponen ielle, a ec un aux μ /1 ou /c : nomb e de se eu s (1 ou c)
Donc : M/M/1 = 1 seul se eu e M/M/c = c se eu s en pa allèle
On choisi M/M/c à la place de M/M/1 quand le olume de âches augmen e, on eu édui e les emps
d’a en e e que le sys ème dispose de plusieu s se eu s ; c’es le con ex e de no e é ude ca nous analysons un
sys ème à mul i ile d’a en e. Le modèle M/M/1 es un cas pa iculie de M/M/c a ec c = 1.
2.2. Ca ac é is iques
Voici quelque ca ac é is ique du M/M/C
1. Modèle éalis e pou plusieu s se eu s
• Le modèle M/M/c es adap é aux si ua ions a ec plusieu s se eu s.
• C’es plus éalis e que le M/M/1 quand plusieu s agen s ai en les demandes en même emps
(guiche s, caisses, se eu s in o ma iques, cen e éléphonique…).
2. Hypo hèses simples e cou an es
• A i ées aléa oi es (p ocessus de Poisson) → modélise bien les lux de clien s non p é isibles.
• Du ées de se ice exponen ielles (aléa oi es aussi) → alable pou beaucoup de se ices
apides.
• Les se eu s son iden iques e indépendan s → simpli ie l’analyse ma héma ique.( Donald, G.
John, Sho le,F. James, M. Ca l M, H. 2018).
3. Équilib e en e p écision e simplici é
C’es un bon comp omis en e un modèle simple (M/M/1) e des modèles plus complexes (M/G/c, G/G/c).
4. Mesu es de pe o mances accessibles. A ec M/M/c, on peu calcule : Temps moyen d’a en e,
Nomb e moyen de clien s, Taux d’occupa ion des se eu s (ρ), P obabili é qu’un clien
a ende. Ces ésul a s aiden à dimensionne un se ice (combien de se eu s au -il pou
ga an i un bon se ice ?)
5. U ilisé dans de nomb eux domaines
2.3. Élémen s d'un sys ème à iles mul iples
Le sys ème d'a en e à plusieu s iles comp end les élémen s sui an s.
➢ Les clien s : en i és à considé e
➢ Les se eu s : essou ces de p es a ion de se ice.
➢ Les queues : zones d'a en e
➢ F equence d'a i ée (λ) e équence de se ice (μ)
➢ Poli ique de ges ion des iles d'a en e (FIFO ou FCFS, p io i é, e c.)
2.4. Di e s scéna ios.
2.4.1. La p obabili é d'occupa ion Po (sys ème inoccupé) :
Dans le modèle M/M/c, la o mule ci-dessous es u ilisée pou calcule la p obabili é Po que ous les se eu s
soien disponibles (aucune âche en ai emen ) :
𝑃𝑜=(∑
𝐶−1
𝑛=0 (𝐸𝑛)
𝑛! ) / (∑ (𝐸𝑛)
𝑛!
𝑐
𝑛=0 )
Où :
Le numé a eu illus e l'addi ion des élémen s de la sé ie de n = 0 jusqu'à n = c−1.
Le dénomina eu co espond à l'addi ion de ous les e mes de la sé ie, allan de n = 0 jusqu'à n = c, cela inclu
égalemen le e me où n = c.
2.4.2. P obabili é qu'une âche soi en a en e :
La p obabili é Pa en e qu'une âche soi en a en e (c'es -à-di e que ous les se eu s son occupés e que la
âche doi pa ien e ) dans un sys ème M/M/c es exp imée de la maniè e sui an e :
Re ue In e na ionale de la Reche che Scien i ique (Re ue-IRS) - ISSN : 2958-8413
h p://www. e ue-i s.com
7031
Pa en e =(𝐸𝑐)
𝑛! 𝑥 (1)
(1−ρ)
∑ (𝐸𝑛)
𝑛!
𝐶
𝑛=0
Où : ρ = 𝜆
𝑐𝜇 es le aux de a ic pa se eu (la cha ge pa se eu ).
E es la cha ge o ale du sys ème, E= λ
𝜇′=, comme men ionné p écédemmen .
2.4.3. P obabili é qu'une âche soi eje ée (c'es -à-di e, que ous les se eu s soien occupés e qu'il n'y ai
plus de places disponibles) :
La p obabili é qu'une âche soi eje ée, c'es -à-di e lo sque ous les se eu s son occupés e qu'une âche
en an es eje ée, peu ê e app oximée pa P eje , qui es simplemen la p obabili é que le sys ème soi à pleine
capaci é (c'es -à-di e que c se eu s son occupés).
P eje =(𝐸𝑐)
𝑛!
∑ 𝐸𝑛
𝑛!
𝐶
𝑛=0
2.5. Récapi ula i des o mules :
1. P obabili é que le sys ème soi ide P0 :
P0= ∑ (𝐸𝑛)
𝑛!
𝐶−1
𝑛=0
∑ (𝐸𝑛)
𝑛!
𝐶
𝑛=0
2. P obabili é qu'une âche soi mis en a en e Pa en e :
Pa en e =(𝐸𝑐)
𝑐! 𝑥 (1)
(1−ρ)
∑ 𝐸𝑛
𝑛!
𝐶
𝑛=0
3. P obabili é de eje (sys ème sa u é) P eje :
P eje =(𝐸𝑐)
𝑛!
∑ 𝐸𝑛
𝑛!
𝐶
𝑛=0
Le modèle M/M/c es u ilisé pou ep ésen e un sys ème d'a en e compo an plusieu s se eu s.
L'es ima ion des chances que les âches soien e usées, en a en e ou que le sys ème soi ide se ai g âce aux
équa ions p écédemmen ci ées. Ce modèle es pa iculiè emen pe inen pou é alue les pe o mances d'un
sys ème disposan de plusieu s canaux de se ice.
3. P oblème d’a ec a ion e équilib age de cha ge
L’a ec a ion e l’équilib age de cha ge isen ainsi à amélio e les pe o mances globales d’un
sys ème, à édui e les emps de éponse, à op imise l’u ilisa ion des essou ces disponibles e à ga an i une
meilleu e olé ance aux pannes. Ces echniques son pa iculiè emen c uciales dans les en i onnemen s dis ibués,
les cen es de données, les sys èmes de cloud compu ing e les a chi ec u es o ien ées se ices (Nadje , K., Louiza,
B. & Djamil 2023).
3.1. Objec i s de l'a ec a ion de âches
L'objec i p incipal de ce p oblème es d'op imise la épa i ion des essou ces. Cela peu inclu e :
➢ Minimise les coû s ;
➢ Maximise l'e icaci é ;
Respec e les con ain es : elles que la capaci é de Modélisa ion du p oblème d'a ec a ion de âches
3.2. Types de p oblèmes d'a ec a ion
▪ P oblème d'a ibu ion ypique :
▪ P oblème d'a ibu ion a ec des coû s a iables : chaque essou ce dispose d'un coû dis inc pou
accompli une âche spéci ique,
▪ P oblème a ec es ic ions : une mission peu ê e con iée à un ou ie , mais sous ce aines
condi ions de coû s ou de capaci és.
Hypo hèses sous-jacen es
▪ Le olume de âches e de essou ces,
▪ Les essou ces on la capaci é de gé e les âches e ec uées (il n'y a pas de dépendances
complexes en e elles),
▪ Les âches son au onomes e peu en ê e exécu ées en pa allèle.
Re ue In e na ionale de la Reche che Scien i ique (Re ue-IRS) - ISSN : 2958-8413
h p://www. e ue-i s.com
7032
Plusieu s app oches exis en pou ai e le p oblème de l'a ibu ion de âches su un se eu :
▪ A ec a ion classique (op imisa ion d'un c i è e unique) ;
▪ A ec a ion a ec con ain es ( épa i ion sous con ain es spéci iques) ;
▪ A ec a ion dynamique (en emps éel, ou selon la cha ge du sys ème) ;
▪ A ec a ion à plusieu s c i è es (mul i-objec i s) ;
▪ A ec a ion pa poli ique de p io i é (a ec a ion a ec p io i és) ;
▪ A ec a ion de ype "équilib age de cha ge.
3.3. Mé hodes de ésolu ion du p oblème d'a ec a ion de âches (B ahim Meb ek, 2021).
3.3.1. App oche b u e- o ce (exhaus i e)
L'app oche b u e- o ce consis e à es e ou es les pe mu a ions possibles d'a ec a ion en e les âches e
les essou ces, e à choisi celle qui minimise la onc ion objec i e. Ce e mé hode es ex êmemen coû euse en
e mes de emps de calcul, pa iculiè emen lo sque le nomb e de âches e de essou ces es éle é, ca elle nécessi e
de es e même n solu ions possibles :
3.3.2. Mé hodes exac es
1. Algo i hme de Kuhn-Munk es (Hong ois) : Ce algo i hme es u ilisé pou ésoud e le p oblème
d'a ec a ion dans les cas de O(n3) Su 3 pou un p oblème de n âches e essou ces. Il es basé su un
p ocessus de éduc ion de ma ice de cou ou de gains.
2. P og ammes linéai es : Fo mula ion du p oblème comme un p og amme linéai e (Y es Tabou ie , 1972).
3.3.3. Mé hodes heu is iques e app oxima i es
1. Algo i hmes glou ons : Ces algo i hmes p ennen des décisions locales basées su des c i è es immédia s
2. Algo i hmes géné iques : Ce ype d'algo i hme de eche che é olu ionnai e explo e l'espace des solu ions
en géné an des popula ions de solu ions e en exécu an des mécanismes de sélec ion,
c oisemen e mu a ion.
3. Algo i hmes de eche che locale : Des mé hodes comme la eche che abou ou le ecui simulé pe me en
d'amélio e une ainsi la solu ion en ajus an localemen les a ec a ions. (I ène Cha on &
Oli ie Hud y, 2019).
3.3.4. Mé hodes d'op imisa ion combina oi e
Pou les g ands p oblèmes, les app oches d'op imisa ion combina oi e comme les mé hodes de
b anchemen e liées ou les algo i hmes de dynamique de p og amma ion peu en ê e u ilisés pou ou e des
solu ions op imales.
3.3.5. App oches pa in elligence a i icielle
1. App en issage pa en o cemen : U ilisa ion d'un agen in elligen pou app end e à ésoud e le p oblème
d'a ec a ion au u e à mesu e de ses in e ac ions a ec l'en i onnemen .
2. Op imisa ion pa essais pa iculai es (PSO) : U ilisa ion de g oupes de "pa icules" qui explo en l'espace
de solu ion e ajus en leu posi ion pou ou e de solu ion.
3.3.6. App oche hyb ide
Ce e app oche pe me de i e pa i des o ces de plusieu s s a égies de plani ica ion e a ec a ion ou
en compensan leu s aiblesses.
À a e s une analyse c i ique des mé hodes classiques, no ammen l’algo i hme hong ois e les
echniques d’o donnancemen s a iques, nous a ons mis en é idence leu s limi es ace aux exigences des sys èmes
mode nes, ca ac é isés pa leu complexi é, leu dynamique e leu hé é ogénéi é.
4. Nou el mé hode d’a ec a ion e équilib age de âche
Face à ce aines con ain es des mé hodes adi ionnelles e aux exigences changean es des sys èmes
con empo ains, les algo i hmes els que hong ois ou les iles d'a en e ondées su le ound- obin ne iennen pas
sys éma iquemen comp e de la dynamique du sys ème (u ilisa ion du p ocesseu , mémoi e, éseau, e c.).
Ils son e icaces en héo ie, mais manquen de lexibili é dans des en i onnemen s a iés ou en changemen apide.
Re ue In e na ionale de la Reche che Scien i ique (Re ue-IRS) - ISSN : 2958-8413
h p://www. e ue-i s.com
7033
Voici les mo i s p incipaux de l'adop ion de ce e nou elle mé hode :
Nécessi é d'une meilleu e épa i ion de la cha ge (équilib age de cha ge) : Dans un con ex e mul i-se eu s, une
a ec a ion inco ec e peu en aîne :
✓ Une su cha ge de ce ains se eu s,
✓ Une exploi a ion insu isan e d'au es se eu s,
✓ Un déclin géné al de la pe o mance.
Un bon équilib e de cha ge op imise :
✓ La la ence,
✓ Les délais de éponse,
✓ L'espé ance de ie des essou ces ( éduc ion de la su chau e ou de l'usu e)
1. Scalabili é e complexi é c oissan e
A ec la mon ée en puissance de l'in o ma ique en nuage, de l'in o ma ique pé iphé ique e des cen es de données
à g ande échelle, il y a une explosion du nomb e de se eu s e de âches. Les app oches classiques ne s'adap en
pas aisémen à l'échelle, d'où la nécessi é de solu ions plus pe o man es e é olu i es.
2. Adap a ion à la di e si é
Les se eu s peu en p ésen e les ca ac é is iques sui an es :
• Des spéci ica ions a iées (Se eu , CPU, RAM, GPU, e c.),
• Des p io i és dis inc es de ai emen ,
• Des poli iques de sécu i é ou des égions géog aphiques spéci iques.
Les p océdu es con en ionnelles p ésumen équemmen que ous les se eu s son iden iques (une
hypo hèse peu éalis e). Ces con ain es hé é ogènes peu en ê e inco po ées dans une nou elle echnique.
4.1. En i onnemen s en emps éel e de na u e dynamique
Les missions peu en se p ésen e de maniè e cons an e, possédan di e ses ca ac é is iques (du ée,
p io i é, dépendances...).
Nous a ons besoin d'algo i hmes :
▪ Rapides (capaci é de p end e des décisions apidemen ),
▪ Résis an s à des modi ica ions ina endues (pannes, pics de équen a ion…),
▪ Mieux enco e, pa ois au onomes g âce à l'app en issage machine.
4.2. Op imisa ion à plusieu s objec i s
Dans les sys èmes con empo ains, il ne su i pas simplemen de édui e le emps de ai emen , mais
égalemen de :
▪ Diminuons la consomma ion d'éne gie,
▪ Rédui e les ais de mig a ion ou de communica ion,
▪ Respec e les exigences en ma iè e de sécu i é ou de p io i é.
Les echniques adi ionnelles on équemmen un seul objec i .
4.3. Modélisa ion de l’a ec a ion e équilib age de âches
Ce e nou elle mé hode p ésuppose que : Nous a ons à no e disposi ion un ce ain nomb e de se eu s
de ai emen , cha gés d'exécu e une onc ion d'a ibu ion su di e ses iles d'a en e. Il su i d'a ibue à chaque
appa eil une âche à accompli en onc ion de sa capaci é de ai emen .
4.3.1. Modèle de dis ibu ion con enu :
Quelle es le nomb e de âches ni à a ec e à chaque p ocesseu pou que le ai emen se e mine au
même momen ?
a. Desc ip ion de a iables
✓ ni = nomb e des âches à con ie aux machine de ca égo ie i ;
✓ Ni = nomb e de machines de la ca égo ie i ;
✓ N = nomb e o al de âches ;
✓ i = i esse des machines de ca égo ie i ;
✓ n = nomb e des ca égo ies de machines.
On che che le nomb e ni de aches à con ie à chaque machine de ca égo ie i ;
On doi alo s sa is ai e :
Re ue In e na ionale de la Reche che Scien i ique (Re ue-IRS) - ISSN : 2958-8413
h p://www. e ue-i s.com
7034
ni*Ni + ni+1*Ni+1 = N
ni = i . 𝑁
i*Ni+ i+1 *Ni+1 … =
Ces ela ion se géné alisen acilemen à
Chaque machine de la ca égo ie i, exécu e a chacune le nomb e de âche ni
Ainsi ou es les machines e mine on leu s âches en même emps si on leu con ie à chacune ce
nomb e ni de âche. Comme ces nomb es son ac ionnai es ce ains des machines de la ca égo ie i ece on plus
de âches à éali és, que les au es e cela selon leu ca égo ie.
On oi que ce modèle donne une app oxima ion du nomb e de calculs à con ie à chaque p ocesseu ,
mais ne donne pas le nomb e op imal.
4.3.2. Modèle de dis ibu ion disc e :
Pa an de la dis ibu ion con enu, le nomb e de âche es a ec e en onc ion de la i esse du se eu de
ca égo ie i, cela ai que ce aine machine eçoi en plus de âche que les au es. La nou elle idée es de con ie
une âche à un p ocesseu de ca égo ie i en onc ion de sa i esse, comme l’illus e la igu e ci-ap ès :
Figu e 1 : Modèle de dis ibu ion disc e
L’algo i hme se a donc exécu e sous ces é apes :
1. Le p ocesseu doi en ê e classés pa o d e déc oissan de apidi é ( i esse) ;
2. Répa i le âches une pa une :
1. En commençan pa la gauche
2. En se décalen d’une case e s la d oi si ni / i ≥ (ni+1 +1)/ i+1
3. On e ien à la p emiè e case si la condi ion ci-hau n’es pas é i iée ou si on a i e ou à d oi e.
5. Algo i hme d’a ec a ion con enu e équilib age de aches dans un sys ème dis ibué.
Figu e 2 : algo i hme d’a ec a ion e équilib age de cha ge (no e con ibu ion)
Débu de l’algo i hme
Ec i e "En e le nomb e d'élémen s n :"
Li e n
Dimensionne [n], N_i [n], n_i [n]
Ec i e "En e la aleu de N (cons an e) :"
Li e N
somme ← 0
i ← 1
TANTQUE i ≤ n
Ec i e "En e [",i, "] :"
Li e [i]
Ec i e "En e N_ i[",i, "] :"
Li e N_i[i]
i ← i + 1
FINTANTQUE
i ← 1
TANTQUE i ≤ n
somme ← somme + [i] * N_i[i]
i= 1 + 1
FINTANTQUE
i ← 1
TANTQUE i ≤ n
n_i [i] = ( [i] * N) / somme
i = 1 + 1
FINTANTQUE
Fin de l’algo i hme
ni = 𝒗𝒊 .𝑵
∑𝒗𝒊 .𝑵𝒊
𝒏
𝒊=𝟏
Re ue In e na ionale de la Reche che Scien i ique (Re ue-IRS) - ISSN : 2958-8413
h p://www. e ue-i s.com
7035
Ce algo i hme pe me de calcule e dé e mine le nomb e de âche à con ie à chaque se eu placé en
pa allèle ou en équilib an e op imisan la ges ion des capaci és de ai emen des se eu s disponibles. En
u ilisan une app oche basée su la ges ion de mul iple ile e l'op imisa ion dynamique, il es possible de minimise
e icacemen le emps d'a en e o al des âches dans un en i onnemen de ai emen pa allèle, édui e la su cha ge
e é i e de explosion de sys ème.
5.1. Complexi és de l’Algo i hme
1. Complexi é empo elle
➢ É ape 1 (somme des i esses) : O(n)
➢ É ape 2 (calcul des âches) : O(n)
Il s’agi de deux boucles linéai es indépendan es, donc la complexi é globale es : O(n)
2. Complexi é spa iale
Le ableau âches [1..n] nécessi e un espace p opo ionnel au nomb e de se eu s : O(n).
3. Complexi é o ale es :
➢ Complexi é empo elle : O(n) — linéai e a ec le nomb e de se eu s.
➢ Complexi é spa iale : O(n) — on s ocke une âche pa se eu .
C’es un algo i hme ès e icace, adap é à la épa i ion apide même su un g and nomb e de se eu s
5. Applica ion en py hon
Figu e 3 : algo i hme de épa i ion de cha ge en Py hon
Re ue In e na ionale de la Reche che Scien i ique (Re ue-IRS) - ISSN : 2958-8413
h p://www. e ue-i s.com
7036
5.1. Tes de l’algo i hme a ec les aies données
Figu e 4 : Tes de l’algo i hme e ésul a .
Nous a ons codé ce e algo i hme a ec py hon, e aisan le jeu d’essai a ec les données éelle p isen au
hasa d pou oi son exécu ion ainsi que les ésul a s. A pa i de ce ésul a , les a ec a ions s’e ec uen selon le
modèle con enu ou disc e ci-hau , selon chaque ca égo ie.
Conclusion
L'a ibu ion e icace des âches e l'équilib age de la cha ge dans un cad e de iles d'a en e mul iples
cons i uen oujou s un dé i majeu pou les sys èmes in o ma iques con empo ains, su ou dans les si ua ions de
cloud compu ing, de éseaux ad hoc ou de se ices en emps éel. La mé hode inno an e suggé ée dans ce
documen se déma que pa sa lexibili é à s'ajus e en emps éel aux changemen s de cha ge, à la di e si é des
se eu s e aux a ia ions des equê es des u ilisa eu s.
Ce e mé hode, qui usionne des echniques basées su la héo ie des iles d'a en e a ec des
algo i hmes sophis iqués (comme l'app en issage machine, l'op imisa ion heu is ique ou la p ise de décision
décen alisée), acili e une dis ibu ion plus jus e des âches, un abaissemen no able du emps d'a en e moyen e
une exploi a ion plus homogène des essou ces à disposi ion. Elle dépasse les echniques adi ionnelles en
considé an la condi ion géné ale du sys ème e en p é oyan l'élémen agile qui en a e le lux e diminue la
pe o mance du sys ème.
Pa conséquen , ce e echnique inno an e ep ésen e un p og ès majeu dans la ges ion des soucis de
conges ion des se eu s e de dé é io a ion de l'e icaci é. Elle pa e aussi la oie pou des é olu ions u u es en
inco po an des mécanismes de p é ision, d'app en issage au onome ou d'au onomie dans des con ex es
dynamiques els que les éseaux mobiles, les in as uc u es cloud hyb ides ou les sys èmes c i iques en emps éel.
REFERENCES
[1]. BARDET, S., e Blanc, L., Les Se ices Web, Ed. Ey olle, Pa is, 2003.
[2]. BAYNAT, B., Théo ie de la ile d’a en e ; Ed. Ey olles, Pa is, 1970,
[3]. B ahim Meb ek. (2021). Modèles d’a ec a ion a ec capaci és de essou ces, Uni e si é d’Annaba, 27.
[4]. Coo donna eu s di e s : Théo ie des iles d’a en e 2, ISTE Edi ions, Pa is, 2021.
[5]. Donald, G. John, Sho le,F. James, M. Ca l M, H. (2018). Fundamen als o Queueing Theo y (5ᵉ édi ion). Éd.
John Wiley & Sons, USA. 90-93.
[6]. Ha chol-Bal e , M. (2013). Pe o mance Modeling and Design o Compu e Sys ems: Queueing Theo y in
Ac ion. Camb idge Uni e si y P ess.
[7]. Cha on, I. & Hud y, O. (2019). In oduc ion à l'op imisa ion con inue e disc è e, Édi ion La oisie , Cachan,
339-374.
[8]. Nadje , K., Louiza, B. & Djamil. Équilib age de cha ge pou l’amélio a ion des pe o mances : dans les
éseaux de cap eu s sans il, Édi ions Uni e si ai es, B uxelles, 2023.
[9]. Ndungu, M. N. Sys ème de ges ion des iles d’a en e i uelles, Edi ions No e Sa oi , Pa is, 2023
[10]. Philippe, R. (2000). Réseaux e iles d’a en e : mé hodes p obabilis es, Sp inge , 2e éd., Pa is, 101-104.
[11]. Philippe, R. (2003). Réseaux s ochas iques e iles d’a en e (édi ion ançaise). Sp inge , Be lin/Heidelbe g.
[12]. STALLINGS, W. « Queuing Analysis (A P ac ical Guide o Compu e Scien is s) », 2000.
[13]. Toky, B. R. & Falimanana, R. Des iles d’a en e au élé a ic, ISTE Edi ions, Pa is 2023
[14]. Y es Tabou ie , (1972), Un algo i hme pou le p oblème d’a ec a ion, Reche che Opé a ionnelle, Vol. 6,
No. V3 pp. 3-15.
[15]. Oli ei a, A. L. (2025). É alua ion des s a égies d’équilib age de cha ge : s a égies
maî e-escla e pou les clus e s e les g illes in o ma iques, Édi ions No e Sa oi . Pa is.
