Search

Your search keyword '"Houssin, Laurent"' showing total 98 results
Start Over Author "Houssin, Laurent"
98 results on '"Houssin, Laurent"'

8. A Branch-and-Bound Procedure for the Robust Cyclic Job Shop Problem

Author

Hamaz, Idir, Houssin, Laurent, Cafieri, Sonia, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Lee, Jon, editor, Rinaldi, Giovanni, editor, and Mahjoub, A. Ridha, editor

Published
2018
Full Text
View/download PDF

12. A Comparison of a Global Approach and a Decomposition Method for Frequency Assignment in Multibeam Satellite Systems

Author

Camino, Jean-Thomas, Artigues, Christian, Houssin, Laurent, Mourgues, Stéphane, Diniz Junqueira Barbosa, Simone, Series editor, Chen, Phoebe, Series editor, Du, Xiaoyong, Series editor, Filipe, Joaquim, Series editor, Kara, Orhun, Series editor, Liu, Ting, Series editor, Kotenko, Igor, Series editor, Sivalingam, Krishna M., Series editor, Washio, Takashi, Series editor, de Werra, Dominique, editor, Parlier, Greg H., editor, and Vitoriano, Begoña, editor

Published
2015
Full Text
View/download PDF

13. An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

Author

Carla Juvin and Emmanuel Hebrard and Laurent Houssin and Pierre Lopez, Juvin, Carla, Hebrard, Emmanuel, Houssin, Laurent, Lopez, Pierre, Carla Juvin and Emmanuel Hebrard and Laurent Houssin and Pierre Lopez, Juvin, Carla, Hebrard, Emmanuel, Houssin, Laurent, and Lopez, Pierre

Abstract

Constraint Programming has been widely, and very successfully, applied to scheduling problems. However, the focus has been on uninterruptible tasks, and preemptive scheduling problems are typically harder for existing constraint solvers. Indeed, one usually needs to represent all potential task interruptions thus introducing many variables and symmetrical or dominated choices. In this paper, building on mostly known results, we observe that a large class of preemptive disjunctive scheduling problems do not require an explicit model of task interruptions. We then introduce a new constraint programming approach for this class of problems that significantly outperforms state-of-the-art dedicated approaches in our experimental results.

Published
2023
Full Text
View/download PDF

15. Approche hybride multi-étape pour la résolution du problème de job-shop flexible robuste avec budget d'incertitude

Author

Juvin, Carla, Houssin, Laurent, Lopez, Pierre, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), Rennes School of Business, and ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018)

Subjects
programmation linéaire en nombres entiers, optimisation robuste multi-étape, Problème d'ordonnancement jop-shop flexible, budget d'incertitude, programmation par contraintes, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

National audience; Dans ce travail, nous nous intéressons à la conception de méthodes exactes pour résoudre le problème d'ordonnancement de type job-shop flexible robuste. Nous proposons pour cela une optimisation robuste en deux étapes, la première étape s’occupant de l’affectation des opérations et de leur séquencement sur les machines, la seconde déterminant la date de début des opérations. Deux modèles robustes, basés sur des formulations de programmation linéaire en nombres entiers mixtes et de programmation par contraintes, sont présentés, de même qu’un algorithme de génération de colonnes et de contraintes. Des résultats expérimentaux permettent de tirer des conclusions sur la performance des méthodes proposées.

Published
2023

16. Optimisation pour l'ordonnancement et le spatial

Author

Houssin, Laurent and Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)

Subjects
Ordonnancement cyclique, Optimisation robuste, Recherche opérationnelle, Optimisation combinatoire
Abstract

