Schémas d'approximation pour la planification des tâches sur des machines parallèles identiques afin de minimiser la lateness maximale et le makespan

Nous considérons un problème de planification multiobjectif, visant à minimiser la lateness maximale et le makespan sur des machines identiques, lorsque le nombre de machines est fixe. Cet article propose un algorithme exact (basé sur la programmation dynamique) pour générer la frontière de Pareto complète en temps pseudo-polynomial. De plus, quatre heuristiques ont été proposées afin d'optimiser notre algorithme. Ensuite, nous présentons un schéma d'approximation en temps polynomial (PTAS) pour générer une frontière de Pareto approximative. Dans ce schéma, nous utilisons une technique de simplification basée sur la fusion des tâches. En outre, nous présentons un schéma d'approximation en temps complètement polynomial (FPTAS) pour générer une frontière de Pareto approximative, basé sur la conversion de l'algorithme de programmation dynamique. Le FPTAS proposé est fortement polynomial. Enfin, quelques expériences numériques sont fournies afin de comparer les approches proposées.