10-25
Minimizing a Regular Function on Uniform Machines with Ordered Completion Times
Preprint series: 10-25 , Preprints
Abstract: 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 $J_j, j = 1, \ldots, n$, has an arbitrary due date $d_j$. Job $J_j$ becomes available for processing at its release date $r_j$ and has to be scheduled by its deadline $D_j$. 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\mid r_j, \mbox{ pmtn}, D_j\mid F$ and want to find an optimal schedule among the schedules with a given order of completion times.
We show that problem $Q\mid r_j, \mbox{ pmtn}, D_j\mid F$ with a given order of completion times is equivalent to the problem of minimizing a function $F$ subject to linear constraints.
Keywords: Uniform machines, Linear programming
Upload: 2010-10-25
The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.