[SUMMARY] Scheduling (#42)

(James Edward Gray II) #1

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:

  #!/usr/local/bin/ruby -w

  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...