Assignment problem where assignments must be done sequentially

Question

I have a weird planning problem. I think it falls under the assignment category, but I'm not sure because I'm not familiar with assignment problems, and also because there is a "temporal" angle to it, which maybe makes it a bit different from classical assignment problems.

We have $k$ workers $\{W_1,\dots,W_k\}$ ($k=2$ currently, but it could change in the future), and a sequence of tasks of different value $L=[v_1,\dots,v_n \mid v_i\in Z^{\neq}]$ such that $V=\sum_iv_i$. I want to assign tasks to each worker in such a way that $\sum v_{iW_1}=0.3V$ and $\sum v_{iW_2}=0.7V$, i.e., minimizing the cost

$$L=\left(\sum v_{iW_2}-0.7V\right)^2$$

However, the tasks are assigned in order (i.e., task $v_i$ is assigned before task $v_{i+1}$) and for some reason, the number of "switches" $m$ is to be minimized. With switch, I mean the action of assigning task $v_{i+1}$ to a different worker than the one to which I assigned task $v_i$. Obviously $m\geq1$. The overall number of switches should be minimized, and a "batched assignment" solution would be preferred: say, assign at least 3 consecutive tasks to the same worker.

I understand the problem is underspecified: the internal customer I'm doing this for, doesn't really know what they want. For example, rather than saying "don't switch too often", they should actually quantify the cost of switching from a worker to another.

Even then, I think there should be a way to find a solution which is "optimal" in some sense, like for example minimizing both the cost and the number of switches:

$$L'=\left(\sum v_{iW_2}-0.7V\right)^2+cm^2,\ c>0$$

Answer 1

You can model this with a binary variable $x_{i,j}$ to indicate whether task $i$ is assigned to worker $j$, and a binary variable $y_{i,j}$ to indicate whether task $i$ is the first task assigned to worker $j$ in the current batch. The number of switches is then $\sum_{i\ge 2} \sum_j y_{i,j}$ because this sum counts the number of times that any worker starts a new batch of tasks (except the first batch that contains task $i=1$). The constraints are: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ x_{1,j} &= y_{1,j} &&\text{for all $j$} \\ x_{i,j} - x_{i-1,j} &\le y_{i,j} &&\text{for $i\ge 2$ and all $j$} \\ y_{i,j} &\le x_{i+k,j} &&\text{for $k\in\{0,1,2\}$}\\ \end{align} The first constraint assigns each task to exactly one worker. The second constraint forces task 1 to start a new batch. The third constraint enforces the logical implication that, if task $i$ is assigned to worker $j$ and task $i-1$ is assigned to a different worker, then task $i$ starts a new batch for worker $j$; that is, $(x_{i,j}=1 \land x_{i-1,j}=0) \implies y_{i,j}=1$. The fourth constraint enforces the logical implication that, if task $i$ start a new batch for worker $j$, then tasks $i$ through $i+2$ (3 consecutive tasks) must be assigned to worker $j$; that is, $y_{i,j}=1 \implies x_{i+k,j}=1$.

You specified a quadratic objective, so you could use an MIQP solver. Or you could change the objective to $$\left|\sum_i v_i x_{i,2} - 0.7V\right| + c \cdot m,$$ linearize the absolute value and use an MILP solver.

Answer 2

When you have two objective functions, and your client can't articulate exactly how the two are to be weighed against one another, sometimes the easiest solution is to avoid making that decision. Instead of trying to figure out the client's priorities and find the single best solution, you can present them with a small list of options guaranteed to contain the best solution, and then let them choose from that list.

A solution is called "nondominated" or "Pareto efficient" if there's no way to improve one objective without worsening another. The Pareto front is the set of all nondominated solutions. It follows that no matter how heavily your client weights cost vs. switches, or vice versa, their best solution will lie somewhere in the Pareto front.

Here's one way to calculate the solutions on that front. Letting $x$ and $y$ stand for the two objective functions:

1. Solve the problem, optimising only for $x$, and record this solution $S_0$. Let the resulting objective values be $x_0$ and $y_0$.
2. Solve the problem again, adding a constraint that $y<y_0$. Record the solution $S_1$ and OF values $x_1, y_1$.
3. Solve again, with the constraint that $y<y_1$...
4. Keep going until the problem becomes infeasible.

You will now have a set of solutions where $x$ decreases as $y$ increases. Any solution outside this set will be worse than some solution within it.

(Strictly speaking, this set might contain a few non-Pareto-efficient ones too, e.g. if the first one gives $x=100, y=200$, the second one could have $x=100, y=199$, in which case the first solution is dominated by the second and could be discarded. So if you want to be really rigorous, you should go back through the results and cull any of those dominated solutions. Alternately, instead of optimising on $x$, you could optimise on something like $x+0.00001*y$ to avoid these "almost-Pareto-efficient" solutions.)

If you like, you can then plot the x- and y-values for each solution and let your client pick off the chart. It's often much easier for people to choose between options than to explain their general rule for choosing.

If you're feeling bold you can then use their preferred solutions to deduce how much priority they put on each of the two objective functions, and use that to construct a single OF to use next time around.