Ordonnancement a deux serveurs parallèles temps de service et inter-arrivées constants

Abstract

Les problèmes de scheduling et de sequencing font l'objet d'un intérêt croissant di, entre autres, 4 leurs applications dans le domaine informatique. La théorie de la complexité y trouve également un terrain d'élection‘?), on y suppose les clients (taches... etc.) présents au début du traitement et les temps de services connus ; on pourrait donc qualifier ces problèmes de "statiques déterministes". A l'opposé, les problèmes dynamiques aléatoires, posés par les systèmes ouverts ou fermés, ou 1'époque d'arrivée des clients est réglée par un processus stochastique et od les temps de services sont aléatoires, ont également fait l'objet de nombreuses études. Nous avons étudié un problème intermédiaire que nous appellerons dynamique déterministe. On suppose les temps inter-arrivées (w) et les temps de services (a et b) pour deux serveurs parallèles (A et B), connus et constants. Nous avons obtenu un certain nombre de règles et propriétés permettant de déterminer la solution optimale du problème d'affectation des clients aux serveurs, selon le critère du cout moyen minimum (temps de service + temps d'attente) lorsque b est inférieur ou égal a 2w. Lorsque b est supérieur 4 2w, ces propriétés permettent la construction d'une heuristique et d'une condition suffisante d'optimalité (CS).