MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE ... · L’exemple de la planification ... où elles seront rassemblées par la ... Lors du séminaire hebdomadaire du département

__________________________________________________________________________________________ Université de BLIDA. Rapport d’Activités Annuel 2004.

MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE

SCIENTIFIQUE

COMITE NATIONAL D’EVALUATION ET DE PROGRAMMATION DE LA RECHERCHE UNIVERSITAIRE

PRESENTATION DE L’ETAT D’AVANCEMENT ANNUEL DU PROJET DE RECHERCHE


Ministère de l'Enseignement Supérieur et de la recherche scientifique

Université de BLIDA

Vice Rectorat Chargé de la Recherche et de la Post-Graduation Direction de la Recherche

RAPPORT d'ACTIVITES

Final Annuel X

I. Identification . Période : du 01 Janvier 2004 au 31 Décembre 2004 Projet N° : B*0901/03/04 Faculté : Sciences Département : Mathématiques Chef du Projet : DERBALA Ali Intitulé du Projet : OASEO. Ordonnancement dans les ateliers et dans les systèmes d’exploitation d’ordinateurs. Documents Joints : 1) copie d’article publié à JCIIE, Journal of Chinesse Institute of industrial Engineers. 2) lettre d’acceptation et copie du résumé d’un article publié à MSS04, USTHB, ALGER.

3) Lettre d’acceptation pour présentation orale à la conférence ICEE’2003et copie de l’article soumis( reportée à une date ultérieure).

4)Attestations d’exposés au séminaire hebdomadaire à l’USTHB, Alger avec affichage.

5) Attestations d’exposés au séminaire hebdomadaire à l’USTBlida avec affichage.

6)Trois copies des pages de garde des mémoires d’ingénieurs 7) Copie de la page de garde d’une thèse de doctorat d’état. Nombre total de pages : 08

x


I. Résultats obtenus :

Par Dr. Derbala Ali

Des résultats sont rédigés en une thèse (une copie de la page de garde est ci jointe).

Des résultats sont obtenus. Ils ont fait l’objet de communications.

Nous présentons l’outil des processus bandits, des processus à 2-décisions semi-Markoviens,

pour la résolution des problèmes d'ordonnancement stochastiques sur une machine.

Une expression d’une priorité dynamique particulière allouée aux tâches dans un système

d’exploitation d’ordinateurs multitâches s’interprète comme des problèmes

d’ordonnancement de tâches détériorantes à durée opératoires variables et de tâches en retard

ou en attente de réparation de la machine. Plusieurs applications industrielles sont

mentionnées pour ce modèle. L’exemple de la planification de la machine de maintenance ou

de service dans la production d’acier où la matière coule durant les périodes d’attente. Dans

la gestion des stocks où des produits périssent ou se détériorent, où la demande ou le manque

croit. Des éléments se détériorent en stockage. Des éléments radioactifs qui se désintègrent

dans le temps. Dans l’ordonnancement de fabrication des pneus, si la température d’un

pneu de caoutchouc dans un espace d’attente entre le fourneau et la machine de moulage

chute, alors il a besoin d’être réchauffé jusqu'à la température de moulage. Le réchauffement

dépend du temps d’attente dans l’espace d’attente dont l’ordonnancement dépendra. Nous

montrons qu’elle est aussi une règle d’indice.

Dans la partie ordonnancement à machines parallèles, n’importe quel ordonnancement peut

être améliorer en prenant l’avantage des opérations parallèles sur des machines identiques.

On peut voir “m” machines travaillant simultanément sur une seule tâche comme une seule

machine avec m fois la puissance d’une machine de base. Il est meilleur de fournir une

capacité avec une seule machine qu’avec un nombre équivalent de machines distinctes mais

pour des considérations de fiabilité la réciproque est bonne. Si une machine tombe en panne,

m – 1 machines resteront en marche. On suppose que les tâches sont dans un atelier et qu’il y

a plus d’une machine pour les exécuter. Le critère de performance est la longueur de

l’ordonnancement ou la date de fin de la dernière tâche à exécuter est à minimiser. Dans le

cas de machines parallèles, le makespan devient intéressant. En partageant la charge sur les

machines parallèles, l’ordonnanceur assure un bon équilibre. Trois types de machines

parallèles sont considérées, identiques, uniformes et dédiées. Uniformes où les machines sont