L’optimisation de processus complexes fait l’objet d’études en Recherche Opérationnelle et Optimisation Mathématique. Mes travaux en optimisation se sont concentrés sur deux types d’application : les problèmes d’ordonnancement et les problèmes issus du spatial. Parmi les problèmes d’ordonnancement, les problèmes cycliques correspondent à ceux pour lesquelles les tâches se répètent périodiquement. Ces problèmes ont été étudiés dans la littérature mais la plupart des travaux considèrent des paramètres déterministes. Pourtant, des incertitudes, comme la durée d’execution des tâches, peuvent survenir. Mes travaux sur l’ordonnancement cyclique visent à considérer ces incertitudes sous la forme d’un problème d'optimisation robuste bi-niveau. Une méthode de résolution basée sur une décomposition de Benders pour la version flexible du problème d'ordonnancement cyclique constitue une autre contribution dans ce domaine. Concernant les problématiques du spatial, les technologies modernes posent de nouveaux problèmes d’optimisation que nous tentons de résoudre tels que l’optimisation du placement de faisceau d’un satellite de télécommunication. Pour résoudre ce problème, nous proposons un encadrement paramétrable de la norme euclidienne dans le plan.

Published
2022

20. Logic-based Benders Decomposition for preemptive Flexible Job-Shop Scheduling

Author

Juvin, Carla, Houssin, Laurent, Lopez, Pierre, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018), and Lopez, Pierre

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Benders decomposition, Preemption, Flexible job-shop scheduling, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

International audience; In this paper, we address the preemptive flexible job-shop scheduling problem (pFJSSP). We propose three exact methods to solve the pFJSSP with makespan minimization objective: a Mixed Integer Linear Programming (MILP) formulation, a Constraint Programming (CP) formulation, and a Logic-Based Benders Decomposition (LBBD) algorithm.

Published
2022

23. Ordonnancement des contacts Search And Rescue dans une constellation de satellites de géopositionnement

Author

Artigues, Christian, Gallois, Léonie, Houssin, Laurent, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), INSA Lyon, ANR-18-CE10-0007,PER4MANCE,Planification Et Répartition Flexible du travail entre les OpérateuRs des chaînes d'asseMblage AéroNautiques : une approChe systémique pour gérer les risques Ergonomiques et économiques(2018), and ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019)

Subjects
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], programmation en nombres entiers, constellation de satellites, ordonnancement
Abstract

International audience; Ordonnancement des contacts Search And Rescue dans une constellation de satellites de géopositionnement

Published
2022

24. Décomposition de Benders basée sur la logique pour le problème de job-shop flexible préemptif

Author

Juvin, Carla, Houssin, Laurent, Lopez, Pierre, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut Supérieur de l'Aéronautique et de l'Espace (ISAE-SUPAERO), INSA Lyon, and Sciencesconf.org, CCSD

Subjects
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], préemption, méthodes exactes, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Job shop flexible, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], décomposition de Benders, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

International audience; On s'intéresse au problème d'ordonnancement de production du type job-shop flexible préemptif. Trois approches sont proposées pour le résoudre : la programmation linéaire en nombres entiers, la programmation par contraintes et la décomposition de Benders basée sur la logique.

Published
2022

25. A Benders decomposition for the flexible cyclic jobshop problem

Author

Quinton, Félix, Hamaz, Idir, Houssin, Laurent, ONERA / DTIS, Université de Toulouse [Toulouse], ONERA-PRES Université de Toulouse, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), and Houssin, Laurent

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Cyclic scheduling, Decomposition method, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Flexible scheduling, ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2021

35. La vie en rouge

Author

Lindingre, Houssin, Laurent, Lindingre, Lindingre, Houssin, Laurent, and Lindingre

Abstract

Lindingre aime inventer son propre argot et le dessin de Laurent Houssin, élégant et alambiqué, se prête à merveille au jeu de l'allégorie. Cette rencontre était inéluctable et nous offre une galerie d'illustrations qui ravira les amateurs de bon vin et de bons mots. Comme on le sait, ce sont souvent les mêmes ! En guise d'apéro, l'ouvrage contient une préface de Pierre Perret.

Published
2018

37. A heap of pieces model for the cyclic job shop problem

Author

Houssin, Laurent, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)

Subjects
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

