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

**Series:** 2009-22, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic
- 68Q25 Analysis of algorithms and problem complexity
- 90C05 Linear programming

**Abstract:**

The basic scheduling problem we are dealing with in this paper is the following one. A set of jobs has to be scheduled on a set of parallel uniform machines. Each machine can handle at most one job at a time. All jobs have the same execution requirement. 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 that minimizes

\sum f_j, where

f_j are convex non-decreasing functions such that f_i-f_j are all monotonic functions.

Thus, we consider problem Q | p_j=p, pmtn | \sum f_j.

We show that problem $Q | p_j=p, pmtn | \sum f_j is equivalent to the problem

of minimizing a convex-separable function under linear constraints.

We use this representation to solve problems Q | p_j=p, pmtn | \sum T_j

and Q | p_j=p, pmtn | \sum w_j C_j in polynomial time.

Note that both problems Q | p_j=p, pmtn | \sum w_j C_j and

Q | p_j=p, pmtn | \sum T_j had an open complexity status.

Recently, Tian et al. proposed a polynomial algorithm for problem 1 | r_j, p_j=p, pmtn | \sum T_j.

We show that both the problem P | pmtn \sum T_j

of minimizing total tardiness on a set of parallel machines with allowed preemptions and the problem

P | r_j, p_j=p, pmtn | \sum T_j

of minimizing total tardiness on a set of parallel machines with release dates, equal processing times and allowed preemptions are NP-hard.

**Keywords:**

Scheduling; Parallel uniform machines, Linear programming, Polynomial algorithm, NP-hardness