Create shifts in a constrained forecasted schedule, without workers.

[Richard T]

I thought I was close, but I am having issues creating contiguous sets for my solution, it's like the approach and I may need to do some sort combinatorics first, isn't of constraints. 

I have a labor demand curve over some period of time, lets say 12 hours and the curve goes from 6am to 6pm

s = [5, 5, 5, 6, 6, 6, 6, 6, 5, 5, 4, 4]

The rows are the combination of hours to = a shift

the columns are hours worked

The sum of a row must be either 0 or in range between x>=4  x<=8

The sum of the columns must be == to the total labor for that hour, defined as the positions in s[i]

I am having trouble constraining the problem to output contiguous spans/block of time to represent valid shifts, i.e. shift 1 and 4 are valid, shift 2 and 3 are not.  

I can get the continuous blocks to work when I use labor demand needs (num_hours) that are either 4,5,6,7,8,  but then it won't create a solution, when there is clearly a way to make a schedule that would work.  

I have been playing with an iteration on blocks of time and trying to create combinations of sets of variables to be equal to the constrain of 4,5,6,7,8 or 0.   Not 100% sure I am approaching this in the correct way.  I also need a way to add breaks into the constraints as well, but seems like one should walk before running. 

Labor Order	3 (6:00AM)	3 (7:00AM)	3 (8:00AM)	3 (9:00AM)
Sum(3) Shift 1	1	1	1	0
Sum(3) Shift 2	1	0	1	1
Sum(3) Shift 3	1	1	0	1
Sum(3) Shift 4	0	1	1	1

from __future__ import print_function

from ortools.constraint_solver import pywrapcp

from ortools.constraint_solver import solver_parameters_pb2

from ortools.linear_solver import pywraplp

def main():

  solver = pywrapcp.Solver("schedule_shifts")

  num_required_workers = 15

  num_hours = 8

  num_shifts = 15

  shifts = {}

  y={}

  for j in range(num_required_workers):

    for i in range(num_hours):

      shifts[(j, i)] = solver.IntVar(0, 1, "shifts(%i,%i)" % (j, i))

  shifts_flat = [shifts[(j, i)] for j in range(num_required_workers) for i in range(num_hours)]

  for j in range(num_required_workers):

      y[j] =  solver.IntVar(0, 1, "shift2(%i)" % (j))

  import numpy.random as nprnd

#  s = nprnd.randint(5,8, size=num_hours)

#  print(s)

#  print(sum(s))

  s =[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]

  for i in range(num_hours):

    solver.Add(solver.Sum([shifts[(j,i)] for j in range(num_required_workers)]) == s[i])

    print(s[i],i)

  for j in range(num_required_workers):

    solver.Add(solver.Sum([shifts[(j,i)] for i in range(num_hours)]) <= 8 * y[j])

    solver.Add(solver.Sum([shifts[(j,i)] for i in range(num_hours)]) >= 4 * y[j])

    solver.Add(y[j]<=1)

#  flatys = [y[j] for j in range(num_required_workers) ]

  z={}

  for j in range(num_required_workers):

      for i in range(num_hours-3):

          z[(j,i)] =  solver.IntVar(0, 1, "shift3(%i,%i)" % (j,i))

          solver.Add(z[(j,i)]<=1)

          solver.Add(solver.Sum([shifts[(j, i+k)] for k in range(4)])  == 4 * z[(j,i)])

  a ={}

  for j in range(num_required_workers):

      for i in range(num_hours-4):

          a[(j,i)] =  solver.IntVar(0, 1, "shift4(%i,%i)" % (j,i))

          solver.Add(a[(j,i)]<=1)

          solver.Add(solver.Sum([shifts[(j, i+k)] for k in range(5)])  == 5 * a[(j,i)])

  b= {}

  for j in range(num_required_workers):

      for i in range(num_hours-5):

          b[(j,i)] =  solver.IntVar(0, 1, "shift5(%i,%i)" % (j,i))

          solver.Add(b[(j,i)]<=1)

          solver.Add(solver.Sum([shifts[(j, i+k)] for k in range(6)])  == 6 * b[(j,i)])

  c={}

  for j in range(num_required_workers):

      for i in range(num_hours-6):

          c[(j,i)] =  solver.IntVar(0, 1, "shift6(%i,%i)" % (j,i))

          solver.Add(c[(j,i)]<=1)

          solver.Add(solver.Sum([shifts[(j, i+k)] for k in range(7)])  == 7 * c[(j,i)])

  d={}

  for j in range(num_required_workers):

      for i in range(num_hours-7):

          d[(j,i)] =  solver.IntVar(0, 1, "shift7(%i,%i)" % (j,i))

          solver.Add(d[(j,i)]<=1)

          solver.Add(solver.Sum([shifts[(j, i+k)] for k in range(8)])  == 8 * d[(j,i)])

  db = solver.Phase(shifts_flat, solver.CHOOSE_FIRST_UNBOUND,

                    solver.ASSIGN_MIN_VALUE)

  solution = solver.Assignment()

  collector = solver.AllSolutionCollector(solution)

  import time

  start2 = time.time()

  solver.NewSearch(db,[collector])

  num_solutions = 0

  while solver.NextSolution():

    for j in range(num_required_workers):

            print("x{}: ".format(j), [shifts[(j, i)].Value() for i in range(num_hours)])