International audience; In classical scheduling, a set of tasks is executed once while the determined scheduleoptimizes objective functions such as the makespan or earliness-tardiness. In contrast, cyclicscheduling means performing a set of generic tasks infinitely often while minimizing thetime between two occurrences of the same task. Cyclic scheduling has several applications,e.g. in robotic industry (see Kats and Levner [1997]), in manufacturing systems (see Pinedo[2005] and Hillion and Proth [1989]) or multiprocessor computing (see Hanen and Munier[1995b]). It has been studied from multiple perspectives, since there exist several possiblerepresentations of the problem such as graph theory, mixed integer linear programming,Petri nets or (max; +) algebra. An overview about cyclic scheduling problems and thedifferent approaches can be found in Hanen and Munier [1995a].However, a less known tool is the heaps of pieces approach. A first paper consideringthis modelling for cyclic scheduling is Gaubert and Mairesse [1999]. The authors introducea method to represent safe Petri nets as particular automata which compute the height ofheaps of pieces. This approach enables to compute efficiently the throughput of a cyclicschedule. In this paper, we use the heaps of pieces approach for solving cyclic schedulingproblems with resource constraints.

Published
2014

38. Ordonnancement cyclique : nouveaux résultats sur la théorie des tas

Author

Houssin, Laurent, Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées, Société française de recherche opérationnelle et d'aide à la décision, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), and Université de Toulouse (UT)

Subjects
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], ordonnancement cyclique, poids moyen d'un graphe
Abstract

International audience; Les problèmes de Job-Shop peuvent souvent être simplifiés en les considérant comme des problèmes cycliques. L'ordonnancement des tâches devient ainsi cyclique et son objectifest d'organiser les activités de production en répétant un cycle de base que l'on a optimisé. De nombreux paramètres entrent en jeu dans l'optimisation du cycle de base tels que lapériode du cycle choisie, l'ordre des opérations élémentaires pour réaliser un travail, la durée de ces opérations, le nombre de produits à réaliser par cycle, etc.Plusieurs approches ont été utilisées pour résoudre ce problème. Parmi elles, nouspouvons citer l'approche par réseaux de Petri et plus particulièrement par graphes d'événementstemporisés, l'approche par les graphes, l'approche par la programmation linéaireet l'approche par la théorie des tas.Concernant l'approche par la théorie des tas, le sous-problème de l'évaluation d'unesolution peut être résolu aisément avec l'aide de la théorie des tas. En effet, en traduisantle problème dans une structure mathématique adaptée, l'évaluation du taux de productiondu cycle revient au calcul d'une valeur propre d'un produit de matrices dans lequel chacunedes matrices représente une opération élémentaire. Cette propriété s'avère particulièrementintéressante dans le cas de l'évaluation successive d'un grand nombre d'ordonnancement. En outre, la théorie des tas permet une représentation très intuitive d'un ordonnancement,puisque celui-ci s'illustre comme un empilement de plusieurs briques (en fait, un " tas "de briques) dont le contour supérieur correspond aux dates de fin des dernières opérationsdes machines. Dans ce papier nous présentons les derniers résultats concerant l'application de cette théorie à l'ordonnancement cyclique. Plus particulièrement, nous montrons que le problème du nombre d' "en cours" à l'intérieur du motif peut être résolu au prix d'une extension du tas.

Published
2014

39. Contribution to (max,+)-linear systems control.‎ Applications to transportation networks.‎

Author

Houssin, Laurent and Houssin, Laurent

