Planification de tâches avec des délais non uniformes sur deux processeurs

Étant donné un ensemble @@@@ = T 1, T 2, ···, T n de tâches, chaque T i ayant un temps d'exécution de 1 et une date limite d i > 0, ainsi qu'un ensemble de contraintes de précédence qui restreignent les plannings autorisés, le problème de déterminer s'il existe un planning utilisant deux processeurs dans lequel chaque tâche est terminée avant sa date limite est examiné. Un algorithme efficace pour trouver un tel planning, chaque fois qu'il existe, est proposé. L'algorithme peut également être utilisé pour trouver le plus court de ces plannings. De plus, il est montré que le problème de trouver un planning à un processeur qui minimise le nombre de tâches ne respectant pas leurs délais est NP-complet et, par conséquent, est susceptible d'être computationnellement intraitable.