# Otto-von-Guericke-Universität Magdeburg

### 09-22

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

Preprint series: 09-22, Preprints

MSC:
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

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 10.02.2016 - Ansprechpartner: Pierre Krenzlin