Optimal preemptive scheduling on uniform machines with discounted flowtime objectives

Abstract

We consider the problem of scheduling n jobs on m parallel machines. Each job has a deterministic processing time and a weight associated with it. For uniform machines we show that discounted flowtime is minimized by serving jobs preemptively in increasing order of their remaining processing times, assigning the job with the shortest remaining processing time to the fastest available machine. (c) 2006 Published by Elsevier B.V.