Ordonnancement des opérations dans un atelier de production agroalimentaire en minimisant le coût

27/09/2017
Publication e-STA e-STA 2006-1
OAI : oai:www.see.asso.fr:545:2006-1:19969
DOI :

Résumé

Ordonnancement des opérations dans un atelier de production agroalimentaire en minimisant le coût

Métriques

24
9
49.43 Ko
 application/pdf
bitcache://4509cb26bd50c7f043edd384dc53913a2dc302fc

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:2006-1/19969</identifier><creators><creator><creatorName>Pierre Borne</creatorName></creator><creator><creatorName>Fatma Tangour</creatorName></creator></creators><titles>
            <title>Ordonnancement des opérations dans un atelier de production agroalimentaire en minimisant le coût</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Wed 27 Sep 2017</date>
	    <date dateType="Updated">Wed 27 Sep 2017</date>
            <date dateType="Submitted">Fri 20 Jul 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">4509cb26bd50c7f043edd384dc53913a2dc302fc</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33906</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Ordonnancement des opérations dans un atelier de production agroalimentaire en minimisant le coût Fatma Tangour1, 2 et Pierre Borne2 1 LARA Automatique, École Nationale d'Ingénieurs de Tunis, BP 48, Le Belvédère 1002 Tunis, Tunisie 2 LAGIS, École Centrale de Lille, Cité scientifique, BP 48, 59650 Villeneuve d'Ascq Cedex, France fatma.tangour@laposte.net, slim. hammadi@ec-lille.fr, pierre.borne@ec-lille.fr, mohamed.benrejeb@enit.rnu.tn RÉSUMÉ : Cette communication porte sur la recherche d’une solution au problème d’ordonnancement dynamique à une machine d’un atelier flexible de production agroalimentaire. La méthode de résolution mise en œuvre avec succès, consiste d’abord à explorer les différents cas d’ordonnancements réalisables d’un ensemble d’opérations candidates à être ordonnancées sur la même machine et d’identifier le meilleur optimisant le coût des produits périmés et le coût de discount de distribution, deux critères spécifiques à l’industrie agroalimentaire , des coefficients tenant compte du chan- gement de la production pouvant être en plus introduits dans le cas où une commande urgente doit être favorisée. MOTS-CLÉS : atelier agroalimentaire, ordonnancement dynamique, règles de dominance, minimisation du coût, ap- proche multicritère 1. INTRODUCTION L’évolution et la mondialisation de la production ainsi que l’ouverture des marchés internationaux ont poussé les industriels à se diriger vers des systèmes de fabrica- tion flexibles ; ceci conduit à mettre en place une logique industrielle qui remet en cause certains fondements des habitudes de la production telles que l’organisation et la gestion des ateliers de production : c’est le problème d’ordonnancement (Mesghouni, 1999). Ces nouveaux domaines d’application rendent plus complexes les pro- blèmes d’ordonnancement des tâches ; ce qui exige la résolution rigoureuse de ces problèmes (Carlier, et al., 1988). La nature des produits et des procédés ainsi que les contraintes de qualité et de contrôle des coûts font que les besoins des industriels de l’agroalimentaire en matière de gestion des données techniques sont assez différents de ceux des entreprises manufacturières (Ga r- gouri et al., 2001) (Gargouri et al., 2002b). Ainsi, l’évolution et les caractéristiques dynamiques des ate- liers industriels, en particulier ceux des industries agroa- limentaires, imposent la génération, en temps réel, d’une décision du processus d’ordonnancement (Gargouri et al., 2003). En général, les problèmes d’ordonnancement sont des problèmes d’optimisation multicritères ou muti- objectifs (Gzara, 2001). Ainsi, la meilleure solution, ap- pelée aussi solution optimale, est la solution ayant obte- nue la meilleure évaluation au regard du critère défini. Dans notre travail, nous nous intéressons aux critères de la minimisation du coût des produits périmés et du dis- count de distribution, qui sont spécifiques à l’industrie agroalimentaire ; la solution optimale correspond à celle dont le coût total est minimal. 2. MÉTHODES DE RÉSOLUTION- POSTION DU PROBLÈME Résoudre un problème d'optimisation consiste à trouver la ou les meilleure(s) solution(s), vérifiant un ensemble de contraintes et d'objectifs définis par l’utilisateur (Ba- richard et al., 2003). Pour déterminer si une solution est meilleure qu’une autre, il est nécessaire que le problème introduise un critère de comparaison. Les problèmes d’optimisation sont, en général, difficiles à résoudre. Plusieurs méthodes sont utilisées afin de trouver une réponse satisfaisante à ces problèmes. On distingue les méthodes exactes et les méthodes appro- chées (Barichard, 2003). Les méthodes exactes, telles que la méthode Branch and Bound (Baptiste et al., 1996) (Le Pape, 1995), la pro- grammation dynamique, etc, examinent, d’une manière implicite, la totalité de l’espace de recherche et produi- sent, en principe, une solution optimale. Lorsque le temps de calcul nécessaire pour atteindre cette solution est excessif, les méthodes approchées peuvent produire une solution quasi-optimale au bout d’un temps de calcul raisonnable. Parmi ces méthodes on distingue les algo- rithmes génétiques (Holland, 1975), la recherche tabou (Glover et al., 1997), le recuit simulé (Kirkpatrick et al., 1983),etc. Optimisation combinatoire Définition : un problème d’optimisation combinatoire est défini par un ensemble d’instances I , chaque instance I est un couple ( , )X f où X S⊆ est un ensemble fini de solutions admissibles de l’ensemble S des solutions, et f une fonction coût (ou objectif) à minimiser f : X R→ . Le problème est de trouver une solution * s ∈ X telle que ( ) ( )f s f s ∗ ≤ pour tout élément s de X . Notion de dominance En ordonnancement, le concept de dominance d’un sous- ensemble de solutions est important afin de limiter la complexité algorithmique liée à la recherche d’une solu- tion optimale au sein d’un grand ensemble de solutions. Pour trouver une telle solution relative à l’optimisation multi-objectifs, il s’avère nécessaire de définir une rela- tion d’ordre entre les solutions dite relation de domi- nance, pour identifier les meilleurs compromis. La règle de dominance est une contrainte qui peut être ajoutée au problème initial sans changer la valeur de l’optimum (Jouglet., 2002). La méthode de résolution la plus utili- sée est celle définie au «sens de Pareto » (Barichard, 2003). Position du Problème Pour construire un ordonnancement multicritère adapté à l’industrie agroalimentaire, il s’agit de distinguer les critères spécifiques à cette industrie tels que la périssabi- lité des produits et le discount de distribution. L’objectif est alors de sélectionner parmi l’ensemble des opérations candidates à ordonnancer, celle qui présente le meilleur compromis entre les différents critères en réduisant et en filtrant l’espace de recherche initial. La décision d’éliminer ou de maintenir une opération permet d’éviter la péremption de certains composants et entraîne la di- minution des coûts de ces composants périmés ainsi que le coût de discount de distribution. 3. APPLICATION DES RÈGLES DE DOMI- NANCE A L’ORDONNANCEMENT DES OPÉRATIONS Notations x i t : date effective de début de fabrication de l’opération Oj sur le poste x i r : date de début au plus tôt de l’opération Oi i γ : date de fin effective de l’opération Oi i δ : durée opératoire de l’opération Oi i P : produit fini de l’opération Oi ik c : ième k composant de l’ensemble des compo- sants de l’opération Oi ik v : date de validité limite du composant ikc iP C : date de fin de fabrication du produit i P i liv P d : date de livraison du produit i P fP d : date de fin de la séquence P iP DV : durée de vie du produit i P iP DR : délai de retour du produit i P rev ik P : prix de revient du composant ikc i ven P P : prix de vente unitaire du produit i P i stk P C : coût du stockage par unité de temps d’une unité du produit i P 3 .1 Formulation du problème Etant donné un ensemble E de n opérations à ordonnan- cer entre deux séquences P et A d’opérations déjà or- donnancées. Pour un couple d’opérations Oi et Oj de l’ensemble E des opérations candidates à l’ordonnancement. Le problème est de déterminer la- quelle de ces opérations est à ordonnancer en premier, c’est à dire l’opération dominante, afin de minimiser : • le coût des produits périmés, • le coût du discount de distribution. Il s’agit donc, de filtrer l’espace de recherche pour cons- truire un ordonnancement qui satisfait ces critères tout en respectant les contraintes (Gargouri, 2003). 3 .2 Distinction de différents cas d’ordonnancement Pour avoir le meilleur ordonnancement qui optimise les critères cités, tous les cas réalisables sont, dans cette partie, étudiés puis comp arés. Cet ordonnancement est ensuite déterminé en vue de son exploitation. 1er cas : Ordonnancement initial S1 2ème cas : Ordonnancement S2, relatif à l’échange dans S1 entre l’opération Oi et l’opération Oj 3ème cas : Ordonnancement S3, relatif à l’insertion de l’opération Oj juste après la séquence P du cas 2 4ème cas : Ordonnancement S4, relatif à la permutation entre l’opération Oi et l’opération Oj du cas 3 3.3 Calcul des coûts pour les différents cas Dans le cas général, le coût des produits périmés ( )1 K S et celui du discount de distribution ( )2 K S s’écrivent comme suit : ( ) ( ) ( )1 max 0, x i ikrev i ik x i k i ik t v K S P t v α − = −       ∑ ∑ (1) ( ) ( )2 max 0, i i ven liv stk i i i i P P P P P P i i P d C C DV DR K S β= − × + −       ∑ (2) La fonction coût, représentant le coût total ( )tot K S , est la somme de ces deux coûts : ( ) ( ) ( )1 2 tot K S K S K S= + (3) Remarque : Les coefficients i α et i β favorisent une gamme par rapport à une autre par exemple dans le cas où une commande urgente est plus intéressante (de point de vue coût) qu’une autre qui est en cours de production, la commande qui est en urgence est alors favorisée et lancée en production alors que la production de l’autre gamme est interrompue. S1 Oi AP Oj S2 Oj AP Oi S3 Oj OiP A S4 Oi OjP A • Cas de l’ordonnancement 1 S Pour l’ordonnancement 1 S où les séquences A et P sont déjà ordonnancées , le coût des produits périmés 1 1 ( )K S est formulé par l’expression (1) et le coût du discount de distribution 2 1 ( )K S est formulé par l’expression (2). Le coût total relatif à cet ordonnancement est alors : ( ) ( ) ( )1 1 1 2 1 tot K S K S K S= + (4) • Cas de l’ordonnancement 2 S L’échange entre les opérations Oi et Oj, tout en gardant la séquence A, conduit à l’ordonnancement 2 S . Dans ce cas il faut mettre à jour les dates de début et de fin des opé- rations. Soient : 2 x j t : date de début effective de l’opération Oj, 2 x j t ( )max ,fP j d r= 2 j γ : date de fin de l’opération Oj, ( )2 max ,fP j jj d r δγ += 2 x A t : date de début effective de la séquence A, 2 x A t = ( )2 max ,A j r γ 2 A γ : date de fin effective de la séquence A, 2 A γ = ( )2 max ,A j A r γ δ+ 2 x i t : date de début effective de Oi, ( )2 2 max , x i i A t r γ= 2i γ : date de fin de Oi, ( )22 max ,i A ii r γ δγ += Le coût total relatif à cet ordonnancement est alors ( ) ( ) ( )2 1 2 2 2 tot K S K S K S= + (5) • Cas de l’ordonnancement 3 S Pour le cas de l’insertion de l’opération Oj juste après la séquence P, l’ordonnancement 3 S est obtenu et les dates sont mises à jour comme suit : 3 x j t : date de début effective de l’opération Oj, 3 x j t ( )max ,fP j d r= 3 j γ : date de fin effective de l’opération Oj, ( )3 max ,fP j jj d r δγ += 3 x i t : date de début effective de Oi, ( )33 max ,i j x i rt γ= 3i γ : date de fin de Oi, ( )33 max ,i j ii r γ δγ += 3 x A t : date de début effective de la séquence A, 3 x A t = ( )3 max ,A i r γ 3 A γ : date de fin effective de la séquence A, 3 A γ = ( )3 max ,A i A r γ δ+ Le coût total relatif à cet ordonnancement est alors : ( ) ( ) ( )3 1 3 2 3 tot K S K S K S= + (6) • Cas de l’ordonnancement 4 S Pour le cas de l’insertion de l’opération Oj juste après l’opération Oi, l’ordonnancement 4 S est obtenu et les dates sont mises à jour comme suit : 4 x i t : date de début effective de l’opération Oi, 4 x i t ( )max ,fP i d r= 4i γ : date de fin effective de l’opération Oi, ( )4 max ,fP i ii d r δγ += 4 x j t : date de début effective de Oj, ( )44 max ,j i x j rt γ= 4 j γ : date de fin effective de Oj, ( )44 max ,j i jj r γ δγ += 4 x A t : date de début effective de la séquence A, 4 x A t = ( )4 max ,A j r γ 4 A γ : date de fin effective de la séquence A, 4 A γ = ( )4 max ,A j A r γ δ+ Le coût total relatif à cet ordonnancement est alors : ( ) ( ) ( )4 1 4 2 4 tot K S K S K S= + (7) 3.4 Application Considérons l’exemple suivant, tab.1 : • l’opération O1 est formée de trois composants 11c , 12c et 13c , O1 = { }11 12 13, ,c c c • l’opération O2 est formée de deux composants 21c et 22c , O2 ={ }21 22,c c • la séquence A est composée de deux opérations O3 et O4, telles que O3 = { }31c et O4 ={ }41 42,c c • 1i i α β= = Pour cet exemple, le coût des produits périmés est égal à : ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 3 3 1 1 1 3 3 2 2 4 4 2 2 4 4 3 1 1 22 2 4 1 1 3 max 0, max 0, max 0, max 0, x x k k x x k k x x k k x x k k rev k k rev rev k k k k rev k t v t v K S t v t v t v t v t v t v P P P P = = = = − − + − − − − + + − −                         ∑ ∑ ∑ et le coût du discount de distribution est égal à : ( )2 4 1 ( ) max 0, i i i i i i ven Pliv stk P P P P Pi P K S d C C DV DR= = − × + −       ∑ Tableau 1. Données relatives à l’exe mple étudié O1 O2 O4 O5 kr 1 2 4 4 kp 2 3 6 6 1iv 2 1 2 5 2iv 3 2 - 6 3iv 4 - - - 1 rev i P 2 3 4 3 2 rev i P 1 2 - 5 3 rev i P 1 - - - k ven P P 7 6 8 8 kP DV 16 13 12 12 kP DR 12 9 10 10 k liv P d 8 13 10 10 k stk P C 5 2 1 1 Pour cet exemple, six cas d’ordonnancements peuvent être distingués parmi lesquels certains sont à éliminés. A titre d’exemple, le cas de la séquence «P-A-O1-O2 » n’est pas réalisable compte tenu que ce cas ne respecte pas la contrainte que les deux séquences P et A ne doi- vent pas être successives. En effet, quatre séquences réalisables ont été retenues pour l’étude (tab.2). Ainsi, moyennant des règles de dominance des opéra- tions et des paramètres nécessaires pour le calcul des coûts et des données de stock, peut être évitée la pé- remption de certains composants et produits semi-finis Tableau 2. Calcul des coûts des ordonnancements réalisables Ordonnancements K1 K2 Ktot P O1 A O2 9 40.75 49.75 P O2 A O1 11 28 39 P O2 O1 A 9 48.25 57.25 P O1 O2 A 7 61.75 68.75 Les résultats obtenus montrent une grande disparité entre le coût minimum et le coût maximum, cette disparité est due principalement au coût du discount de distribution compte tenu de son importance. 4. CONCLUSION L’étude systématique des différents cas d’ordonnance- ments considérés pour deux séquences d’opérations déjà ordonnancées et de deux autres opérations, a permis de dégager la séquence présentant le coût cumulé des produits périmés et du discount de distribution minimal. L’exemple traité a montré l’importance du coût de discount de distribution relativement au coût des produits périmés dans la prise de décision finale concernant le choix de l’ordonnancement dont la fonction coût est minimale. Ainsi, cette décision peut éviter la péremption de certains composants et produits semi-finis. RÉFÉRENCES Allahverdi, A., F. S. Al-Anzi, 2005. A branch-and- bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times. European Journal of Operational Research Vol. 169, pp. 767-780. Barichard, V., 2003. Approches hybrides pour les pro- blèmes multiobjectifs. Thèse de Doctorat, Univer- sité d’Angers, Novembre. Baptiste, P., C. Le Pape, W. Nuijten, 2001. Constraint- based scheduling: applying constraints program- ming to scheduling problem. Edition Kluwer’s In- ternationnal Series ISBN 0-7923-7408-8. Baptiste, P., C. Le Pape, 1996. A constraint-Based Branch and Bound Algorithm for Preemptive Job- Shop Scheduling. Proceedings of the International Workshop on Production Planning and Control, Mons. Proceedings of the 5th IEE, International Symposium on Assembly and Task Planning, Be- sançon. Carlier, J., P. Chrétinne, 1988. Problèmes d’ordonn- ancement, modélisation, complexité, algorithmes, Edition Masson, Paris . Gargouri, E., 2003. Ordonnancement coopératif en in- dustrie agroalimentaire, Thèse de Doctorat, Uni- versité des Sciences et Technologies de Lille. Gargouri, E., S. Hammadi, 2003. A distributed schedul- ing for agro-food manufacturing problems, IEEE Transactions on Systems, Man, and Cybernetics- part C: applications and reviews, Vol. 33, No 2. Gargouri, E., S. Hammadi, P. Borne, 2002. Analyze of reactive schedule in agro-food chain. Acte de la 2ème Conférence Internationale JTEA Sousse, Vol. 2, pp. 312-319. Gargouri, E., S. Hammadi, P. Borne, 2001. New con- straints of agro-food industry scheduling prob- lem. Acte de IFDICOM’2001, Europeen Work- shop on Intelligent Forecasting, Diagnosis and Control Manufacturing, Santorin, pp. 73-80. Glover, F., 1990. Tabu search, part II, ORSA Journal on Computing, Vol.2, No 1, pp. 24-32. Gzara, M., 2001. Méthode coopérative d’aide multicri- tère à l’ordonnancement flou , Thèse de Doctorat, Université des Sciences et Technologies de Lille. Holland, J.H. 1975. Adaptation in natural and artificial systems, PhD, University of Michigan Press. Jouglet A., 2002. Ordonnancer une machine pour mi- nimiser la somme des coûts, Thèse de Doctorat, Université de Technologie de Compiègne. Kirkpatrick S., C.D Gelatt, M.P. Vecchi, 1983. Optimi- sation by simulated annealing. Science, 220, pp. 671-680. Le Pape, C., 1995. Three mechanisms for managing re- source constraints in the library for constraint- based scheduling. Proceeding of the INRIA/IEEE Conference on Emerging Technologies and Fac- tory Automation, Paris , pp 980-995. Mesghouni, K., 1995. Application des algorithmes évo- lutionnistes dans les problèmes d’optimisation en ordonnancement de la production. Thèse de Doc- torat, Université des Sciences et Technologies de Lille.