8
$\begingroup$

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()))
$\endgroup$
  • 1
    $\begingroup$ 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)? $\endgroup$ – prubin Sep 25 at 20:40
  • $\begingroup$ Yes, they are identical. Would that simplify the problem? $\endgroup$ – Stradivari Sep 26 at 9:31
  • 1
    $\begingroup$ Yes, in that there is no concern for whether shifting load from one worker to another adversely effects cost or productivity. $\endgroup$ – prubin Sep 28 at 17:49
9
$\begingroup$

Why quadratic?

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

$\endgroup$
  • $\begingroup$ so, something like (n*1000*tasks1)+((n-1)*1000*tasks2)+... $\endgroup$ – Stradivari Sep 23 at 19:26
  • 2
    $\begingroup$ Yes. It has some limitation, you do not have that large range of weights. It is always better than quadratic anyway. $\endgroup$ – Laurent Perron Sep 23 at 19:27
  • $\begingroup$ 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? $\endgroup$ – Stradivari Sep 24 at 0:21
  • $\begingroup$ @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. $\endgroup$ – Holt Sep 24 at 6:54
  • 1
    $\begingroup$ You can maximize the absolute value of their difference $\endgroup$ – Laurent Perron Sep 24 at 7:46
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.