Zurück zu den Preprints des Jahres 2010


Minimizing a Regular Function on Uniform Machines with Ordered Completion Times

by Kravchenko, S.A., Werner, F..

Series: 2010-25, Preprints

90B35 Scheduling theory, deterministic
90C05 Linear programming

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
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.

Uniform machines, Linear programming