2
$\begingroup$

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:

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A8FEB960E21CA0361066CD5200C02718?doi=10.1.1.380.8241&rep=rep1&type=pdf (Page 4 left column) as generalized AP association problem

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Jun 26, 2014 at 18:32
  • $\begingroup$ 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 $\endgroup$
    – Chandra Chekuri
    Commented Jun 26, 2014 at 19:23

1 Answer 1

Reset to default
1
$\begingroup$

Appreciable literature is available in this standard book on Approximation Algo by Vazirani http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf

Refer to chapter 10 for details.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I don't think this problem has that much of a connection to makespan. Here there is no constraint at all on the load to machines. $\endgroup$
    – Sasho Nikolov
    Commented Jun 26, 2014 at 18:31
  • $\begingroup$ @SashoNikolov The objective function is basically a makespan constraint over $k$ dimensions. This is related to vector scheduling where each job has $k$ dimensions. $\endgroup$
    – Chandra Chekuri
    Commented Jun 26, 2014 at 20:34
  • $\begingroup$ @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. $\endgroup$
    – Sasho Nikolov
    Commented Jun 26, 2014 at 22:27
  • $\begingroup$ @SashoNikolov the question is ill phrased I think. I looked at the refs and figured it was the multidimensional/vector scheduling problem. $\endgroup$
    – Chandra Chekuri
    Commented Jun 27, 2014 at 1:47
  • $\begingroup$ @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 $\endgroup$
    – Sasho Nikolov
    Commented Jun 27, 2014 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.