Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Université du Québec à Chicoutimi

$20,000.00

Ordonancement d'ateliers : algorithmes et complexité

FY 2014-15

Summary
La théorie de l?ordonnancement s?intéresse aux problèmes d?allocation de ressources dans le temps pour réaliser un ensemble de tâches. Le nombre de ressources étant limité, la décision d?affecter une tâche à une ressource, à un instant donné, est cruciale pour atteindre le ou les objectifs fixés au départ et /ou satisfaire les contraintes liés au problème étudié. Il est utile de mentionner que les ressources et les tâches peuvent avoir plusieurs interprétations dépendamment du contexte. Ainsi, le terme ressource peut signifier argent, processeurs, machines, énergie, matériel, etc. L?interprétation des tâches, quant à elle, peut aller des produits manufacturiers jusqu?aux processus dans les systèmes informatiques, en passant par des quarts de travail. Dans ces conditions, il est facile de constater que les problèmes d?ordonnancement sont associés ou surviennent dans la plupart des problèmes réels. Bien entendu, chaque application peut posséder ses propres spécificités dont il faut tenir compte lors de la résolution. Le programme de recherche proposé ici s?intéresse aux effets induits par la prise en compte de certaines paramètres pratiques, négligés ou non suffisamment pris en considération jusque-là dans la littérature, sur les modèles de base d?ordonnancement d?atelier, afin de les rendre plus proches de la réalité. Le premier paramètre considéré est celui des temps de latence pour exprimer les temps induits par les déplacements des tâches à travers les ressources. Le second paramètre est celui lié à l?existence de relations de précédence entre les tâches (dans certains cas, une tâche ne peut commencer son exécution qu?à la fin d?autres tâches ; ces dépendances définissent un graphe de précédence). Le troisième paramètre concerne la présence d'opérateurs qui, dans certaines situations, sont nécessaires au fonctionnement des ressources pour réaliser une solution d?ordonnancement. Et, enfin, le quatrième paramètre considéré concerne l?utilité de dupliquer des machines dans le but d?alléger les éventuels goulots d?étranglements dus à certaines ressources. Le point commun des différents problèmes d?ordonnancement est d'arriver à mieux organiser le travail afin d?utiliser efficacement les ressources existantes (souvent chères et rares) et de diminuer les pertes de temps et/ou les délais de livraison autant que possible. En règle générale, les problèmes d?ordonnancement sont réputés être difficiles à résoudre d?un point de vue de la complexité de calculs ; seule une poignée d?entre eux possède des solutions algorithmiques efficaces. En conséquence, je compte investiguer plusieurs de ces modèles (flow shop, permutation flow shop, open shop, mixed shop, une seule machine et machines parallèles) sur plusieurs fronts : détermination du degré de difficulté de leur résolution, recherche de cas particuliers pertinents, utilisation de méthodes exactes et de méthodes heuristiques (l?évaluation des algorithmes heuristiques constructifs se fera par rapport à l?analyse dans le pire des cas, tandis que celle des solutions méta-heuristiques se fera d?une manière expérimentale).
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-06025
Name nom
Rebaine, Djamal
Department département
Informatique et mathématique
Organization id
52
Institution établissement
Université du Québec à Chicoutimi
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2014
Award amount
20000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
405
Area of application group en
Environment
Area of application group fr
Environnement
Area of application en
Modelling and mathematical simulation of natural processes
Area of application fr
Modélisation et simulation mathématique des processus naturels
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
1
Nb partie
5
Application title
Ordonancement d'ateliers : algorithmes et complexité
Keyword
NSERC
Application summary
La théorie de l?ordonnancement s?intéresse aux problèmes d?allocation de ressources dans le temps pour réaliser un ensemble de tâches. Le nombre de ressources étant limité, la décision d?affecter une tâche à une ressource, à un instant donné, est cruciale pour atteindre le ou les objectifs fixés au départ et /ou satisfaire les contraintes liés au problème étudié. Il est utile de mentionner que les ressources et les tâches peuvent avoir plusieurs interprétations dépendamment du contexte. Ainsi, le terme ressource peut signifier argent, processeurs, machines, énergie, matériel, etc. L?interprétation des tâches, quant à elle, peut aller des produits manufacturiers jusqu?aux processus dans les systèmes informatiques, en passant par des quarts de travail. Dans ces conditions, il est facile de constater que les problèmes d?ordonnancement sont associés ou surviennent dans la plupart des problèmes réels. Bien entendu, chaque application peut posséder ses propres spécificités dont il faut tenir compte lors de la résolution. Le programme de recherche proposé ici s?intéresse aux effets induits par la prise en compte de certaines paramètres pratiques, négligés ou non suffisamment pris en considération jusque-là dans la littérature, sur les modèles de base d?ordonnancement d?atelier, afin de les rendre plus proches de la réalité. Le premier paramètre considéré est celui des temps de latence pour exprimer les temps induits par les déplacements des tâches à travers les ressources. Le second paramètre est celui lié à l?existence de relations de précédence entre les tâches (dans certains cas, une tâche ne peut commencer son exécution qu?à la fin d?autres tâches ; ces dépendances définissent un graphe de précédence). Le troisième paramètre concerne la présence d'opérateurs qui, dans certaines situations, sont nécessaires au fonctionnement des ressources pour réaliser une solution d?ordonnancement. Et, enfin, le quatrième paramètre considéré concerne l?utilité de dupliquer des machines dans le but d?alléger les éventuels goulots d?étranglements dus à certaines ressources. Le point commun des différents problèmes d?ordonnancement est d'arriver à mieux organiser le travail afin d?utiliser efficacement les ressources existantes (souvent chères et rares) et de diminuer les pertes de temps et/ou les délais de livraison autant que possible. En règle générale, les problèmes d?ordonnancement sont réputés être difficiles à résoudre d?un point de vue de la complexité de calculs ; seule une poignée d?entre eux possède des solutions algorithmiques efficaces. En conséquence, je compte investiguer plusieurs de ces modèles (flow shop, permutation flow shop, open shop, mixed shop, une seule machine et machines parallèles) sur plusieurs fronts : détermination du degré de difficulté de leur résolution, recherche de cas particuliers pertinents, utilisation de méthodes exactes et de méthodes heuristiques (l?évaluation des algorithmes heuristiques constructifs se fera par rapport à l?analyse dans le pire des cas, tandis que celle des solutions méta-heuristiques se fera d?une manière expérimentale).