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

**Series:** 2010-25, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic
- 90C05 Linear programming

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