by Hans Fugal
You have a list of employees along with the hours they would _like_ to work, and the hours they _cannot_ work. You have a list of hours that need to be worked. (Extra credit for allowing for a different number of employees needed at different hours.)
Write a scheduler that schedules employees without scheduling them on hours they cannot work. It would be nice if the employees got as many of the hours they wanted as possible. It would be nice if the employees didn't end up with split shifts, had more or less consistent hours from day to day (e.g. Joe gets scheduled in mornings), and so forth.
Quiz Summary
The problem space of scheduling is vast and complicated, but it's not too hard to get some form of working solution. The real trick is the quality of the schedule generated.
I took a very easy approach, to keep the problem manageable. My initial thought when reading the problem was to use a "Hill Climbing" algorithm. I planned to start by just assigning every shift (ignoring availability and preference), and then swap shifts until I had a corrected schedule. That process changed a bit when I was actually coding it up though. More on that later.
The first thing I needed was some notion of time. I did consider using the built-in Time class, but I really wanted something simple. My approach only considers time in hour slices and the main functionality I needed was support for use in a Range object. Here's what I settled on:
require "yaml"
# A representation of a single hour. Usable in Ranges.
class Hour
def initialize( text )
@hour = case text
when "12 AM"
0
when "12 PM"
12
when /(\d+) PM/
$1.to_i + 12
else
text[/\d+/].to_i
end
end
include Comparable
def <=>( other )
@hour <=> other.instance_eval { @hour }
end
def succ
next_hour = Hour.new("12 AM")
next_time = (@hour + 1) % 24
next_hour.instance_eval { @hour = next_time }
next_hour
end
def to_s
str = case @hour
when 0
"12 AM"
when 12
"12 PM"
when 13..23
"#{@hour - 12} PM"
else
"#{@hour} AM"
end
"%5s" % str
end
end
# ...
The easiest way to get a unique and comparable representation of an hour I could think of was to use military time. That's exactly what the constructor does. I parse the string representation of a time and store the military hour (0-23) internally.
If you glance down, you'll see that to_s() is simply the reverse of this process. I use it in printing results.
The other two methods are simple. The documentation for Range say that you can use any object that supports <=>() and succ(), so that's what we have here. The <=>() method just compares the military hours. succ() builds a new Hour object then sets it to one hour ahead of the current object and returns the new Hour.
You can see that I'm using instance_eval() in both of these methods to read and adjust the internal representation in other Hour objects. That felt more correct than exposing the internal representation with an accessor and I think it's great that Ruby lets me make this choice.
The other helper class I felt need for was something to represent a worker. I wanted to be able to feed it the worker's requested schedule and then query it as needed. Here's the code:
# An object for tracking a worker's availability and preferences.
class Worker
def initialize( name )
@name = name
@avail = Hash.new
@prefers = Hash.new
end
attr_reader :name
def can_work( day, times )
@avail[day] = parse_times(times)
@prefers[day] = if times =~ /\((?:prefers )?([^)]+)\s*\)/
parse_times($1)
else
Hour.new("12 AM")..Hour.new("11 PM")
end
end
def available?( day, hour )
if @avail[day].nil?
false
else
@avail[day].include?(hour)
end
end
def prefers?( day, hour )
return false unless available? day, hour
if @prefers[day].nil?
false
else
@prefers[day].include?(hour)
end
end
def ==( other )
@name == other.name
end
def to_s
@name.to_s
end
private
def parse_times( times )
case times
when /^\s*any\b/i
Hour.new("12 AM")..Hour.new("11 PM")
when /^\s*before (\d+ [AP]M)\b/i
Hour.new("12 AM")..Hour.new($1)
when /^\s*after (\d+ [AP]M)\b/i
Hour.new($1)..Hour.new("11 PM")
when /^\s*(\d+ [AP]M) to (\d+ [AP]M)\b/i
Hour.new($1)..Hour.new($2)
when /^\s*not available\b/i
nil
else
raise "Unexpected availability format."
end
end
end
# ...
The constructor just makes note of the name for this Worker, then sets up two Hash objects to hold availability and preferred schedule. The Hashes will use a day of the week as a key and a Range of Hour objects as the value. An availability of "any" can be represented as a Range of all the Hours in a day. This is easy to work with, but it can't handle split-shift style availabilities. You could fix this by making the values Arrays of Ranges.
The next three methods are all closely related. First, can_work() takes a day String and a String representation of available times and uses those to set the previously mentioned Hashes. The actual parsing is delegated to the private parse_time() method, which just uses Regexps to break down the input. Once a schedule has been loaded, you can check availability for a given day and hour with available?(). The prefers?() method takes the same input but returns a preference instead. A Worker must be available to work a given time to have a preference about it.
Those are the only helper classes I built. The rest is application code:
if __FILE__ == $0
unless ARGV.size == 1 and File.exists?(ARGV.first)
puts "Usage: #{File.basename($0)} SCHEDULE_FILE"
exit
end
# load the data
data = File.open(ARGV.shift) { |file| YAML.load(file) }
# build worker list
workers = Array.new
data["Workers"].each do |name, avail|
worker = Worker.new(name)
avail.each { |day, times| worker.can_work(day, times) }
workers << worker
end
# ...
That's all pretty basic. Check and display usage, if needed; load the YAML representation of workers and schedule hours to be filled; anf finally, build an Array of Worker objects that are aware of their availability and preferences. Here's the YAML file I'm using:
---
Schedule:
Wed: 9 AM to 6 PM
Sun: 9 AM to 10 PM
Thu: 9 AM to 8 PM
Mon: 9 AM to 6 PM
Tue: 9 AM to 6 PM
Sat: 9 AM to 10 PM
Fri: 9 AM to 6 PM
Workers:
James:
Wed: any
Sun: any (prefers before 5 PM)
Thu: 12 PM to 3 PM
Mon: before 3 PM (prefers before 12 PM)
Tue: any
Sat: not available
Fri: 12 PM to 3 PM
Brian:
Wed: not available
Sun: after 1 PM
Thu: any (prefers 8 AM to 5 PM)
Mon: any (prefers 8 AM to 5 PM)
Tue: any (prefers 8 AM to 5 PM)
Sat: any
Fri: any (prefers 8 AM to 5 PM)
The next step is to build a schedule. Here's where I deviated from my original plan. I realized that if I limit myself to just worrying about availability at first, I can build a correct schedule in those terms as I load it. Here's how that turns out:
# create a legal schedule, respecting availability
schedule = Hash.new
data["Schedule"].each do |day, times|
schedule[day] = Array.new
if times =~ /^\s*(\d+ [AP]M) to (\d+ [AP]M)\b/i
start, finish = Hour.new($1), Hour.new($2)
else
raise "Unexpected schedule format."
end
(start..finish).each do |hour|
started_with = workers.first
loop do
if workers.first.available? day, hour
schedule[day] << [hour, workers.first]
break
else
workers << workers.shift
if workers.first == started_with
schedule[day] << [hour, "No workers available!"]
break
end
end
end
end
workers << workers.shift
end
# ...
A schedule is a Hash that stores day names paired with Arrays of Arrays. The Arrays are a collection of Hour and Worker pairs, showing who is scheduled to work at that time.
The second half of that code is what assembles the initial schedule. It just walks every hour of every day assigning a worker. It starts with the first worker in the list and keeps assigning them until them end of the day or until the worker has a schedule conflict. Anytime either of those conditions happens, the worker list is rotated and we try the next worker.
If we make it all the way through the list of workers without finding a person who could work at that time, we just set the Worker slot to a warning message and rely on the user to fix the problem. Blowing up with an exception here seemed too drastic for what is likely a fairly common snag that I doubt software is qualified to resolve.
The main issue with the above system is that it can assign people very long or very short shifts. I think a good way to correct this would be to set minimum and maximum shift lengths and adjust the software to honor them. Of course, this will create more conflicts so you either have to accept that or make them soft limitations.
Now, my code does make a second pass adjusting shifts, but now the focus turns from availability to preference. Let's examine that:
# make schedule swaps for preferred times
schedule.each do |day, hours|
hours.each_with_index do |(hour, worker), index|
next unless worker.is_a?(Worker)
unless worker.prefers?(day, hour)
alternate = workers.find { |w| w.prefers?(day, hour) }
hours[index][-1] = alternate unless alternate.nil?
end
end
end
# ...
Here I'm just searching for people working hours they didn't prefer. When found, I try to swap them out for someone who did prefer the time, if I can find such a person. Otherwise, they have to stay.
Again, this can create some odd schedules. Mainly, people are traded on an hourly basis and this can cause scheduling of one hour shifts. Again, I think the answer is minimum shift lengths as I mentioned above, but in practice this wasn't a chronic problem with availabilities like the ones in the YAML file. When someone passed out of the times they preferred, it would generally cause the rest of their shift to be replaced with someone that did want to work the time.
All that remains is to print the schedule:
# print schedule
%w{Mon Tue Wed Thu Fri Sat Sun}.each do |day|
puts "#{day}:"
schedule[day].each do |hour, worker|
puts " #{hour}: #{worker}"
end
end
end
That's as easy as it looks. Walk the days, printing hours and who's working at that time.
All-in-all it's an imperfect solution, but I think you could keep tuning it until you get what you need. It works, but can certainly be made better.
Next week's Ruby Quiz is the number game that's been requested of me twice now, so I really hope I'm not the only guy working that one...
