Issue |
RAIRO-Oper. Res.
Volume 35, Number 2, April June 2001
ROADEF'99
|
|
---|---|---|
Page(s) | 189 - 209 | |
DOI | https://doi.org/10.1051/ro:2001111 | |
Published online | 15 August 2002 |
Resource allocation in a mobile telephone network: A constructive repair algorithm
1
Département Informatique,
École des Mines de Nantes,
4 rue Alfred Kastler, La Chantrerie,
44307 Nantes Cedex 3, France;
Patrice.Boizumault@emn.fr.
2
Département Informatique,
École des Mines de Nantes,
4 rue Alfred Kastler, La Chantrerie,
44307 Nantes Cedex 3, France;
Philippe.David@emn.fr.
3
: ,
9a rue de la Porte de Buc, 78000 Versailles, France; housni.djellab@eurodecision.fr.
Received:
May
1999
To cope with its development, a French operator of mobile telephone network must periodically plan the purchase and the installation of new hardware, in such a way that a hierarchy of constraints (required and preferred) is satisfied. This paper presents the “constructive repair” method we used to solve this problem within the allowed computing time (1 min). This method repairs the planning during its construction. A sequence of repair procedures is defined: if a given repair cannot be achieved on a partial solution, a stronger repair (possibly relaxing more important constraints) is called upon. We tested our method on ten (both hand-made and real) problems. All our solutions were at least as good as thoses computed by hand by the engineer in charge with the planning.
Résumé
Afin de couvrir les besoins liés au développement de son réseau, un opérateur français de téléphonie mobile doit périodiquement planifier l'achat et l'installation de nouveaux matériels, tout en respectant un ensemble de contraintes (contraintes obligatoires ou préférences hiérarchisées). Cet article présente la méthode, baptisée “constructive repair", utilisée pour résoudre ce problème dans les délais impartis (1 min de temps de calcul). Cette méthode répare le planning durant sa construction. Une suite de procédures de réparation est définie : si une réparation donnée ne peut aboutir sur une solution partielle, une réparation plus forte (relâchant éventuellement des contraintes plus importantes) est appelée. Nous avons testé notre méthode sur dix problèmes (aussi bien réels que spécifiquement conçus “à la main" pour ces tests). Nos solutions sont toutes au moins aussi bonnes que celles imaginées par l'ingénieur responsable de la planification.
Key words: Resource allocation / repair algorithms / constrained resolution time / CSP / telecommunications.
© EDP Sciences, 2001
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.