Minimizing a Regular Function on Uniform Machines with Ordered Completion Times

The scheduling problem we are dealing with is the following one. A set of n jobs has to be scheduled on a set of uniform machines. Each machine can handle at most one job at a time. Each job Jj, j = 1,..., n, has an arbitrary due date dj. Job Jj becomes available for processing at its release date rj and has to be scheduled by its deadline Dj. 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 with a given order of the completion times that minimizes a non-decreasing function F. Thus, we consider problem Q | rj, pmtn, Dj | F and want to find an optimal schedule among the schedules with a given order of completion times. We show that problem Q | rj, pmtn, Dj | F with a given order of completion times is equivalent to the problem of minimizing a function F subject to linear constraints