Здесь должен работать стандартный недетерминированный подход («угадай, потом проверь»): угадай, как должны быть запланированы задания, а затем проверь, что это расписание соответствует пределу штрафа (что, очевидно, возможно за полиномиальное время).
Как правило, показать, что проблема в NP, относительно легко - более сложная часть показывает, что она также является NP-полной (но в этом случае вам не нужно делатьтот).