Дерево решений с отсечением — ИМХО пушкой по воробьям по этой задаче. Эта задача абсолютно не будет ИМХО NP-полной.
Интуиция подсказывает, что для выполнения условия минимальности в любое время выполнения предыдущего задания (в частности в нач. момент, если есть >=2 задания с T_i=0) на конвеер просто надо ставить следующую задачу с наибольшим временем выполнения. Алгоритм также не зависит от кол-ва доступных процессоров.