2
$\begingroup$

I am building a staff scheduling model that has a set of binary variables $x_{[i,j]}$, subject to some set of constraints, where $x_{[i,j]}=1$ when person $i$ is assigned to job $j$.

So far my objective function is just:

$\text{maximise} \displaystyle\sum_{i \in I}\displaystyle\sum_{j \in J} x_{[i,j]}$

which aims to find a feasible solution that allocates as many jobs as possible. And it works fine, and produces feasible solutions with nearly all of the jobs allocated (I don't think full allocation is actually possible, so I am not particularly worried about that).

The only problem is that the solutions seem to wind up allocating lots of jobs to certain people, and nothing to others. So I am wondering if there is something I can do in my objective function that will help me to make the spread a little bit more even?

It doesn't really have to be even between people, but even something like a reward for maximising the number of people who have at least one job allocated to them or something would help a lot.

I can't just put a constraint in that says:

$\displaystyle\sum_{j \in J} x_{[i,j]} \geq 1, \qquad \forall i \in I$

because it makes the model infeasible. So I was hoping there would be a way to implement something in the objective function that encourages the model to spread it around a bit more, rather than forces it to. :)

$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

Sure, you can penalize the maximum number of jobs allocated to any one person!

In particular, you can add a factor to your objective of the form $$-\gamma \max_i \sum_j x_{ij}.$$

We can easily write $\max_i y_i$ by introducing a new variable $t \ge y_i$ for each $i$, where $\gamma \ge 0$ is some nonnegative penalty.

$\endgroup$
6
  • $\begingroup$ Thanks for your reply. I think I understand what you mean. So you are saying to introduce a new variable $y_i,\ \forall i \in I$ that penalises the number of jobs assigned to each $i$? I assume this $y_i$ is continuous.. do i need to add any constraints to the model with respect to $y$? also, what is $t$? $\endgroup$ Commented Feb 7, 2020 at 2:39
  • $\begingroup$ Ah, pretty sure i understand what you mean now. I add a constraint that says $\sum_{j \in J} x_{[i,j]} \leq y_i$ and then penalise the $y_i$'s in the objective function using $\gamma$? That way it lets the model raise the limit for the constraint, but at a cost? $\endgroup$ Commented Feb 7, 2020 at 5:04
  • 2
    $\begingroup$ I think he means the $y_i$ in this case to be $y_i = \sum_j x_{ij}$. We introduce $t$ as the new variable with the constraints $t \geq \sum_j x_{ij}$ and add the penalty term $-\gamma t$. Then for any fixed $x_{ij}$ the objective function is maximized by making $t$ as small as possible, so we can assume $t = \max \sum_j x_{ij}$. $\endgroup$ Commented Feb 7, 2020 at 6:38
  • 2
    $\begingroup$ Sure. Really you just need $t$, not the $y_i$, since you can just set directly the constraints $t \geq \sum_j x_{ij}$. I'd guess the reason Guillermo used $y_i$ was just for generality (showing you how in general to take the maximum in a linear programming context.) $\endgroup$ Commented Feb 7, 2020 at 7:45
  • 1
    $\begingroup$ Ah yes, that makes complete sense, thanks a lot for both of your help! $\endgroup$ Commented Feb 7, 2020 at 16:24

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.