### 2009-22

#### Minimizing a Separable Convex Function on Parallel Machines with Preemptions

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