#    print("num_coins:", totalhours.Value())

    print(sum([shifts_flat[i].Value() for i in range(len(shifts_flat))]))

    num_solutions += 1

    if num_solutions == 5:

        solver.EndSearch()

        break

  finish = time.time()

  print(finish-start2)

  print("num_solutions:", num_solutions)

  print("failures:", solver.Failures())

  print("branches:", solver.Branches())

if __name__ == "__main__":

  main()

[Mark]

If I'm understanding you correctly you want to enforce contiguity in a general way.

Consider modelling the global contiguity constraint using a regular constraint as demonstrated here:

https://github.com/hakank/hakank/blob/master/google_or_tools/contiguity_regular.py

[Laurent Perron]

I believe I have a much simpler way, 

generated all possible shifts (30 of them I believe), add a cardinality variable against each possible shift, then compute the sum of load for each time point.

It is a trivial linear problem.

If you need to add side constraints, it is easy to embed this model inside SAT or CP.

But currently, use the linear_solver.

Note that in general, you will not find an exact solution for a given work load (imagine a work load with 0 everywhere, except a lonely 1). 

So you want to balance overwork against number of worked hours, or simply minimize the number of overwork.

--Laurent

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Richard T]

This was going to be my second approach, it initially seemed trickier, but made more and more sense as I wrote out my current approach.  I had hoped with my current approach I could constrain it to only making valid shifts in the required labor and be a superior approach, but definitely making more sense the other way.  Will definitely share when I get it done.

The real problem is 17 hour working schedule with 15 minute increments, with multiple rules around breaks, with multiple locations and a shared workforce, with some needing a specific number of hours to comply with employment law, demand per day, per time is dynamic.  The idea was to generate valid schedule blocks on daily forecasted need,  then optimize for the week by location and workforce.  

Thank you!

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

[Richard T]

Knocked this out after work, this ended up being the initial solution.  Create all valid shift permutations (could write them directly to variables now, but I wanted the dictionary for other reasons),  can vary time_intervals i.e. 0 being 6AM and 11 being 6PM for a 12 hour day, Can set min and max shift lengths and create all permutations between the 2.  Solves very quickly and consistently for creating shifts that fit a forecasted labor schedule.

Thanks guys

from ortools.constraint_solver import pywrapcp

from ortools.constraint_solver import solver_parameters_pb2

from ortools.linear_solver import pywraplp

import numpy.random as nprnd

time_intervals = 17

s = nprnd.randint(5, 6, size=time_intervals)

print(s)

print(sum(s))

shiftmin = 4

shiftmax = 8

collectshifts ={}

for x in range(shiftmax-shiftmin+1):

    print x

    for i in range(time_intervals-(shiftmax-(x+1))):

        temp = []

        for j in range(time_intervals-(shiftmax-x-1)):

            if j == i:

                [temp.append(1) for k in range(shiftmax-x)]

            else:

                temp.append(0)

        collectshifts[(x,i)] = temp

solver = pywrapcp.Solver("schedule_shifts")

print(len(collectshifts)*time_intervals)

countrow = 0

variablesX = {}

variablesy={}

newrows = {}

for key,value in collectshifts.iteritems():

    countcolumn = 0

    variablesy[countrow] = solver.IntVar(0, 100, "Y(%i)" % (countrow))

    newrows[countrow] = value

    solver.Add(variablesy[countrow]>=0)

    for temp in value:

        tempxval = int(temp)

        variablesX[(countrow,countcolumn)] = solver.IntVar(tempxval, tempxval, "X(%i,%i)" % (countrow, countcolumn))

        solver.Add(variablesX[(countrow,countcolumn)]*variablesy[countrow]>=0)

        countcolumn+=1

    countrow +=1

for x in range(time_intervals):

    solver.Add(solver.Sum([variablesX[(j,x)]*variablesy[j] for j in range(len(collectshifts))]) == s[x])

    print s[x]

shifts_flat = variablesy.values()

new_xshifts =   variablesX.values()

db = solver.Phase(shifts_flat, solver.CHOOSE_FIRST_UNBOUND,

                    solver.ASSIGN_MIN_VALUE)

solution = solver.Assignment()

collector = solver.AllSolutionCollector(solution)

import time

start2 = time.time()

solver.NewSearch(db,[collector])

num_solutions = 0

while solver.NextSolution():

    for j in range(len(variablesy)):

            print("{}: ".format(shifts_flat[j]))

    print()

    num_solutions += 1

    if num_solutions == 100:

        solver.EndSearch()

        break

finish = time.time()

print(finish-start2)

print("num_solutions:", num_solutions)

print("failures:", solver.Failures())

print("branches:", solver.Branches())

[Laurent Perron]

Nice, 

now, as a exercise, and as we are phasing out pywrapcp in favor or pywrapsat (CP with a SAT backend), you can rewrite this for the new solver :-)

Examples are in examples/python/*sat.py

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.

[Colby Greene]

Hi - I'm facing a similar situation and am hoping to leverage the example above. I am getting an error when running the following:

for x in range(time_intervals):

    solver.Add(solver.Sum([variablesX[(j,x)]*variablesy[j] for j in range(len(collectshifts))]) == s[x])

    print (s[x])

TypeError: in method 'Solver_AddConstraint', argument 2 of type 'operations_research::Constraint *const'

Are there any recommended solutions for this error? 

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

[Laurent Perron]

Please use the CP-SAT solver.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le lun. 15 juil. 2019 à 11:58, Colby Greene <colby....@gopuff.com> a écrit :

Hi - I'm facing a similar situation and am hoping to leverage the example above. When running I am getting the following error:

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/d7e01a76-b234-4299-997c-9a4081efdece%40googlegroups.com.