title: Determine allocation of values - Python
body: <p>I am trying to create an optimal shift schedule where employees are assigned to shift times. The output should aim to spend the least amount of money. The tricky part is I need to account for specific constraints. These being:</p>
  <pre><code>1) At any given time period, you must meet the minimum staffing requirements
  2) A person has a minimum and maximum amount of hours they can do
  3) An employee can only be scheduled to work within their available hours
  4) A person can only work one shift per day
  </code></pre>
  <p>The <code>staff_availability df</code> contains the employees to choose from <code>['Person']</code>, the available min - max hours they can work <code>['MinHours']</code>-<code>['MaxHours']</code>, how much they get paid <code>['HourlyWage']</code>, and availability, expressed as hours <code>['Availability_Hr']</code> and 15min segments <code>['Availability_15min_Seg']</code>.</p>
  <p>Note: Available employees don't have to be assigned shifts if not required. They're  just available to do so.</p>
  <p>The <code>staffing_requirements df</code> contains the time of day <code>['Time']</code> and the staff required <code>['People']</code> during those periods.</p>
  <p>The script returns a <code>df</code> <code>'availability_per_member'</code> that displays how many employees are available at each point in time. So <code>1</code> indicates available to be scheduled and <code>0</code> indicates not available. It then aims to allocate shift times, while accounting for the constraints using <code>pulp</code>.</p>
  <p>I am getting an output but the shift times aren't applied to employees consecutively.</p>
  <h1>I am not meeting the 4th constraint in that employees can only work one shift a day</h1>
  <pre><code>import pandas as pd
  import matplotlib.pyplot as plt
  import matplotlib.dates as dates
  import pulp
  
  staffing_requirements = pd.DataFrame({
      'Time' : ['0/1/1900 8:00:00','0/1/1900 9:59:00','0/1/1900 10:00:00','0/1/1900 12:29:00','0/1/1900 12:30:00','0/1/1900 13:00:00','0/1/1900 13:02:00','0/1/1900 13:15:00','0/1/1900 13:20:00','0/1/1900 18:10:00','0/1/1900 18:15:00','0/1/1900 18:20:00','0/1/1900 18:25:00','0/1/1900 18:45:00','0/1/1900 18:50:00','0/1/1900 19:05:00','0/1/1900 19:07:00','0/1/1900 21:57:00','0/1/1900 22:00:00','0/1/1900 22:30:00','0/1/1900 22:35:00','1/1/1900 3:00:00','1/1/1900 3:05:00','1/1/1900 3:20:00','1/1/1900 3:25:00'],                 
      'People' : [1,1,2,2,3,3,2,2,3,3,4,4,3,3,2,2,3,3,4,4,3,3,2,2,1],                      
       })
  
  staff_availability = pd.DataFrame({
      'Person' : ['C1','C2','C3','C4','C5','C6','C7','C8','C9','C10','C11'],                 
      'MinHours' : [3,3,3,3,3,3,3,3,3,3,3],    
      'MaxHours' : [10,10,10,10,10,10,10,10,10,10,10],                 
      'HourlyWage' : [26,26,26,26,26,26,26,26,26,26,26],  
      'Availability_Hr' : ['8-18','8-18','8-18','9-18','9-18','9-18','12-1','12-1','17-3','17-3','17-3'],                              
      'Availability_15min_Seg' : ['1-41','1-41','1-41','5-41','5-41','5-41','17-69','17-79','37-79','37-79','37-79'],                              
      })
  
  staffing_requirements['Time'] = ['/'.join([str(int(x.split('/')[0])+1)] + x.split('/')[1:]) for x in staffing_requirements['Time']]
  staffing_requirements['Time'] = pd.to_datetime(staffing_requirements['Time'], format='%d/%m/%Y %H:%M:%S')
  formatter = dates.DateFormatter('%Y-%m-%d %H:%M:%S') 
  
  # 15 Min
  staffing_requirements = staffing_requirements.groupby(pd.Grouper(freq='15T',key='Time'))['People'].max().ffill()
  staffing_requirements = staffing_requirements.reset_index(level=['Time'])
  
  staffing_requirements.index = range(1, len(staffing_requirements) + 1) 
  
  staff_availability.set_index('Person')
  
  staff_costs = staff_availability.set_index('Person')[['MinHours', 'MaxHours', 'HourlyWage']]
  availability = staff_availability.set_index('Person')[['Availability_15min_Seg']]
  availability[['first_15min', 'last_15min']] =  availability['Availability_15min_Seg'].str.split('-', expand=True).astype(int)
  
  availability_per_member =  [pd.DataFrame(1, columns=[idx], index=range(row['first_15min'], row['last_15min']+1))
   for idx, row in availability.iterrows()]
  
  availability_per_member = pd.concat(availability_per_member, axis='columns').fillna(0).astype(int).stack()
  availability_per_member.index.names = ['Timeslot', 'Person']
  availability_per_member = (availability_per_member.to_frame()
                          .join(staff_costs[['HourlyWage']])
                          .rename(columns={0: 'Available'}))
  
  
  ''' Generate shift times based off availability  '''
  
  prob = pulp.LpProblem('CreateStaffing', pulp.LpMinimize) # Minimize costs
  
  timeslots = staffing_requirements.index
  persons = availability_per_member.index.levels[1]
  
  # A member is either staffed or is not at a certain timeslot
  staffed = pulp.LpVariable.dicts(&quot;staffed&quot;,
                                     ((timeslot, staffmember) for timeslot, staffmember 
                                      in availability_per_member.index),
                                       lowBound=0,
                                       cat='Binary')
  
  # Objective = cost (= sum of hourly wages)                              
  prob += pulp.lpSum(
      [staffed[timeslot, staffmember] * availability_per_member.loc[(timeslot, staffmember), 'HourlyWage'] 
      for timeslot, staffmember in availability_per_member.index]
  )
  
  # Staff the right number of people
  for timeslot in timeslots:
      prob += (sum([staffed[(timeslot, person)] for person in persons]) 
      == staffing_requirements.loc[timeslot, 'People'])
  
  # Do not staff unavailable persons
  for timeslot in timeslots:
      for person in persons:
          if availability_per_member.loc[(timeslot, person), 'Available'] == 0:
              prob += staffed[timeslot, person] == 0
  
  # Do not underemploy people
  for person in persons:
      prob += (sum([staffed[(timeslot, person)] for timeslot in timeslots])
      &gt;= staff_costs.loc[person, 'MinHours']*4) # timeslot is 15 minutes =&gt; 4 timeslots = hour
  
  # Do not overemploy people
  for person in persons:
      prob += (sum([staffed[(timeslot, person)] for timeslot in timeslots])
      &lt;= staff_costs.loc[person, 'MaxHours']*4) # timeslot is 15 minutes =&gt; 4 timeslots = hour
  
  
  prob.solve()
  print(pulp.LpStatus[prob.status])
  
  output = []
  for timeslot, staffmember in staffed:
      var_output = {
          'Timeslot': timeslot,
          'Staffmember': staffmember,
          'Staffed': staffed[(timeslot, staffmember)].varValue,
      }
      output.append(var_output)
  output_df = pd.DataFrame.from_records(output)#.sort_values(['timeslot', 'staffmember'])
  output_df.set_index(['Timeslot', 'Staffmember'], inplace=True)
  if pulp.LpStatus[prob.status] == 'Optimal':
      print(output_df)
  </code></pre>
  <p>Below is an output for the first two hours (8 15 min time slots). The issue is the shifts aren't consecutive. The employees scheduled for the first <code>8</code> time slots are mainly different. I'd have 5 people starting within the first 2 hours. Employees should only work one shift per day.</p>
  <pre><code>   Timeslot   C
  0         1  C2
  1         2  C2
  2         3  C1
  3         4  C3
  4         5  C6
  5         6  C1
  6         7  C5
  7         8  C2
  </code></pre>