Maximize assigned tasks to each worker

Question

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:
    worker_task_count[w] = model.NewIntVar(
        0, number_tasks, f'{w}_task_count'
    )
    squared_count[w] = model.NewIntVar(
        0, number_tasks**2, f'{w}_squared_task_count'
    )
    model.Add(
        worker_task_count[w] == sum(
            assigned_tasks[w, t]
            for t in tasks
        )
    )
    model.AddMultiplicationEquality(
        squared_count[w],
        [worker_task_count[w], worker_task_count[w]]
    )
self.model.Add(objective == sum(squared_count.values()))

Answer 1

Why quadratic?

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

Answer 2

There are some linear possibilities, depending on exactly what your goal is. They all require adding some binary variables to what is already a discrete optimization problem. One is to maximize the spread between the largest and smallest assigned loads (or maybe largest and smallest nonzero loads). That may result in one large load, one minimal (zero or one task) load and just about any mix of loads for the remaining workers, so I don't think it's the best choice. Another is to use a piecewise linear value function for individual loads, where each additional unit of load adds progressively larger amounts to the objective (to be maximized).

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.)

Answer 3

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.

More information about symmetry breaking can be found at:

https://pdfs.semanticscholar.org/0bac/193bc74453aa97759d1162401aaa4d6d907a.pdf