Minimisation de la somme des retards dans un jobshop flexible

30/09/2017
Publication e-STA e-STA 2005-2
OAI : oai:www.see.asso.fr:545:2005-2:20019
DOI :

Résumé

Minimisation de la somme des retards dans un jobshop flexible

Métriques

14
8
293.73 Ko
 application/pdf
bitcache://a539a3ed1e35c382c4459a3bc98c36aee21f6a0c

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2005-2/20019</identifier><creators><creator><creatorName>Pierre Borne</creatorName></creator><creator><creatorName>Abdelkader El Kamel</creatorName></creator><creator><creatorName>Nozha Zribi</creatorName></creator><creator><creatorName>Imed Kacem</creatorName></creator></creators><titles>
            <title>Minimisation de la somme des retards dans un jobshop flexible</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 30 Sep 2017</date>
	    <date dateType="Updated">Sat 30 Sep 2017</date>
            <date dateType="Submitted">Tue 15 May 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">a539a3ed1e35c382c4459a3bc98c36aee21f6a0c</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>34034</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Minimisation de la somme des retards dans un jobshop flexible Nozha ZRIBI1 , Imed KACEM2 , Abdelkader EL KAMEL1 , Pierre BORNE1 1 LAGIS Ecole Centrale de Lille, BP 48, 59651 Villeneuve d’Ascq Cedex, France 2 ISTIT Université de Technologie de Troyes, BP 2060, 10010 Troyes Cedex, France {nozha.zribi, abdelkader.elkamel, p.borne}@ec-lille.fr, imed.kacem@utt.fr Résumé—Dans cet article nous considérons le problème d’or- donnancement d’un job-shop flexible avec dates de disponi- bilité et dates dues. Nous proposons une méthode heuris- tique en deux phases pour la minimisation de la somme des retards. La première consiste à affecter les tâches selon une heuristique de la littérature et à améliorer le résultat avec une recherche Tabou. La deuxième étape permet d’optimiser les solutions données par les heuristiques classiques (EDD, MOD, LRPT...) par le biais d’un algorithme évolutionniste. Mots-clés— Job-shop flexible, affectation, ordonnancement, somme des retards, recherche Tabou, algorithme génétique, règles de priorité. I. Introduction Le problème des job-shops flexibles est une extension du problème classique connu sous le nom de job shop. Il s’agit de planifier et d’organiser des tâches à réaliser sur un ensemble de machines selon des durées d’exécution variables [17], [18], [13], [7], [3]. Dans la littérature, la plupart des approches cherchent à optimiser le critère du makespan (la date de fin d’exécution de la dernière tâche). Elles considèrent deux étapes dans la résolution d’un tel problème [3], [13], [18]. La première consiste à construire une affectation pour les différentes tâches sur les machines adéquates. La deuxième est l’ordonnance- ment des tâches et la détermination des dates de début d’exécution en tenant compte de différentes contraintes conjonctives (précédence) et disjonctives (capacités des ma- chines). Néanmoins, Dauzère-Pérès et ses co-auteurs ont construit une approche intégrée qui traite conjointement l’affectation et le séquencement [7]. Mastrolilli a également repris cette approche intégrée pour améliorer ces résultats [17]. Récemment, Kacem a proposé une étude de plu- sieurs modèles de résolution et des bornes inférieures pour quelques critères pour l’évaluation des solutions [14]. Dans nos travaux précédents, nous avons mis en place une approche hiérarchique pour résoudre le problème du job-shop flexible afin de minimiser le makespan [22]. Dans cet article, nous proposons d’adapter cette méthode pour la minimisation de la somme des retards dans un job- shop flexible. Cet article est organisé comme suit. Après la formulation du problème traité, nous présentons dans Fig. 1. Exemple d’un PF JSP la section III l’algorithme proposé pour la résolution du sous-problème d’affectation. La quatrième section décrit l’approche évolutionniste proposée pour résoudre le sous- problème de séquencement. Des résultats numériques sont ensuite présentés, et nous terminons cet article par quelques conclusions sur ce travail de recherche. II. Formulation du problème du job-shop flexible avec dates de disponibilité et dates dues imposées Le problème est d’organiser la réalisation de N jobs sur M machines. Chaque job Jj représente un nombre nj d’opérations ordonnées (contraintes de précédence). Chaque opération i d’un job Jj (notée Oi,j) peut être réalisée sur n’importe quelle machine disponible. La durée d’exécution pi,j,k de l’opération Oi,j dépend de la machine Mk affectée à cette opération. Pour chaque problème de job-shop flexible, on peut associer un tableau des durées opératoires tel que : PF JSP = {pi,j,k ∈ IN∗ |1 ≤ j ≤ N; 1 ≤ i ≤ nj; 1 ≤ k ≤ M},Un exemple est représenté dans Fig.1. Dans ce problème, nous faisons les hypothèses suivantes : ◦ Toutes les machines sont disponibles à la date t = 0; ◦ Chaque job Jj peut commencer à la date t = rj ; ◦ Pour chaque job, l’ordre des opérations est fixé dès le départ et ne peut être modifié (contraintes de précédences dans la gamme) ; ◦ Chaque job possède une date échue di ; ◦ Une machine ne peut exécuter qu’une seule opération à la fois ; ◦ La préemption n’est pas autorisée. Le problème considéré présente deux sous-problèmes. Le premier est l’affectation de chaque opération Oi,j sur une machine Mk. Le deuxième est la détermination d’un ordonnancement qui minimise la somme totale des retards. Par la suite nous proposons un algorithme en deux phases pour la résolution du problème d’ordonnancement d’un job-shop flexible avec minimisation de la somme des retards. III. Le problème d’affectation Il existe différents critères associés à l’affectation des opérations sur les machines. Par exemple, on doit équilibrer la charge des différentes machines, minimiser la charge to- tale de toutes les machines, minimiser la charge de la ma- chine critique (la machine la plus chargée)... Dans [14], l’auteur a proposé une heuristique appelée ap- proche par localisation permettant d’affecter les opérations sur les machines tout en équilibrant la charge des différentes machines. En effet, cette heuristique affecte les opérations d’une manière itérative tout en tenant compte des durées opératoires et des charges des machines sur lesquelles nous avons deja affecté des opérations. On se propose d’améliorer la solution donnée par l’ap- proche par localisation par une recherche Tabou qui mini- mise le critère suivant : Crit = α × Cr2 + (1 − α) × Cr3 (1) tel que : ◦ Cr2 est la charge de la machine critique : Cr2 = maxk {Wk}, ◦ Wk est la charge de la machine k, ◦ Cr3 est la charge totale de toutes les machines Cr3 = P k {Wk}, ◦ α est une variable appartenant à l’intervalle [0, 1]. Les deux critères choisis ont beaucoup d’influence sur la valeur de la somme des retards et aussi sur la difficulté du problème. Considérons le coefficient Aj = dj −rj Pj (Pj est la durée totale du job j). Ce coefficient mesure la sévérité de la contrainte de la date d’échéance imposée (dj est indépendant de l’affectation) du job j et par conséquent la difficulté du problème. La charge totale des machines peut être interprétée aussi comme la durée totale de tous les jobs. Il est clair que ce critère affecte la valeur des Aj (Aj et Pj sont inversement proportionnelles) et ainsi de la valeur du retard de chaque job. Il est évident aussi que la répartition des charges sur les différentes machines ainsi que la charge de la machine cri- tique affectent la difficulté du problème et la somme des retards. La recherche Tabou est une méthode itérative générale d’optimisation combinatoire, elle est très performante sur un nombre considérable de problèmes d’ordonnancement. Fig. 2. Exemple d’un PJSP Elle consiste à se déplacer de solution en solution en s’in- terdisant de revenir en une configuration déjà rencontrée [11]. A. Paramètres de la recherche Tabou A.1 La solution initiale La solution initiale est calculée en utilisant l’approche par localisation A.2 Mouvement Le mouvement consiste à réaffecter une opération à différentes machines. Toutes les possibilités sont testées et le meilleur mouvement minimisant le critère Crit est sélectionné. A.3 Restriction Tabou La liste Tabou est constituée des paires {op, m o}, où op désigne l’opération initialement affectée à la machine m o et ayant été réaffectée à une autre. A.4 Critère d’aspiration Dans cette application, nous avons utilisé le critère d’as- piration le plus connu et le plus utilisé dans la littérature qui est le critère d’aspiration globale. Ce critère permet à un mouvement Tabou d’être candidat pour la sélection, s’il conduit à une nouvelle meilleure solution. A.5 Critère d’arrêt L’algorithme s’arrête si un nombre donné d’itérations est atteint. Le nombre d’itérations est fixé à 100. Après avoir résolu le sous problème d’affectation, le problème du job-shop flexible se réduit à un problème de job shop classique. ◦ A chaque opération Oi,j, on définit Mk comme la ma- chine sur laquelle Oi,j va être exécutée (Mk est la ma- chine affectée à Oi,j pendant la première phase du pro- gramme), et une durée opératoire pi,j égale à pi,jk. ◦ Pour chaque problème de job-shop, on peut associer un tableau D des durées opératoires tel que : PJSP = {pi,j ∈ IN∗ , 1 ≤ j ≤ N; 1 ≤ i ≤ nj; }. Un exemple est representé dans Fig.2. Dans la section suivante nous proposons un algorithme génétique permettant d’optimiser le séquencement des opérations. Le critère choisi est la minimisation de la somme totale des retards exprimé par la formule 2 sui- vante : T1 T2 ... Tz TNT (1, 2, 3) (2, 2, 3) (i, j, k) (3, 2, 4) Fig. 3. Codage proposé • = { } ∈ • = { } ∈ { } ∈ • ( ) = = + • = + • = + Fig. 4. Procédure d’ordonnancement T = N X j=1 max j (Cj − dj, 0) (2) avec Cj la date de fin d’exécution du job j. IV. Algorithme génétique pour la minimisation de la somme des retards dans un job-shop De nombreux travaux dans la littérature ont été dédiés au problème d’ordonnancement avec minimisation de la somme des retards notamment pour les problèmes à une machine [1],[6] et les problèmes à machines parallèles [21]. Certains travaux ont concerné la minimisation de ce critère dans un atelier de type job-shop [19], [20], [12]. Les règles de priorité ont été fréquemment utilisées pour résoudre ce problème [15]. D’autres approches heuristiques basées sur la recherche Tabou ont été récemment développées [20]. Le problème d’ordonnancement dans un job-shop est NP-difficile [4], [10]. Les problèmes de minimisation de la somme des retards sur une machine est aussi NP-difficile [9]. Nous proposons alors dans ce qui suit une metaheuris- tique basée sur les algorithmes génétiques [8], [2], [5] pour la minimisation de la somme des retards dans un job-shop. A. Codage : Liste des opérations Nous choisissons d’utiliser un codage linéaire simple. Il consiste à représenter le séquencement par une liste de NT opérations (NT