From: Ruby Quiz <james@...>
Date: 2005-08-18T23:11:30+09:00
Subject: [SUMMARY] Scheduling (#42)

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