[QUIZ] Scheduling (#42)
Ruby Quiz
1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.
2. Support Ruby Quiz by submitting ideas as often as you can:
3. Enjoy!
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
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.
Brian Schröder
How are theses hours given? Is it a one-time appointment, repeating
appointments on a weekly/monthly basis? Is there an example input so
we can test the programs against each other?
regards,
Brian
--
http://ruby.brian-schroeder.de/
Stringed instrument chords: http://chordlist.brian-schroeder.de/
James Edward Gray II
> How are theses hours given? Is it a one-time appointment, repeating
> appointments on a weekly/monthly basis? Is there an example input so
> we can test the programs against each other?
Here's one possible idea. What do you think?
James Edward Gray II
---
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)
Brian Schröder
Interesting to parse. May I assume then, that there are only timeslots
of full hours?
James Edward Gray II
> Interesting to parse.
If you've got an easier format in mind, toss it up here. I'm not picky.
> May I assume then, that there are only timeslots of full hours?
I assumed that from reading of quiz. It's probably an over
simplistic assumption, but I think it will do for this challenge.
James Edward Gray II
P.S. Hans, feel free to jump in here and save me at any time... :D
Kero
>
> I assumed that from reading of quiz. It's probably an over
> simplistic assumption, but I think it will do for this challenge.
Isn't the problem in general NP hard? Meaning you have to make some
simplifications to keep the input small, or apply some other
restrictions to get the problem to P.
Of course, it is also possible to generate input for which there is no
solution. Then what? When to loosen bonus targets like regular times for
a person and when to give up?
I think everybody has to figure this out for him/herself.
Moreover, do not restrict the application to people and time, it can be
anything and time (or even boxes and space if you can restrict the space
to 1D meaningfully :)
I can't suppress the feeling that the quiz is meant to pick a "nice"
solution when there's plenty of solutions available. For which you need
(a lot of) example input...
+--- Kero ------------------------- kero@chello@nl ---+
| all the meaningless and empty words I spoke |
| Promises -- The Cranberries |
+--- M38c --- http://members.chello.nl/k.vangelder ---+
James Edward Gray II
Mon:
9 AM: Brian
10 AM: Brian
11 AM: Brian
12 PM: Brian
1 PM: Brian
2 PM: Brian
3 PM: Brian
4 PM: Brian
5 PM: Brian
6 PM: Brian
Tue:
9 AM: Brian
10 AM: Brian
11 AM: Brian
12 PM: Brian
1 PM: Brian
2 PM: Brian
3 PM: Brian
4 PM: Brian
5 PM: Brian
6 PM: James
..
Sun:
9 AM: James
10 AM: James
11 AM: James
12 PM: James
1 PM: James
2 PM: James
3 PM: James
4 PM: James
5 PM: James
6 PM: Brian
7 PM: Brian
8 PM: Brian
9 PM: Brian
10 PM: Brian
This is a legal schedule, with everyone having shifts only when they
are available. On top of that, it tries to correct for preferred
schedules as much as possible.
That's probably a bit of a problem, because you get schedules like
Tuesday above, with one hour shifts. To correct this, you probably
need to set something like a minimum shift length and assign only in
terms of those. Exploration of such possibilities is left as an
exercise to the reader... :)
Here's the code:
#!/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
# 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
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
# 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
# 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
# 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
__END__
James Edward Gray II
Hans Fugal
Kero wrote:
> >> May I assume then, that there are only timeslots of full hours?
> >
> > I assumed that from reading of quiz. It's probably an over
> > simplistic assumption, but I think it will do for this challenge.
> > P.S. Hans, feel free to jump in here and save me at any time... :D
>
> Isn't the problem in general NP hard? Meaning you have to make some
> simplifications to keep the input small, or apply some other
> restrictions to get the problem to P.
Well I'll take your word for it on the NP thing because I don't have
the brain cycles to spare at the moment. ;-) It is definitely not
trivial.
> Of course, it is also possible to generate input for which there is no
> solution. Then what? When to loosen bonus targets like regular times for
> a person and when to give up?
See below...
> I think everybody has to figure this out for him/herself.
I'm not clear what you mean by that. I think you might mean every
McDonalds manager has to figure this out him/herself. That's the
interesting thing here - lots and lots of people do this every single
day.
> Moreover, do not restrict the application to people and time, it can be
> anything and time (or even boxes and space if you can restrict the space
> to 1D meaningfully :)
Yes, it is essentially the knapsack problem with time dependence added.
> I can't suppress the feeling that the quiz is meant to pick a "nice"
> solution when there's plenty of solutions available. For which you need
> (a lot of) example input...
Yes and no. I alluded to the fact that people have minimal difficulty
doing this (although as you can imagine it is a common sore spot
between employees and employers) so that seems to suggest that one
approach would be an AI approach. We are looking for one of many
solutions. Ideally we find the optimal solution, but we're happy to
find a "good" solution. Your response has piqued my interest (I
unfortunately don't often find time to do these quizzes, even when I'm
the one who comes up with the idea. ;-). Here's how I plan to do it:
We want to search the solution space for good answers. First we need to
represent things, and my first idea here is a sequence of (day, hour,
person) tuples, where day is a weekday name, hour is something like
1300, and person is the name of a person. The sequence for a whole week
(with a 12-hour business day) is 72 tuples long, not too bad.
Next we need to have a way to know if an answer is good, and how good
the answer is. This is called a utility function in AI. Normally you
award points for things you like and demerit points for things you
don't like. Finding a good utility function is the artistic and most
important part of a search like this.
Now we can represent whole and partial solutions and measure their
utility. Now all we have to do is search. I'm guessing an A* search
will do the trick nicely (it usually does). If not A* then one of its
variants, probably. Or maybe greedy will do the job sufficiently well
for most purposes. All that remains is to choose a good heuristic, this
is the other artistic and important part of the algorithm.
Assuming we can find a reasonable heuristic and utility function, the
computer should be able to find us good solutions. If we can find
sufficiently good heuristic and utility functions, we can say the
solution is optimal - whatever that means. (In other words, if we knew
what optimal was in the real world for this problem, and we could
represent it with utility/heuristic functions, we could find an optimal
solution).
I hope to find the time to code this up, for the proof is in the
pudding. The only real question in my (perhaps over-confident) mind is,
will it fit in memory and time constraints? When you have a problem
where valid solutions abound and you're looking for a "good" solution,
the answer is usually that you can find better and better solutions
given enough time and memory, and hopefully you can find something good
enough given realistic time and memory.
Hans
Ruby Quiz
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"
include Comparable
next_hour
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:
# ...
attr_reader :name
def to_s
@name.to_s
end
private
# ...
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:
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:
# ...
# ...
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...