4
$\begingroup$

I am studying an assignment problem with batching costs, and I would like to know if there is a standard name or algorithm for this problem. I know this problem can be formulated as mixed-integer programming and be solved using the solvers, but I am looking for algorithms that are faster than the standard MILP methods. Both exact and approximated algorithms are appreciated, and polynomial-time methods are expected if exist.

The problem is: We have $i$ jobs that can be assigned to $j$ workers, $j>i$. Each job $i$ has a cost when assigned to worker $j$, namely, $w_{ij}$. Each worker $j$ can work with one or two job(s). When worker $j$ only works with one job, there is no additional cost. However, if worker $j$ works with two jobs, there is an additional cost. This additional cost can be regarded as a batching cost as it only exists when two jobs are assigned to the same worker. The additional cost for worker $j$ with job $i_1$ and $i_2$ is $c_{i_1i_2j}$, and it can be arbitrarily positive or negative. In this case, the total cost for worker $j$ with job $i_1$ and $i_2$ is $w_{i_1j}+w_{i_2j}+c_{i_1i_2j}$. Our objective is to assign all the jobs with a minimum total cost.

$\endgroup$
13
  • $\begingroup$ Welcome to OR.SE. Are you sure that $j \ge i$? If so, you can assign all jobs to all workers without any additional cost? $\endgroup$ – A.Omidi Apr 5 at 13:13
  • $\begingroup$ @A.Omidi Thx for the reply. We surely can assign all jobs without any additional cost, but the costs $w_{ij}$ are different for $i$ and $j$. If we assign all jobs without any additional cost, we might not have a minimum total cost. $\endgroup$ – Luo ArChen Apr 5 at 13:19
  • $\begingroup$ Is there any way to convert these different costs $w_(i,j)$ to their corresponding time? If so, one possible way would be formulating the problem as a varient of the parallel machine scheduling with sequence depending setup time to minimize sum of the completion time which the converted $w_(i,j)$ can be interpreted as the setup time. $\endgroup$ – A.Omidi Apr 5 at 14:13
  • $\begingroup$ @A.Omidi This is a good idea. Unfortunenately, our costs include more than one factors(time, quality, etc.), so it cannot be converted in this way. $\endgroup$ – Luo ArChen Apr 5 at 14:26
  • $\begingroup$ What's the order of magnitude of $i$ and $j$? Have you already tried the MILP implementation? How long does it take to solve your problem with a MILP solver or to find a good enough solution? What computation time would you expect? $\endgroup$ – fontanf Apr 5 at 15:25
5
$\begingroup$

You can formulate this as an instance of the quadratic assignment problem by duplicating the workers and incurring the batching cost only for pairs of duplicate workers.


Here's an alternative MIQP formulation that does not double the number of workers. Let binary decision variable $x_{i,j}$ indicate whether job $i$ is assigned to worker $j$. The problem is to minimize $$\sum_{i,j} w_{i,j} x_{i,j} + \sum_{i_1<i_2} \sum_j c_{i_1,i_2,j} x_{i_1,j} x_{i_2,j} \tag1$$ subject to \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$} \tag2\\ \sum_i x_{i,j} &\le 2 &&\text{for all $j$} \tag3\\ \end{align} You can use an MIQP solver directly or linearize.

The most straightforward linearization is to introduce a new binary (optionally nonnegative) decision variable $y_{i_1,i_2,j}$ to represent the product $x_{i_1,j} x_{i_2,j}$ and then minimize $$\sum_{i,j} w_{i,j} x_{i,j} + \sum_{i_1<i_2} \sum_j c_{i_1,i_2,j} y_{i_1,i_2,j} \tag4$$ subject to $(2)$, $(3)$, and \begin{align} y_{i_1,i_2,j} &\le x_{i_1,j} &&\text{for all $i_1<i_2$ and $j$} \tag5\\ y_{i_1,i_2,j} &\le x_{i_2,j} &&\text{for all $i_1<i_2$ and $j$} \tag6\\ y_{i_1,i_2,j} &\ge x_{i_1,j} + x_{i_2,j} - 1 &&\text{for all $i_1<i_2$ and $j$} \tag7\\ \end{align}

You can strengthen this formulation by replacing $(5)$ and $(6)$ with the valid inequality \begin{align} \sum_{i < i_2} y_{i,i_2,j} + \sum_{i > i_2} y_{i_2,i,j} &\le x_{i_2,j} &&\text{for all $i_2$ and $j$} \tag8\\ \end{align} Note that $(8)$ is obtained via RLT by multiplying both sides of $(3)$ by $x_{i_2,j}$.

I would be interested to hear how your MILP compares with:

  • MIQP: minimize $(1)$ subject to $(2)$ and $(3)$.
  • MILP: minimize $(4)$ subject to $(2)$, $(3)$, $(7)$, and $(8)$.
$\endgroup$
6
  • $\begingroup$ Thx. As far as I know, the QAP is proven to be NP-hard, and solving it seem to be too time-consuming for my applications. Any fast algorithm for QAP recommend? $\endgroup$ – Luo ArChen Apr 5 at 13:53
  • 1
    $\begingroup$ @LuoArChen LocalSolver is efficient in solving QAP problems in practice: localsolver.com/benchmarkqap.html. LocalSolver is commercial software. If you're just interested in good-quality solutions, then a local-search heuristic based on k-exchange will be ok. If your instances are large (thousands of jobs and workers), then incremental evaluation of the exchanges will be a must to hope high-quality solutions in minutes. $\endgroup$ – LocalSolver Apr 5 at 15:23
  • $\begingroup$ Also, this is a special case where the quadratic part is quite sparse, so you should expect better performance than the worst case. $\endgroup$ – RobPratt Apr 5 at 16:12
  • $\begingroup$ @LocalSolver Thx for providing your solution. Can you refer some good reference for the local-search heuristic based on k-exchange? $\endgroup$ – Luo ArChen Apr 6 at 7:14
  • $\begingroup$ @LuoArChen By searching "QAP local search" on the web, you will find many references. For example, have a look at neighborhoods described in archive.alvb.in/msc/04_infoea/seminar/papers/…. The so-called 2-exchange is conceptually simple. Given an assignment of jobs to workers, swap the jobs of 2 workers. Evaluate the new assignment; if better, take it, otherwise leave it. Then, you can generalize to k-exchange. The evaluation of the new assignment can be done incrementally, then allowing to get fast convergence. $\endgroup$ – LocalSolver Apr 6 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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