Preemptive scheduling on uniform machines to minimize mean flow time

What is it about?

A set of jobs has to be scheduled on parallel uniform machines. Each job becomes available for processing at its release date. All jobs have the same execution requirement, and each machine has a known speed. The processing of any job may be interrupted arbitrarily often and resumed later on any machine. We determine a schedule that minimizes the sum of completion times, in polynomial time. The algorithm is based on a reduction of the scheduling problem to a linear program. The crucial condition for implementing the proposed reduction is the known order of job completion times.

Featured Image

Why is it important?

This paper settled the open complexity status of a scheduling problem with uniform parallel machines.