title: Optimal shift scheduling algorithm
body: <p>I have been trying for some time solve a scheduling problem for a pool that I used to work at. This problem is as follows...</p>
  
  <p>There are X many lifeguards that work at the pool, and each has a specific number of hours they would like to work. We hope to keep the average number of hours away from each lifeguards desired number of hours as low as possible, and as fair as possible for all. Each lifeguard is also a college student, and thus will have a different schedule of availability.</p>
  
  <p>Each week the pool's schedule of events is different than the last, thus a new schedule must be created each week. </p>
  
  <p>Within each day there will be so many lifeguards required for certain time intervals (ex: 3 guards from 8am-10am, 4 guards from 10am-3pm, and 2 guards from 3pm-10pm). <strong>This is where the hard part comes in.</strong> There are no clearly defined shifts (slots) to place each of the lifeguards into (because of the fact that creating a schedule may not be possible provided the availability of the lifeguards plus the changing weekly pool schedule of events).</p>
  
  <p>Therefore a schedule must be created from a blank slate provided only with...</p>
  
  <ul>
  <li>The Lifeguards and their information (# of desired hours, availability)</li>
  <li>The pool's schedule of events, plus number of guards required to be on duty at any moment</li>
  </ul>
  
  <p>The problem can now be clearly defined as "Create a possible schedule that covers the required number of guards at all times each day of the week AND be as fair as possible to all lifeguards in scheduling." </p>
  
  <p>Creating a possible schedule that covers the required number of guards at all times each day of the week is the part of the problem that is a necessity and must be completely solved. The second half about being as fair as possible to all lifeguards significantly complicates the problem leading me to believe I will need an approximation approach, since the possible number of way to divide up a work day could be ridiculous, but sometimes may be necessary as the only possible schedule may be ridiculous for fairness.</p>
  
  <p><strong>Edit</strong>: One of the most commonly suggested algorithms I find is the "Hospitals/Residents problem", however I don't believe this will be applicable since there are no clearly defined slots to place workers.</p>