Linear Programming constraints clarification

linear programming

Given https://machinelearninggeek.com/solving-staff-scheduling-problem-using-linear-programming/ this case on scheduling,

  • Can someone explain constraints 1, the latter $3$?
  • Where on constraints 2 is $x_3$ if $x_2$ is also considered?

I played around with the constraints and got a different answer and am not convinced the prose and example are correct. It's a while since I looked at LP. However, I am pretty sure this example is incorrect.

Staff Scheduling Problem as in the link

In this problem, a saloon owner wants to determine the schedule for staff members. The staff consists of the full-time shift of $9$ hours and part-time shift of $3$ hours. The saloon’s opening hours are divided into $4$ shifts of $3$ hours each. In each shift, different levels of demands are there that need the different number of staff members in each shift.

The required number of nurses for each shift is mentioned in the below table:

Shift     Time Period   Number of Employees
Morning   09 AM-12 PM   6
Afternoon 12-03 PM      11
Evening   03-06 PM      8
Night     06-09 PM      6

There is at least 1 full-time employee we need in each shift.

The full-time employee will get $150$ dollars for $9$ hours shift and the part-time employee will get $45$ dollars per shift.

The decision variables, objective function, constraints are as follows:

Decision Variables:

$x_I$ = Number of full-time employees scheduled in shift $I$.

$y_I$ = number of part-time employees scheduled in shift $I$.

Objective Function:

$\text{minimize} \; Z= 150( x_0 + x_1 + x_2 + x_3 ) + 45( y_0 + y_1 + y_2 + y_3 )$

Constraints 1:

Employee starting shift constraints

$x_0 + y_0 ≥ 6$

$x_0 + x_1 + y_1 \ge 8$

$x_1 + x_2 + y_2 \ge 11$

$x_2 + x_3 + y_3 \ge 6$

Constraints 2:

Minimum full-time employees during any shift/period

$x_0 \ge 1$

$x_1 \ge 1$

$x_2 \ge 1$

FINISH OF EXAMPLE ON INTERNET

MY SOLUTION BY HAND CALCULATION

enter image description here
Based on comments made by observer, on no-partial shifts for full-timers (although not that that is stated), then I think this is better approach:

# Import all classes of PuLP module
from pulp import *

# Initialize Class
model = LpProblem("StaffSchedulingProblem", LpMinimize)

# Create Shifts
shifts = list(range(4))

# Define Decision Variables
x = LpVariable.dicts('fulltimeshift_', shifts, lowBound=0, cat='Integer')
y = LpVariable.dicts('parttimeshift_', shifts, lowBound=0, cat='Integer')

# Define Objective
model += 150 * lpSum([x[i] for i in shifts]) + 45 * lpSum([y[i] for i in shifts])

# Define Constraints: For Employee starting the shift

model += x[0]+y[0]>=6
model += x[0]+x[1]+y[1]>=11
model += x[0]+x[1]+y[2]>=8
model += x[1]+y[3]>=6

# Define Constraints: At least full-time employee during any shift
model += x[0]>=1
model += x[1]>=1

# The problem is solved using PuLP's choice of Solver
model.solve()

# Print the variables optimized value
for v in model.variables():
    print(v.name, "=", v.varValue)
    
# The optimised objective function value is printed to the screen
print("Total Cost of Staff = ", value(model.objective))

The model vs. hand calc agree.

So I am looking how the proposed example is more correct than my approach – which I believe it is not. I think it misses the overlapping shift aspect of a full-time employee. If so, then this is a poor showing.

Best Answer

I agree with your mathematical formulation of the problem.

In my opinion, the statement of the problem itself is very poorly worded:

  • It's not at all clear whether or not full-time staff can perform a split shift of one $6$-hour stint and one $3$-hour stint separated by $3$-hours off. I'd normally expect an employee doing such a shift to be paid more than one who just does a straight shift of $9$ hours. So the fact that there's only one size, $\ \$150$, of payment specified for a full-time shift does suggest that split shifts aren't allowed. That's hardly conclusive, however.
  • It's also not entirely clear whether or not full-time employees can perform part-time shifts. Again, though, the fact that no payment is specified for such an option tends to suggest that it's not allowed.
  • It must be a pretty tough saloon if its owner needs $11$ nurses on hand for an afternoon shift.

In my opinion, the assumptions you've made to resolve the above-mentioned ambiguities are the most reasonable. In practice, if this were a real problem you were trying to formulate for a client, you should resolve the ambiguities by getting your client to clarify his or her requirements. On the other hand, if you're doing the exercise as a class assignment, it would be a good idea to point out the ambiguities and clearly state what assumptions you've made to resolve them. I'd suggest choosing your language tactfully, however (something like "I'm not sure I've understood this statement correctly" rather than "This statement is not at all clear"). While it's very possible that ambiguities like this may well be deliberately included by the formulator of the problem as a test of his or her students' abilities to detect them, they could very well also be unintentional (which I suspect is the case here).

There are several inconsistencies between the statement of the problem and its mathematical formulation given on the machinelearninggeek web page:

  • The number of employees required for the afternoon and evening shifts in the mathematical formulation are the reverse of what they are in the problem statement.
  • The mathematical formulation seems to be assuming six-hour full time shifts, rather than the nine-hours specified in the problem statement. This is suggested by the fact that $\ x_0\ $ appears only in the first two constraints, $\ x_1\ $ only in the second and third, and $\ x_2\ $ only in the third and fourth.
  • The variable $\ x_3\ $ is at least redundant, but I would categorise it as an ouright mistake. It supposedly represents the number of full-time employees starting work on the night shift, which means that they would only be working a single three-hour part-time shift while the objective function sill has them being paid the full $\ \$150\ $ for a complete full time shift. As it happens, this mistake doesn't have any really deleterious consequences, because $\ x_3\ $ will automatically be set to $0$ in the optimal solution of the erroneously formulated problem.

It looks to me like the problem statement and mathematical formulation given on the website might be a confabulation of two different problems. The original looks like it might have been one of assigning nurses to shifts in a hospital ward in which the full-time shifts were of $6$ hours, while the updated version is supposed to have been the assignment of bar staff to shifts in a saloon in which the full-time shifts are of $9$ hours. Whoever updated the page, however, missed the word "nurses" in the statement of requirements, and forgot to update the mathematical formulation of the problem.

Related Question