Subjects
(max, +) algebra, transportation networks, discrete event dynamic systems, +), [SPI.AUTO] Engineering Sciences [physics]/Automatic, commande, algèbre (max, réseaux de transport, systèmes à événements discrets, control
Abstract

The functioning of Discrete event dynamic systems subject to synchronization and delay phenomena can be described by linear models in a particular algebraic structure called (max,+) algebra. A linear system theory has been developed over dioids (such as (max,+) algebra) by analogy with the conventional one. This report is devoted to control problem of (max,+)-linear systems. Some control problems for these systems have previously been tackled. In all these works, the problematic was to compute an optimal solution in regards of the just-in-time criterion while considering control objective such as reference model or reference output. For our concern, the first contribution to the control aim at delaying as less as possible the controlled system while ensuring some given specifications. More precisely, we consider specifications which fit on system state inequalities. Then, we study a new control criterion. We are interested in controller synthesis which delay as less as possible the system while ensuring a control objective defined by constraints on system state. Transportation networks can be described by a linear representation in (max,+)-algebra. The last part of this report is devoted to their study. We propose some tools for the evaluation performance and the control of these systems. Notably, the timetables synthesis problem is formulated and solved as (max,+)-linear system control., Les systèmes à événements discrets qui mettent en jeu des phénomènes de synchronisation possèdent une description linéaire dans l'algèbre (max,+). Une théorie des systèmes linéaires dans les dioïdes, développée par analogie à la théorie conventionnelle des systèmes, a alors vu le jour. Dans ce mémoire, nous abordons des problèmes de commande des systèmes (max,+)-linéaires. Jusque-là, les commandes de systèmes linéaires dans les dioïdes ont principalement considéré le critère du juste-à-temps et des objectifs de commande comme la poursuite d'une trajectoire de référence ou la poursuite d'un transfert de référence. La première contribution à la commande réside dans la prise en compte d'un nouvel objectif pour la commande en juste-à-temps. Plus précisément, on considère des spécifications sous la forme de contraintes sur l'état du système. Ensuite, nous abordons un nouveau critère de commande. On s'intéresse à la synthèse d'un correcteur qui ralentit le moins possible le transfert du système tout en assurant un objectif de commande défini par un ensemble de contraintes sur l'état. Les réseaux de transport admettent une description linéaire dans l'algèbre (max,+). La dernière partie de ce mémoire est consacrée à leur étude. Plus précisément, on propose des outils pour l'évaluation de performances et la commande de ces systèmes. Le problème de synthèse de tables d'horaires est notamment formulé en un problème de commande de système (max,+)-linéaire.

Published
2006

41. Commande en juste-à-temps sous contraintes de systèmes (max,+)-linéaires

Author

Houssin, Laurent, Lahaye, Sébastien, Boimond, Jean-Louis, Houssin, Laurent, Laboratoire d'Ingéniérie des Systèmes Automatisés (LISA), and Centre National de la Recherche Scientifique (CNRS)-Université d'Angers (UA)

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-AU] Computer Science [cs]/Automatic Control Engineering
Abstract

National audience; Ce papier présente une commande optimale vis-à-vis du critère juste-à-temps de systèmes à événements discrets mettant en jeu des phénomènes de synchronisation. Au regard des études existantes sur le sujet, on généralise le problème en considérant de nouvelles contraintes dans la spécification de l'objectif à atteindre. Pour résoudre le problème ainsi étendu, on le formule comme un problème de recherche d'un plus grand point fixe d'une application définie sur un dioïde. On présente de plus une application à la génération des tables d'horaires des réseaux de bus urbains.

Published
2005

42. Frequency allocation in a SDMA satellite communication system with beam moving (ICC 2012)

Author

Kiatmanaroj, Kata, Artigues, Christian, Houssin, Laurent, Messine, Frédéric, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), and Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3)

Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Computer Science::Information Theory
Abstract

International audience; Spatial Division Multiple Access (SDMA) is a principle of radio resource sharing that separates communication channels in space. It relies on adaptive and dynamic beamforming technology and well-designed algorithms for resource allocation. As satellite communication systems move towards greater capacity in both the number of users and throughput, SDMA becomes one of the most promising techniques that can achieve these two goals. This paper studies static Frequency Assignment Problem (FAP) in a satellite communication system involving a satellite and a number of users located in a service area. The objective is to maximise the number of users that the system can serve while maintaining the signal to interference plus noise ratio of each user under a predefined threshold. Traditionally, interference is binary and fixed. In this paper, the interference is cumulative and variable depending on how the frequency is assigned. To solve the problem, we work on both discrete and continuous optimizations. Integer linear programming formulations and greedy algorithms are proposed for solving the discrete frequency allocation problem. The solution is further improved by beam moving algorithm which involves continuous adjustment of satellite beams and deals with non-linear change of interference.

Published
2012
Full Text
View/download PDF

43. Greedy algorithms for time-frequency allocation in a SDMA satellite communication system

Author

Kiatmanaroj, Kata, Artigues, Christian, Houssin, Laurent, Corbel, Erwan, Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées, Thales Alenia Space (TAS), THALES, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT), Thales Alenia Space [Toulouse] (TAS), and THALES [France]

