09-22
Minimizing a Separable Convex Function on Parallel Machines with Preemptions
by Kravchenko, S.A.; Werner, F.
Preprint series: 09-22, Preprints
- MSC:
- 90B35 Scheduling theory, See also {68M20}
- 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.