Approches heuristiques pour la planification d'un flux de deux machines avec délai d'externalisation

Cet article étudie un problème de planification d'un flux de deux machines, en tenant compte du délai d'externalisation, où l'externalisation d'une tâche entraîne un coût d'externalisation ainsi qu'un délai d'externalisation. Chaque tâche a la possibilité d'être externalisée, c'est-à-dire que la première opération de la tâche externalisée est gérée par un sous-traitant externe tandis que la deuxième opération doit être traitée en interne après sa livraison. L'objectif est de trouver un emploi du temps minimisant la somme pondérée des coûts d'externalisation et le temps total d'achèvement. Pour le problème, le sous-ensemble de tâches à externaliser et l'ordre de traitement des tâches sont entrelacés, ce qui implique que les décisions doivent être prises simultanément. Cette étude examine les propriétés de la solution optimale et propose diverses heuristiques basées sur une recherche locale itérative et l'algorithme génétique à clés aléatoires biaisées. D'importantes expériences computationnelles sont réalisées dans divers contextes.