Subjects
[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2012

44. Cyclic jobshop problem and (max,plus) algebra

Author

Houssin, Laurent, LAAS-MOGISA, Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)

Subjects
[INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, [SPI.AUTO]Engineering Sciences [physics]/Automatic
Abstract

International audience; In this paper, we focus on the cyclic job-shop problem. This problem consists in determining the order of a set of generic tasks on machines in order to minimize the cycle time of the sequence. We propose an exact method to solve this problem. For each solution, a linear max-plus model (possibly non causal) is obtained. To evaluate the performance of a considered schedule, we build the causal max-plus representation and compute the eigenvalue of the evolution matrix. A branch and bound procedure is presented.

Published
2011

48. Allocation de fréquences dans un système de communication satellitaire utilisant de SDMA

Author

Houssin, Laurent, Artigues, Christian, Corbel, Erwan, LAAS-MOGISA, Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Thales Alenia Space [Toulouse] (TAS), THALES [France], Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Thales Alenia Space (TAS), and THALES

Subjects
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

Allocation de fréquences dans un système de communication satellitaire utilisant de SDMA

Published
2009

50. Contributions à la commande des systèmes (max,+)-linéaires. Applications aux réseaux de transport

Author

Houssin, Laurent, Laboratoire d'Ingéniérie des Systèmes Automatisés (LISA), Centre National de la Recherche Scientifique (CNRS)-Université d'Angers (UA), Université d'Angers, and Jean-Louis Boimond

Subjects
(max, +) algebra, transportation networks, discrete event dynamic systems, +), commande, algèbre (max, réseaux de transport, systèmes à événements discrets, control, [SPI.AUTO]Engineering Sciences [physics]/Automatic
Abstract

The functioning of Discrete event dynamic systems subject to synchronization and delay phenomena can be described by linear models in a particular algebraic structure called (max,+) algebra. A linear system theory has been developed over dioids (such as (max,+) algebra) by analogy with the conventional one. This report is devoted to control problem of (max,+)-linear systems. Some control problems for these systems have previously been tackled. In all these works, the problematic was to compute an optimal solution in regards of the just-in-time criterion while considering control objective such as reference model or reference output. For our concern, the first contribution to the control aim at delaying as less as possible the controlled system while ensuring some given specifications. More precisely, we consider specifications which fit on system state inequalities. Then, we study a new control criterion. We are interested in controller synthesis which delay as less as possible the system while ensuring a control objective defined by constraints on system state. Transportation networks can be described by a linear representation in (max,+)-algebra. The last part of this report is devoted to their study. We propose some tools for the evaluation performance and the control of these systems. Notably, the timetables synthesis problem is formulated and solved as (max,+)-linear system control.; Les systèmes à événements discrets qui mettent en jeu des phénomènes de synchronisation possèdent une description linéaire dans l'algèbre (max,+). Une théorie des systèmes linéaires dans les dioïdes, développée par analogie à la théorie conventionnelle des systèmes, a alors vu le jour. Dans ce mémoire, nous abordons des problèmes de commande des systèmes (max,+)-linéaires. Jusque-là, les commandes de systèmes linéaires dans les dioïdes ont principalement considéré le critère du juste-à-temps et des objectifs de commande comme la poursuite d'une trajectoire de référence ou la poursuite d'un transfert de référence. La première contribution à la commande réside dans la prise en compte d'un nouvel objectif pour la commande en juste-à-temps. Plus précisément, on considère des spécifications sous la forme de contraintes sur l'état du système. Ensuite, nous abordons un nouveau critère de commande. On s'intéresse à la synthèse d'un correcteur qui ralentit le moins possible le transfert du système tout en assurant un objectif de commande défini par un ensemble de contraintes sur l'état. Les réseaux de transport admettent une description linéaire dans l'algèbre (max,+). La dernière partie de ce mémoire est consacrée à leur étude. Plus précisément, on propose des outils pour l'évaluation de performances et la commande de ces systèmes. Le problème de synthèse de tables d'horaires est notamment formulé en un problème de commande de système (max,+)-linéaire.

Published
2006

Catalog

Books, media, physical & digital resources
See catalog results