Introduction au calendrier des magasins de débit

L'horaire des magasins de débit est un problème fondamental dans la recherche opérationnelle et l'ingénierie industrielle qui consiste à séquencer un ensemble de tâches par une série de machines dans un ordre fixe. Chaque tâche doit visiter chaque machine exactement une fois, et l'ordre de traitement est identique pour tous les emplois. L'objectif est généralement de minimiser la makepan (temps total d'achèvement), le temps total de débit ou d'autres mesures de performance telles que la retard ou le temps de ralenti.

L'heuristique est un algorithme de résolution de problèmes qui sacrifie l'optimalité pour la vitesse. Ils utilisent les connaissances du domaine, les règles de pouce ou la recherche stochastique pour explorer efficacement l'espace de solution. L'heuristique de la programmation de magasin de flux a été étudiée de façon approfondie depuis les années 1950, avec des règles initiales comme l'algorithme de Johnson pour deux machines et des généralisations ultérieures.

Méthodes heuristiques communes

L'heuristique des magasins de flux se divise en deux grandes catégories : l'heuristique constructive, qui construit un calendrier à partir de zéro, et l'heuristique d'amélioration, qui part d'un calendrier réalisable et l'améliore itérativement.

Règles de répartition des priorités

Les règles de priorité sont les plus simples et constructives. Elles attribuent à chaque emploi une priorité fondée sur des attributs comme le temps de traitement, la date d'échéance ou l'heure d'arrivée, et les tâches de séquence par ordre de priorité.

  • Temps de traitement le plus court (SPT)[ : Les emplois avec le plus petit temps total de traitement sont programmés en premier. SPT minimise le temps de traitement moyen, mais peut augmenter makespan.
  • First Come First Serve (FCFS) : Les emplois sont traités par ordre d'arrivée.
  • Date d'échéance la plus rapprochée : Les emplois avec les dates d'échéance les plus rapprochées sont priorisés, souvent utilisés pour minimiser les retards.
  • Temps de traitement le plus long (LPT): Opposite de SPT, utilisé dans certains scénarios pour équilibrer la charge.

Les règles de priorité sont extrêmement rapides (O(n log n) complexes) et faciles à mettre en œuvre, ce qui les rend adaptés à l'horaire en temps réel.

Voisinage le plus proche (NEH)

L'heuristique NEH (Nawaz, Encore, & Ham) est l'une des méthodes constructives les plus efficaces pour la minimisation des surfaces de l'atelier de flux.

  1. Ordre initial[: Trier les emplois dans un ordre non croissant de temps total de traitement (somme sur toutes les machines).
  2. Insertion: Prenez le premier travail comme séquence initiale. Puis insérez chaque travail ultérieur dans la meilleure position (celui qui minimise makespan) dans la séquence partielle actuelle.

La force de NEH= est dans sa capacité à générer rapidement des solutions de haute qualité. Il est souvent utilisé comme point de référence et de départ pour l'heuristique d'amélioration. La complexité est O(m n3)[[m] machines et n emplois, mais il peut être accéléré à l'aide de structures de données.

Algorithmes génétiques (GA)

Les algorithmes génétiques sont des métaheuristiques basées sur la population inspirées par la sélection naturelle. Ils codent les horaires comme chromosomes (p. ex. permutation d'emplois) et les développent au fil des générations en utilisant les opérateurs:

  • Sélection : Choisissez des parents en fonction de la forme physique (p. ex., valeur makespan).
  • Crossover: Combiner deux séquences parentales pour produire des descendants. Pour les problèmes de permutation, les opérateurs comme les crossover partiellement cartographiés (PMX) ou les crossovers d'ordre (OX) préservent l'ordre relatif.
  • Mutation : Modifier aléatoirement un chromosome (p. ex., échanger deux emplois, déplacer un emploi vers une nouvelle position) pour maintenir la diversité.
  • Élitisme : Préserver les meilleurs individus pour éviter la perte de solutions de haute qualité.

Les GA explorent un large espace de solution et peuvent échapper à l'optima local. Ils sont flexibles et peuvent gérer des objectifs complexes (p. ex., des magasins de débit multi-objectifs). Cependant, ils nécessitent un réglage attentif des paramètres (taille de la population, taux de croisement, taux de mutation) et peuvent être calculables coûteux pour les grandes instances.

Annealing simulé (SA)

Dans le planning, SA commence par une solution initiale (souvent de NEH) et génère itérativement une solution voisine par de petites perturbations (p. ex., échange ou insertion). La nouvelle solution est toujours acceptée si elle améliore la masspan; autrement, elle peut être acceptée avec une probabilité qui dépend du paramètre de température et de l'ampleur de la détérioration. La température diminue au fil du temps selon un calendrier de refroidissement (p. ex., refroidissement géométrique: T = T0] * αk[.

SA's avantage clé est sa capacité à échapper à l'optima local, en particulier à des températures élevées. Il a été appliqué avec succès à de nombreux problèmes de magasin de débit. Performance est sensible au programme de refroidissement et au choix de l'opérateur de quartier.

Recherche Tabu (TS)

La recherche Tabu est une amélioration heuristique qui utilise des structures de mémoire (listes de tabu) pour éviter de revoir les solutions récemment explorées. A partir d'une solution initiale, TS explore le quartier et sélectionne la meilleure solution non-tabu (ou acceptable si elle répond à un critère d'aspiration). La liste de tabu enregistre les attributs des mouvements récents (par exemple, les emplois échangés) pour éviter les cycles.

TS offre un bon équilibre entre exploration et exploitation. Il produit souvent des solutions de haute qualité avec un temps de calcul modéré. Les variantes incluent la recherche réactive de tabu (ajuster dynamiquement la taille de la liste de tabu) et hybride TS avec d'autres heuristiques.

Autres méthodes heuristiques

Au-delà des classiques, plusieurs autres heuristiques ont été développées pour la planification des magasins de flux :

  • Ant Colony Optimization (ACO): Modélise le comportement de recherche de nourriture des fourmis. Les fourmis artificielles construisent des solutions en sélectionnant probabilistement les séquences de travail basées sur les pistes de phéromone et l'information heuristique (p. ex., le temps de traitement).
  • Particle Swarm Optimization (PSO): Utilise une population de particules qui se déplacent dans l'espace de la solution, ajustant leurs positions en fonction des meilleures positions personnelles et mondiales.
  • Itéréated Local Search (ILS)[: Applique une recherche locale (p. ex. descente la plus raide) à partir d'une solution de départ, puis perturbe l'optimum local pour générer un nouveau point de départ, répétant plusieurs fois.
  • Recherche de quartier variable (VNS)[: change systématiquement les structures de quartier pendant la recherche pour échapper à l'optima local.

Analyse comparative

Le choix d'une heuristique dépend de l'échelle de problème, des exigences de qualité de la solution et des ressources informatiques disponibles. Voici une comparaison sommaire basée sur des exemples de référence standard (p. ex., les ensembles de tests de Taillard pour la planification des magasins de flux).

Qualité de la solution

Les règles de priorité et l'heuristique simple et constructive permettent généralement d'atteindre des écarts de 10 à 20% par rapport à la solution optimale ou la meilleure connue. NEH effectue beaucoup mieux, souvent à moins de 3 à 5% de l'optimum. Métaheuristique (GA, SA, TS) peut atteindre des écarts de 0 à 1% en fonction de l'autonomie. Parmi les métaheuristiques, TS et les GA hybrides ont tendance à être plus cohérents entre les différentes tailles de problèmes, tandis que SA peut avoir besoin d'un réglage attentif pour correspondre à leur performance.

Temps de calcul

Les règles de priorité sont les plus rapides (millisecondes pour des centaines d'emplois). NEH est légèrement plus lent mais encore pratique (secondes pour des cas modérés). La métaheuristique varie considérablement : un GA typique de 100 et 1000 générations peut fonctionner pendant des minutes pour de grands cas (p. ex. 100 emplois, 20 machines), tandis que le SA avec un calendrier de refroidissement lent peut être aussi rapide. TS est généralement plus rapide que la peritération GA mais peut nécessiter de nombreuses itérations.

Robusteté

La robustesse fait référence à la cohérence de la qualité de la solution dans différentes instances problématiques. NEH est très robuste pour la minimisation masspan. GA et SA peuvent être sensibles aux paramètres ; GA mal aligné peut converger prématurément ou ne pas explorer. TS=s performance est moins sensible aux paramètres que SA, bien que tabu taille de liste importe. Héuristique hybride qui combine constructive (NEH) avec amélioration (TS ou SA) tend à être le plus robuste.

Mesure des performances

Pour évaluer l'heuristique, plusieurs mesures sont utilisées :

  • Makespan (Cmax)[: Temps total entre le début du premier emploi et la fin du dernier emploi sur la dernière machine. C'est l'objectif le plus commun.
  • Délai de débit total[: Somme des temps d'achèvement de tous les emplois.
  • Tardiness maximales: Délai le plus défavorable par rapport aux dates d'échéance, souvent utilisé dans des environnements orientés vers le client.
  • Nombre d'emplois de Tardy : Nombre d'emplois qui finissent après leur date d'échéance.
  • Heure de la poche: Temps total de ralenti de la machine; la minimisation augmente l'utilisation de la machine.

L'heurerie peut être spécialisée pour chaque métrique. Par exemple, l'heurerie NEH est conçue pour makespan, tandis que l'EDD et d'autres règles basées sur la date due ciblent le retard. L'optimisation multi-objectifs (par exemple, Pareto front) est un domaine de recherche actif.

Approches hybrides et avancées récentes

Aucune heuristique ne domine toutes les instances problématiques. Les méthodes hybrides combinent plusieurs techniques pour tirer parti de leurs forces respectives.

  • NEH + Recherche locale : Utilisez NEH pour générer une bonne solution initiale, puis appliquez simulation de recuit ou tabu recherche d'amélioration.
  • Algorithme génétique + Recherche locale (Algorithme mémétique): Appliquer la recherche locale à chaque descendance avant son insertion dans la population, en assurant une bonne convergence.
  • Contrôle des paramètres adaptatifs: Régler les paramètres GA ou SA pendant l'exécution en fonction du comportement de recherche (p. ex., réannage de température, taux de mutation adaptatifs).
  • Intégration de l'apprentissage en machine[: Former des modèles de régression ou renforcer les agents d'apprentissage pour prédire de bons mouvements ou sélectionner l'heuristique dynamique.

Des recherches récentes explorent également l'informatique en nuage et parallèle[ pour accélérer la métaheuristique de la population, et l'hyperheuristique[ qui choisissent à chaque étape parmi les heuristiques de bas niveau. Le domaine continue d'évoluer, avec de nouveaux repères et des variantes de problèmes (p. ex., atelier de flux sans attente, atelier de flux hybride, atelier de flux flexible).

Choisir la bonne heuristique

La sélection d'une heuristique pour l'horaire des magasins de flux dépend de plusieurs facteurs pratiques:

  • La taille et la complexité des problèmes: Pour les petites et moyennes instances (10 à 50 emplois, jusqu'à 20 machines), des méthodes exactes peuvent être possibles, mais sinon, NEH ou un simple métaheuriste comme TS fonctionne bien.
  • Exigences de qualité de la solution: Si des solutions quasi optimales sont obligatoires (p. ex. dans la fabrication à haut débit), un GA ou un TS hybride à plus long terme est justifié. Si les horaires difficiles suffisent, SPT ou NEH gagneront du temps.
  • Ressources informatiques disponibles: Le cloud computing ou les postes de travail puissants permettent l'utilisation de méthodes plus intensives en calcul comme l'AG avec de grandes populations.
  • effort de mise en œuvre[: Les règles de priorité et NEH sont insignifiantes à coder. SA et TS nécessitent un effort modéré; GA est plus complexe mais bien documenté. ACO et PSO exigent des choix de conception supplémentaires pour les problèmes discrets.
  • Environnements dynamiques: Certains systèmes de production font face à de nouveaux emplois arrivant au fil du temps (planification en ligne).

Il est fortement recommandé de comparer les résultats obtenus avec les exemples représentatifs.De nombreux chercheurs utilisent les Taillard flowshop benchmark[ ou ]]]][F][F][

Conclusion

Les méthodes heuristiques offrent un pont pratique entre la faisabilité de calcul et la qualité de la solution. Bien que les règles de priorité simples et l'heuristique NEH fournissent des solutions rapides et acceptables pour de nombreux scénarios, les métaheuristiques comme les algorithmes génétiques, le recuit simulé et la recherche tabu donnent des résultats presque optimaux au prix d'un calcul plus important. Les approches hybrides qui combinent les forces de plusieurs méthodes sont particulièrement efficaces et constituent un domaine de recherche actif.

Les praticiens devraient tenir compte des objectifs spécifiques, de la taille du problème et du budget de calcul lors de la sélection d'une heuristique. Les progrès continus dans la conception métaheuristique, l'intégration de l'apprentissage machine et l'informatique parallèle continuent de repousser les limites de ce qui est réalisable, rendant l'établissement de calendriers de flux un domaine dynamique pour l'étude théorique et l'application pratique.

Pour plus de détails, voir l'enquête approfondie réalisée par Framinan et al. (2015)[ sur l'heuristique de l'horaire des magasins de débit, et le texte classique réalisé par Pinedo (2016) sur la théorie et les algorithmes de l'horaire.