Full Program »

# Exact Algorithms for Scheduling Programs with Shared Tasks

We study a scheduling problem where the jobs we have to perform are composed of one or more tasks. If two jobs sharing a non-empty subset of tasks are scheduled on the same machine, then these shared tasks have to be performed only once. This kind of problem is known in the literature under the names of \textsc{VM-PACKING} or \textsc{PAGINATION}. Our objective is to schedule a set of these objects on two parallel identical machines, with the aim of minimizing the makespan. This problem is NP-Complete as an extension of the \textsc{PARTITION} problem. In this paper we present two exact algorithms with worst-case time-complexity guarantees, by exploring different branching techniques. Our first algorithm focuses on the relation between jobs sharing one or more symbols in common, and it has a time-complexity of $\mathcal{O}(2^{n - \frac{T}{2}})$, with $n$ being the number of jobs, and $T$ being the number of connected components present in the graph representation associated to our input data. By examining the possible assignments of the shared symbols, we can present a way to solve our problem in $\mathcal{O}(2^{\frac{n}{2}}7^{\frac{c}{2}})$ steps, with $c$ being the number of shared symbols in our input data. A more elaborated analysis of this way of branching allows us to present a better $\mathcal{O}(2^{\frac{n}{2}}\frac{3}{2}^c)$ algorithm.

Imed Kacem
Laboratoire LCOMS, Université de Lorraine
France

Giorgio Lucarelli
Laboratoire LCOMS, Université de Lorraine
France

Théo Nazé
Laboratoire LCOMS, Université de Lorraine
France