0
$\begingroup$

hopefully I can get some help on this problem, it's got me quite stumped.

I was given a linear programming problem with the goal of minimizing labor costs. The variables x_t represent the number of workers available in month t (t = 1, 2, ..., 12), while o_t represents how many of the workers can work overtime hours in month t. The problem has two constraints on overtime:

"Overtime may not exceed 10% of straight time production in any month, and overtime may not be scheduled for more than two consecutive months."

I've got the 10% restriction done, but I absolutely cannot figure out how to make the constraint for consecutive months. I have a feeling that I need to use binary variables, i.e., if y_t represents whether or not overtime was activated in month t (t = 3, ... 12), and y_t is either 0 or 1, then y_t-2 + y_t-1 + y_t ≤ 2. But I can't figure out how to tie this into my overtime constraint.

I appreciate any help I can get. Thank you.

EDIT:

Right now my 10% constraint is: o_t ≤ 0.1*x_t for t = 1, 2, ..., 12

$\endgroup$
4
  • $\begingroup$ What's your 10% constraint? $\endgroup$ Commented Sep 26, 2013 at 21:18
  • $\begingroup$ I understand what you're saying, I apologize since I didn't phrase that correctly. What I meant was, I do not know how to correlate the y_i variables to my overtime variables. So, if overtime for any workers was scheduled for month 5, how does y_5 get set to 1? It's been years since I've done LP, so this may be obvious but I'm just not seeing it. Thank you. $\endgroup$ Commented Sep 26, 2013 at 21:23
  • $\begingroup$ ok- I need to think about that $\endgroup$ Commented Sep 26, 2013 at 21:25
  • $\begingroup$ See my answer @RLS $\endgroup$ Commented Sep 26, 2013 at 21:41

1 Answer 1

0
$\begingroup$

You have an if/then constraint, which is if '$O_t \gt 0$ then $y_t = 1$'.

If P then Q is equivalent to (not P) or Q and so we have

$O_t \le 0$ or $y_t = 1$.

Why not $O_t = 0$ instead of $O_t \le 0$?

We will need to add the constraint $O_t \ge 0$ anyway, so this is covered. Later on it will become clear (Godwilling) why we use $O_t \le 0$ rather than $O_t = 0$.

The standard way of dealing with an either X or Y constraint like this (where X and Y are constraints involving integer variables) is to add these 2 constraints:

$O_t \le M_1 \delta$ (where $\delta $ is a binary variable and we choose the constant $M_1$ according to the problem after thinking about it).

$-y_t \le \ M_2(1-\delta)$ (however, since $y_t$ is a binary rather than an integer variable, it's necessary to adapt the method at this point to fit the problem). Since the only possible values for $y_t$ are 0 and 1, why not just try the following:

$y_t = \delta$.

If $\delta = 0$, $O_t \le 0$ (from constraint 1) and so $O_t = 0$ (from non-negativity contraint).

$\delta = 0$ sets $y_t$ to $0$ in the second constraint.

If $\delta = 1$, the first constraint becomes $O_t \le M_1$. What should we choose $M_1$ to be? So as to allow our solution method to consider all possible values of $O_t$ and choose the optimal one, choose $M_1$ to be 0.1 $\times S_t$, where $S_t$ is the value of the straight time production for month t.

$\delta = 1$ sets $y_t$ to 1 as well, as required.

At this point, I realised that since the second constraint tell us that $y_t = \delta$, we don't really need it. We can just replace the binary variable $\delta $ by $y_t$ itself and have just the first constraint (changing $M_1$ to $M$):

$O_t \le My_t$ where M = 0.1 $\times$ straight time production for month t.

The method you use to solve it will now be able to compare the following 2 possibilites and find which produces the optimal solution. To be rigorous, let's just make sure the constraints are all covered:

case 1: $y_t = 0$

Since $y_t$ = 0, we need $O_t = 0$ which it is when $y_t = 0$ is substituted into $O_t \le My_t$.

case 1: $y_t = 1$

Now we just need $O_t \le 0.1S_t$, precisely what we get by substituting $y_t = 1$ into the constraint.

$\endgroup$
6
  • $\begingroup$ That's it! Thank you! $\endgroup$ Commented Sep 26, 2013 at 22:03
  • $\begingroup$ No probs: I've just added a lengthy explanation of how I worked this out which is almost finished. (Don't feel obliged to read it, but's it's there if you need it). $\endgroup$ Commented Sep 26, 2013 at 22:16
  • $\begingroup$ Very good explanation, thank you for taking the time to write it all out. Everything makes sense! $\endgroup$ Commented Sep 27, 2013 at 15:03
  • $\begingroup$ No probs: actually, I've thought of some improvements I could make to the explanation to make it clearer, but I haven't done anything about it yet. $\endgroup$ Commented Sep 28, 2013 at 11:37
  • $\begingroup$ Just made the edits. This could be the final draft! $\endgroup$ Commented Sep 28, 2013 at 11:49

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.