Nonlinear preservers

Dans cette thèse, nous sommes intéressés par des problèmes de préservation des applications non-linéaires entre deux algèbres de Banach complexes unitaires A et B. En général, ces problèmes demandent la caractérisation des applications φ : A → B non nécessairement linéaires, qui laissent invariant une propriété, une relation ou un sous-ensemble. Dans le Chapitre 3, la description des applications surjectives φ de B(X) sur B(Y), qui satisfont c(φ(S)±φ(T)) = c(S ± T), (S,T ∈ B(X)), est donnée, où c(·) représente soit le module minimal, ou le module de surjectivité ou le module maximal et B(X) (resp. B(Y)) dénote l’algèbre de tous les opérateurs linéaires et bornés sur X (resp. sur Y). Dans le Chapitre 4, une question similaire pour la conorme des opérateurs, est considérée. La caractérisation des applications bicontinues et bijectives φ deB(X) surB(Y), qui satisfont γ(φ(S ± φ(T)) = γ(S ± T), (S,T ∈ B(X)), est obtenue. Le Chapitre 5 est consacré à la description des applications surjectives φ1,φ2 d’une algèbre de Banach semisimple A sur une algèbre de Banach B avec un socle essentiel, qui satisfont σ(φ1(a)φ2(b)) = σ(ab), (a,b ∈ A). Aussi, la caractérisation des applications φ de A sur B, sous les mêmes hypothèses sur A et B, qui satisfont σ(φ(a)φ(b)φ(a)) = σ(aba), (a,b ∈ A), est donnée. Comme conséquences, nous incluons les résultats obtenus au cas des algèbres B(X) et B(Y).

Efficient algorithms to solve scheduling problems with a variety of optimization criteria

La programmation par contraintes est une technique puissante pour résoudre, entre autres, des problèmes d’ordonnancement de grande envergure. L’ordonnancement vise à allouer dans le temps des tâches à des ressources. Lors de son exécution, une tâche consomme une ressource à un taux constant. Généralement, on cherche à optimiser une fonction objectif telle la durée totale d’un ordonnancement. Résoudre un problème d’ordonnancement signifie trouver quand chaque tâche doit débuter et quelle ressource doit l’exécuter. La plupart des problèmes d’ordonnancement sont NP-Difficiles. Conséquemment, il n’existe aucun algorithme connu capable de les résoudre en temps polynomial. Cependant, il existe des spécialisations aux problèmes d’ordonnancement qui ne sont pas NP-Complet. Ces problèmes peuvent être résolus en temps polynomial en utilisant des algorithmes qui leur sont propres. Notre objectif est d’explorer ces algorithmes d’ordonnancement dans plusieurs contextes variés. Les techniques de filtrage ont beaucoup évolué dans les dernières années en ordonnancement basé sur les contraintes. La proéminence des algorithmes de filtrage repose sur leur habilité à réduire l’arbre de recherche en excluant les valeurs des domaines qui ne participent pas à des solutions au problème. Nous proposons des améliorations et présentons des algorithmes de filtrage plus efficaces pour résoudre des problèmes classiques d’ordonnancement. De plus, nous présentons des adaptations de techniques de filtrage pour le cas où les tâches peuvent être retardées. Nous considérons aussi différentes propriétés de problèmes industriels et résolvons plus efficacement des problèmes où le critère d’optimisation n’est pas nécessairement le moment où la dernière tâche se termine. Par exemple, nous présentons des algorithmes à temps polynomial pour le cas où la quantité de ressources fluctue dans le temps, ou quand le coût d’exécuter une tâche au temps t dépend de t.