Planification semi-en ligne sur deux machines parallèles uniformes avec anticipation initiale

Ce travail étudie le problème de la planification semi-en ligne sur deux machines parallèles uniformes avec des vitesses 1 et s (≥2), respectivement. Nous introduisons un nouveau concept d'anticipation initiale dans lequel tout algorithme en ligne déterministe a une connaissance complète des k premiers travaux au début, tandis que les travaux restants sont libérés un par un en mode de sur-liste en ligne. L'objectif du problème considéré est de minimiser le makespan. Nous nous concentrons sur le cas où les k premiers travaux ont un temps de traitement total d'au moins (s + 1)Δ où Δ est la plus longue tâche, et il est supposé que s est un entier. Nous prouvons une borne inférieure de (s² + s + 1)/(s² + s), et proposons un algorithme semi-en ligne déterministe avec un ratio compétitif de (s + 1)² / (s² + s + 1). Ce ratio est au maximum de 9/7 et beaucoup moins que celui de 1,618 pour le cas correspondant sans anticipation initiale (Cho et Sahni, SIAM J. Comput. 9 (1980) 91–103). Nos résultats démontrent qu'une capacité finie d'anticipation initiale peut considérablement améliorer la compétitivité des algorithmes en ligne.