Minimizing total tardiness on parallel machines with preemptions

What is it about?

A set of jobs has to be scheduled on a set of parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing at its release date. All jobs have the same execution requirement and arbitrary due dates. Each machine has a known speed. The processing of any job may be interrupted arbitrarily often and resumed later on any machine. The goal is to find a schedule that minimizes the sum of tardiness whose complexity status was open. We show that both the problem of minimizing total tardiness on a set of parallel machines with allowed preemptions and the problem of minimizing total tardiness on a set of parallel machines with release dates, equal processing times and allowed preemptions are NP-hard. Moreover, we give a polynomial algorithm for the case of uniform machines without release dates.

Featured Image