Hi, I have a problem I've been trying to think of an appropriate way to frame for several days, and I can't quite get it correct. The issue is as follows: I have a set of 20 days and some number of employees, which we'll call Y. There is a separate variable for each employee on each day (10_1 would be a binary for employee 10 worked on day 1). I need to impose a constraint such that IF the employee was scheduled to work 5 days or fewer, then those 5 days MUST be spread apart by 4 days. In other words, they would have to work on day 1, 5, 9, 13, 17. Or they could work on day 2, 6, 10, 14, 18. Or if they're working only 3 days it could be 1, 8, 19. However, IF the employee is scheduled to work more than 5 days, then 5 of those days still must follow the constraint mentioned previously, but the rest of the days can be anywhere.

I believe I have a way to solve the case where it's 5 or more days by setting an indicator variable to 1 if they're working more than 5 days, and another indicator equal to 1 if one of the possible 4-spaced subsets are completely filled. Then those two indicators can just be set equal as a constraint. However, the case where it's fewer than 5 days is not as straightforward to me, because now I don't necessarily know the spacing without making every single combination of variables, which would just blow up. Any ideas would be appreciated!

asked 10 May '15, 11:08

napaman56's gravatar image

napaman56
313
accept rate: 0%

"IF the employee was scheduled to work 5 days or fewer, then those 5 days MUST be spread apart by 4 days". Do you mean 5 days or more?

(12 May '15, 04:14) rschwarz

"Spread apart by four days" sounds like "must have at least three off days between work days" to me. Suppose that we let binary variable \(x_{w,t}\) be 1 if worker \(w\) works on day \(t\), and let binary variable \(y_{w,t}\) be 1 if worker \(w\) starts a three day break on day \(t\). We need to ensure that workers do not work during breaks, which can be done with the constraints \( \sum_{t=\tau - 1}^{\tau + 1} y_{w,t} + x_{w,t} \le 1 \forall w, t \) (with the usual finagling of indices that are out of bounds). These constraints also preclude two credited breaks overlapping.

Now we need to ensure a sufficient number of breaks, which if I'm interpreting your question correctly would be \(\min(4, z_w - 1)\) where \(z_w = \sum_t x_{w,t}\) is the number of days \(w\) works. That's going to require another binary variable \(u_w \), which will be 1 if \(z_w \ge 5\), with the constraints\[\begin{aligned}z_{w} & \le4+16u_{w}\\ z_{w} & \ge5u_{w}\\ \sum_{t}y_{w,t} & \ge4u_{w}\\ \sum_{t}y_{w,t} & \ge z_{w}-1-20u_{w}. \end{aligned}\]

link

answered 10 May '15, 15:47

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 10 May '15, 15:50

While "at least three off days" makes sense from a practical point of view, in my interpretation, there have to be exactly 3 days off, iff there are at least 5 working days.

(12 May '15, 04:06) rschwarz

You could interpret the original statement that way, but it would be odd to mandate exactly three days off when working five or more days but accept longer breaks when working fewer days (as in the 1, 8, 19 example). We'll have to wait for the OP to clarify.

(12 May '15, 10:38) Paul Rubin ♦♦

In the constraint programming community, there is the concept of the regular global constraint. It enforces patterns (e.g., of work, break) that can be represented as regular expressions.

The implementation uses a finite (deterministic) state machine that is then "time-expanded" to yield a network flow model. This model can be used as is in a MIP model (or LP relaxation).

Have a look at the paper Modeling the Regular Constraint with Integer Programming by Louis-Martin Rousseau and others. From the abstract:

Many optimisation problems contain substructures involving constraints on sequences of decision variables. Such constraints can be very complex to express with mixed integer programming (MIP), while in constraint programming (CP), the global constraint regular easily represents this kind of substructure with deterministic finite automata (DFA). In this paper, we use DFAs and the associated layered graph structure built for the regular constraint consistency algorithm to develop a MIP version of the constraint. We present computational results on an employee timetabling problem, showing that this new modeling approach can significantly decrease computational times in comparison with a classical MIP formulation.

link

answered 12 May '15, 04:12

rschwarz's gravatar image

rschwarz
366210
accept rate: 21%

For ease of notation, let's assume that your rule of 4-spaced working days applies for shifts with at least 3 working days. A regular expression modelling your constraint could then be:

(b*)|(b*wb*)|(b*wb*wb*)|(b*(wbbb)*b*)

Here, "b" denotes a break, while "w" denotes a working day and "*" denotes repetition (at least 0 times). The first three terms of the disjunction "|" cover the cases of 0, 1, or 2 working days. The last term covers 3 or more working days, using the pattern of exactly 3 days off between working days.

(12 May '15, 04:18) rschwarz

I would introduce an additional index for the variable, i.e. \(x_{92}^1\) means that the the first working day of employee 9 is day 2, \(x_{92}^2\) means that the second working day of employee 9 is day 2 etc.

Once you have these variables, you can impose conditions that make sure that the difference between the first and second working day is at least 4, second and third is at least 4 and so on. For the sixth, seventh and so on working days, you impose no conditions so that they can be placed arbitrarily.

Furthermore, you need conditions of the form \(x_{92}^1 \geq x_{92}^2 \geq x_{93}^3\) to make sure that the working days are assigned in the designated order.

link

answered 10 May '15, 15:53

JF%20Meier's gravatar image

JF Meier
22329
accept rate: 11%

edited 10 May '15, 15:53

Thanks for the answer. I think I may have not emphasized part of the problem enough in that it should be easy to frame the part of a worker cannot work without at least a 3-day break after working for one day. The way I'm currently modeling this is to have indicators for each worker that indicates whether the following is equal to 1:

if d1+d2+d3+d4 = 1 => y1 = 1 if d2+d3+d4+d5 = 1 => y2 = 1 etc

Then iff the employee worked 5 or more days, the following condition must hold:

sum(y_i) >= 1

If they worked fewer than 5 days, then

sum(yi) = sum(di)

In other words, the number of days they're scheduled to work must be the sum of the indicators of unique 4-day spaced sets. Does that make sense?

rschwartz, I don't think Gurobi support constraint programming, right? If I switch to CPLEX I could look at that, but I'm not currently using it.

link

answered 12 May '15, 17:10

napaman56's gravatar image

napaman56
313
accept rate: 0%

You don't need a Constraint Programming solver for the approach using the regular constraint. Indeed, the linked paper is all about the formulation as an integer program.

(13 May '15, 03:45) rschwarz
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×37
×14

Asked: 10 May '15, 11:08

Seen: 695 times

Last updated: 13 May '15, 03:45

OR-Exchange! Your site for questions, answers, and announcements about operations research.