les mêmes mais leur vitesse sont différentes. Les machines dédiées , ne font pas les mêmes

opérations.


Notre motivation est de répondre à un certain nombre de problèmes ouverts

d’ordonnancement de machines parallèles. On considère les problèmes qui sont NP-difficiles.

En général on ne cherche pas une solution optimale, mais on se contentera d’une solution

approchée donnée par un algorithme approximatif en un temps polynomial. Dans cette article,

on résume tous les résultats connus sur les ordonnancement de machines parallèles quand le

critère d’optimalité est la longueur de l’ordonnancement ou le makespan. D’un article récent

de Schuurman et Woeginger (1999), nous relatons quatre problèmes ouverts sur de tels

algorithmes.

Par Mr Bendraouche :

Les travaux de recherche abordés pendant cette année se résument comme suit :

L’étude d’un problème d’ordonnancement Flow-shop à deux niveaux d’exécution.

Le problème peut être décrit comme suit :

On dispose d’un ensemble de n taches T1 ,T2 ,T3, … ,Tn.

Chaque tache est décomposée en m opérations et doit être exécutée sur deux niveaux

d’exécution.

Au premier niveau d’exécution il y a m machines M1, M2, M3,…,Mm dédiées et au

deuxième niveau on a une machine assembleuse Ma qui rassemble les m opérations de

chaque tache dés qu’elles soient toutes exécutées.

Au premier niveau d’exécution les machines Mi ( i =1,2,…,m ) sont disposés en parallèle.

Quand les m opérations sont achevées au premier niveau elles passeront au second niveau

où elles seront rassemblées par la machine assembleuse Ma.

Le problème consiste alors à chercher un ordonnancement optimal qui minimise la durée

totale de l’ordonnancement Cmax.

Au second semestre, l’étude pratique d’un problème d’ordonnancement Flow-Shop de

type Assemblage à trois machines est réalisée.

Dans une usine de fabrication de pompes à incendies , chacune de ces dernières se

compose d’un corps, d’un châssis et d’un moteur. Le corps et le châssis sont produits au

sein de l’usine dans deux départements différents ,tandis que le moteur est acheté de

l’extérieur.

Les productions du corps et du châssis peuvent avoir lieu en parallèle, mais l’opération

d’assemblage (montage ) finale ne peut commencer que si le corps et le châssis son

délivrés à la chaîne de montage où les moteurs sont reçus directement du fournisseur.


Pour un ensemble de commandes donné de pompes à incendies, le problème du fabricant

est de trouver un plan de production optimal qui permet l’accomplissement de toutes les

commandes dans un temps minimum..

II . Publications et communications

1) Derbala Ali (2004). Deterioration function yielding an index rule. Journal of Chinese

Institute of Industrial Engineers. JCIIE, vol.21. No.3. pp.213-218.

2) Derbala Ali. Une fonction de détérioration de tâches produisant une règle d’indice.

MSS’2004. Modélisation stochastique et statistique, Recueil des résumés, Alger 17-

18-19 Avril 2004, pp.12.

3) M.Hamoudi et M. Bendraouche. Calcul de la capacité optimale du moteur

asynchrone monophasé par la théorie du double champs et des deux axes. The first

International Conference on Energy Efficiency, ICEE’03, Université de Boumerdès

( reporté pour une date ultérieure).

II.1Articles soumis pour publication dans des Journaux scientifiques

1) Boumédiène-Hocine Merouane. Les algorithmes d’approximation dans les problèmes

d’ordonnancement sur des machines parallèles identiques de tâches dépendantes. Soumis à

JIE2’04, secondes journées d’informatique pour l’entreprise.

2) Abbas Moncef et Derbala Ali ( 2003). An analysis of a dynamic allocation index. Article

soumis au Journal of mathematical modelling and algorithms.

II.2. Exposés

Lors du séminaire hebdomadaire du département de Recherche opérationnelle de la faculté

des mathématiques de l’ Université USTHB d’Alger et de l’USTBlida trois communications

avec programme ci-joint sont faites.


1) Boumédiène-Hocine Sofiane et Derbala Ali. Les algorithmes d’approximation dans

les Pbs d’ordonnancement de tâches dépendantes à machines parallèles identiques.

USTHB, Alger,27 Avril 2004.

