Dans la fabrication, les processus de production nécessitent souvent l’utilisation de deux machines ou plus pour effectuer les tâches de production. Le temps par travail sur chaque machine varie généralement. Makespan est le temps total nécessaire pour terminer tous les travaux. Calculer makespan signifie trouver la séquence de travaux qui minimisera le temps requis.
Makespan pour deux machines
Pour déterminer la durée de fabrication minimale pour un ensemble de tâches nécessitant deux machines, commencez par trier les temps de travail en deux listes. La première liste comprend les heures de la machine 1 et la seconde liste les durées des travaux de la machine 2. Parcourez les deux listes et recherchez la durée la plus courte dans l'une ou l'autre liste. Si le temps le plus court est celui de la liste un, planifiez d'abord ce travail et supprimez-le des deux listes. Si le temps le plus court provient de la deuxième liste, planifiez-la en dernier. Encore une fois, supprimez le travail des deux listes. Répétez ce processus de tri jusqu'à ce que chaque travail soit planifié. La séquence de tâches produite a le minimum de temps requis.
Trois machines ou plus
Lorsque trois machines ou plus sont nécessaires, les séquences possibles se développent en fonction d’une progression mathématique rapide. Il devient rapidement impossible de faire le tri manuellement ou même avec un ordinateur. Les fabricants optent pour un makespan raisonnablement efficace, plutôt que optimal. Une façon de procéder consiste à diviser les tâches et les machines en groupes assez petits pour calculer la durée de production de chaque groupe.
