i am looking for literature on this kind of problem. \begin{align} \min_x \max_k &\quad \sum_{i,j} x_{ij}c_{ijk}\\ \text{subject to}&\\ &\sum_j x_{ij}=1,&& \forall i\in\mathcal J\\ &x_{ij}\in\{0,1\},&& \forall i\in\mathcal J, j\in\mathcal M \end{align}

• $\mathcal J$ is a set of Jobs and $\mathcal M$ is a set of Machines.
• $c_{ij}$ is a vector and describes the cost of the job $i$ on the machine $j$. So the cost has multiple dimension.

The Aim of the programm is to find a schedule so that each job is scheduled on a machine and the biggest dimension of the add up cost vector is minimized.

The problem is described here:

http://arxiv.org/pdf/1211.5729v2.pdf (Page 2 left column bottom) as Generalized load balancing

and here:

EDIT

load balancing can be generalized in several ways, i.e. restrict that each job can only run on a specific set of machines. This is also a generalization of the scheduling problem.

I'm interested in the case where the scheduling is restricted and multidimensional. I'm looking for more literature for this problem.

Thank you

• When $k=1$ this is just the classical assignment problem (which can be solved optimally in poly time). This is essentially asking to find a single solution to the assignment problem which has low cost for all $k$ instances simultaneously. Jun 26 '14 at 18:32
• One can get an $O(\log k/\log \log k)$-approximation for this problem. Look at a recent Arxiv paper below and references in that paper. arxiv.org/pdf/1406.5943v1.pdf Jun 26 '14 at 19:23

• @SashoNikolov The objective function is basically a makespan constraint over $k$ dimensions. This is related to vector scheduling where each job has $k$ dimensions. Jun 26 '14 at 20:34
• @ChandraChekuri I disagree (or I may be missing something). What I would call a makespan problem would have the constraint $\forall j: \max_{k} \sum_i{x_{ij}c_{ijk}} \leq T$ and the objective would be to minimize $T$. Right now there are no constraints on machines, and the minimization is for the total cost. Jun 26 '14 at 22:27
• @ChandraChekuri I was wrong in my previous comment (now deleted). I think the problem makes sense actually, and I can see that it generalizes scheduling on unrelated machines. But this is if you think of the third dimensions as the machines, and $c_{ijk}$ is nonzero only for $k=j$. So this problem minimizes the maximum load per resource ("makespan over resources"), even though it sums each resource over machines. To OP: you can also check Chapter 11.1 of the Williamson-Shmoys book, and also 16.1. for a hardness reduction designofapproxalgs.com/book.pdf Jun 27 '14 at 3:25