2) Boumédiène-Hocine Sofiane. Les algorithmes d’approximation dans les Pbs

d’ordonnancement de tâches dépendantes à machines parallèles identiques. USTBlida,

01 Juin 2004.

3) Derbala Ali. La problématique d’un ordonnanceur dans un système d’exploitation

d’ordinateurs multitâches monoprocesseur. USTBlida, 01 Juin 2004.

III. Soutenances

A l’USTHB et en date du 11 Octobre 2004, dans la salle 113, salle des séminaires de la

faculté de mathématiques, une thèse de doctorat d’état est soutenue.

1) Derbala Ali. Problématique d’un ordonnanceur dans un système d’exploitation

d’ordinateur multitâches monoprocesseur. thèse de doctorat d’Etat, Octobre 2004.

Au département de mathématiques, de la faculté des sciences de l’université de Blida et dans

le cadre pédagogique et de la recherche continue, des travaux ont été proposé, suivis et

rédigés sous forme de mémoires d’ingéniorat de mathématiques appliquées. Un binôme

d’élèves ingénieurs soutiendra son mémoire.

2) Bouzefrane Mohamed. Résolution d’un problème d’ordonnancement à m machines à deux

niveaux d’exécution par une méthode de séparation et d’évaluation. Juin 2003.

3)Bouzit Abdelhak et Nait Mohamed Ouail. Résolution d’un problème d’ordonnancement de

grand projet par la méthode PERT. Mémoire d’ingénieurs, Juillet 2004.

4) Soudani Benabdallah et Soualem Hocine. Minimisation de la durée d’un ordonnancement

Flow-shop de type asemblage à deux étages. 2004.

IV. Encadrement de post graduants

Dans le cadre de la post-graduation du département de mathématiques option Recherche

opérationnelle, trois (03) élèves magister sont encadrés par mes soins. Leur nom et leur thème

sont respectivement :

1) Boumediène-Merouane Hocine. Les problèmes d’ordonnancement à machines parallèles de

tâches dépendantes. Septembre 2003.


2) Kali Abdesselem. Les indices de Gittins dans les ordonnancements stochastiques :

Existence, caractérisation et détermination. Septembre 2004.

3) Lemdani Rachid. Résolution des problèmes d’ordonnancement stochastiques par les

processus bandits. Septembre 2004.

V. Conclusion

Nous avons réalisé les implémentations d’une stratégie d’ordonnancement originale appelée

OPBM et même de résoudre un problème de privation d’utilisation du processeur pour des

classes de basses priorités, réalisé l’implémentation d’une stratégie de type job shop et des

stratégies dans les problèmes de type flow shop hybride.

Les problèmes d’ordonnancement avec le processus d’assemblage au dernier niveau de la

production sont d’un grand intérêt théorique et pratique. Cependant des recherches ultérieures

sur des problèmes analogues avec d’autres fonctions objectifs sont à entreprendre.

Le problème étudié au second semestre est une application du problème général étudié au

premier semestre. Ce type de problème se rencontre très fréquemment dans le milieu

industriel qui comporte plusieurs facilités et dans lequel se trouve un atelier d’assemblage où

les montages partiels principaux de diverses installations de fabrications sont assemblés pour

produire le produit final. Pour Mr Bendraouche, les travaux entrepris dans ce projet rentrent

dans le cadre de la préparation de la thèse d’Etat en Mathématiques, option recherche

opérationnelle. Les résultats obtenus sont positifs et encourageants pour la suite.

L’étudiante Attalah Karima est encadrée par Dr. MANSEUR Salah

L’étudiant El Moussaoui H est encadré par Dr. HANANE Farouk

et Khelifi Sofiane est encadré par Dr. BLIDIA Mostefa

De ce fait ils ne font pas partie de l’équipe que je dirige.

Boumediène-Merouane Hocine, Kali Abdesselem et Lemdani Rachid sont intégrés à

notre équipe du projet.

Etat d’avancement : ......................................……………………………… …….30%.


Le Chef du Projet

Date :

Avis du Conseil Scientifique

...............................................................................................................................................................

...............................................................................................................................................................

................................................................................................................................................................

Le Président du C.S

Date : ……………........................... Réservé au COMITE NATIONAL D’EVALUATION Rapport reçu le : ...............................

Le Directeur de la Recherche