Contributions à des problèmes d'ordonnancement en ligne (l'ordonnancement temps réel de tâches à suspension et l'ordonnancement par une machine à traitement par lot)

Durant cette thése, deux problèmes d ordonnancement en-ligne ont été étudiés. Le premier problème concerne l ordonnancement temps réel de tâches à suspension. Nous avons établi des résultats sur la difficulté à résoudre un tel problème d ordonnancement (complexité, anomalies d ordonnancement et non-optimalité des algorithmes en-ligne). Nous avons établi la non-compétitivité d algorithmes en-ligne pour deux critères de performances même quand ceux-ci disposent de plus de ressources que l adversaire. Enfin, nous avons étudié avec l analyse de compétitivité différents tests d ordonnançabilité. Le second problème se rapporte à l ordonnancement par une machine à traitement par lot. Plusieurs algorithmes en-ligne compétitifs ont été présentés pour des problèmes dont la taille des lots est non bornée dont aH qui fait partie des meilleurs algorithmes en-ligne pour le problème général (son ratio de compétitivité est égal à la borne inférieure du problème (1+p52)/2 ).POITIERS-BU Sciences (861942102) / SudocTOURS-Polytech'Informat.Product. (372612209) / SudocSudocFranceF