# Maximize assigned tasks to each worker

In a scheduling problem I want to assign the maximum number of tasks to one worker before assigning it to another. For example, if I have $$10$$ tasks and $$2$$ workers, the best assignment would be $$(10, 0)$$ and the worst $$(5, 5)$$.

I have tried the following ideas:

1. Iterative approach: assign tasks to each worker one by one with the objective of maximizing the number of assigned tasks. Didn't really work because there are constraints and objectives that take into account the other workers.

2. Maximize the sum of squares: $$\sum(\text{number of tasks}^2)$$, this way $$(10, 0)$$ has a score of $$100$$ and $$(5, 5)$$ a score of $$50$$.

I am going by the second approach but the solving speed drops quite a bit, not sure if it is because the problem is much more complex, or because it becomes quadratic.

Is there a better way to model this objective? Maybe something in terms of distance?

PS: The logic of my current OR-Tools code is something along the lines of this:

for w in workers:
)
squared_count[w] = model.NewIntVar(
)
)
)
squared_count[w],
)

• Are your workers identical (meaning assigning any given task to worker 1 has the same impact throughout the constraints as would assigning that task to worker 2)? Sep 25 '19 at 20:40
• Yes, they are identical. Would that simplify the problem? Sep 26 '19 at 9:31
• Yes, in that there is no concern for whether shifting load from one worker to another adversely effects cost or productivity. Sep 28 '19 at 17:49

just use a larger (linear) weight for tasks assigned to worker 1.

• Yes. It has some limitation, you do not have that large range of weights. It is always better than quadratic anyway. Sep 23 '19 at 19:27
• Thanks! A small follow up question, generally speaking, given 2 intvars $x$ and $y$ how can I maximize either one of them while minimizing the other? I was also making it quadratic by $min(x∗y)$... Could $max((big*x+bigger*y)+(bigger*x+big*y))$ also work? Sep 24 '19 at 0:21
• @Stradivari It depends on the actual problem but you could maximize x-y in order to maximize x while minimising y. Only works as is for two variables though.
– Holt
Sep 24 '19 at 6:54
• You can maximize the absolute value of their difference Sep 24 '19 at 7:46

You could also count the number of workers with loads above various predefined thresholds, and reward those counts in the objective. So, for example, assuming a load limit of $$M$$ for each worker, you could count workers with loads of $$M$$, $$0.75M$$ (inclusive) to $$M$$ (exclusive), or $$0.5M$$ (inclusive) to $$0.75M$$ (exclusive), and give the first category the highest value, the second category the second highest value, etc. (In this example, workers at less than 50% capacity would have objective value zero.)

One thing that might be worth considering is symmetry breaking constraints, since your workers are identical.

You haven't provided a formulation but I would assume that with a set of workers $$\mathcal{W}$$ and a set of jobs $$\mathcal{J}$$ you have a variable like:

$$x_{w,j} = \left\{ \begin{matrix}1 \text{ if worker } w \text{ is assigned job } j \\ 0 \text{ otherwise} \end{matrix} \right.$$

From this variable you could create another variable as such:

$$y_{w} = \left\{ \begin{matrix}1 \text{ if worker } w \text{ is assigned any job } \\ 0 \text{ otherwise} \end{matrix} \right.$$

Using the following constraint to link the variables:

$$\sum_{j \in \mathcal{J}} x_{w,j} \leq \vert \mathcal{J} \vert \hspace{0.05cm} y_{w} \hspace{0.5cm} \forall w \in \mathcal{W}$$

You can now implement a symmetry breaking constraint as such:

$$y_{w} \geq y_{w+1} \hspace{0.5cm} \forall w \in \left[0, \vert \mathcal{W} \vert -1 \right]$$

This constraint imposes an artificial precedence on the staff to be allocated, meaning that a staff member indexed by $$w$$ can only be assigned a job if the staff member indexed $$w-1$$ has been assigned at least one job. This is useful for two reasons:

1. You can now simply minimise the number of staff used by minimising $$\sum_{w \in \mathcal{W}} y_{w}$$, since this will make the model try and fill in each workers capacity before assigning the next worker a job.
2. This should help speed up the solving time, since by imposing symmetry breaking constraints you drastically reduce the size of the solution space.