[QUIZ] Scheduling (#42)

(James Edward Gray II) #1

The three rules of 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:

http://www.rubyquiz.com/

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) #2

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

···

On 13/08/05, Ruby Quiz <james@grayproductions.net> wrote:

The three rules of 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:

http://www.rubyquiz.com/

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.

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

(James Edward Gray II) #3

My solution produces output like the following:

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

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

(James Edward Gray II) #4

Here's one possible idea. What do you think?

James Edward Gray II

···

On Aug 13, 2005, at 3:08 AM, Brian Schröder wrote:

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?

---
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) #5

Interesting to parse. May I assume then, that there are only timeslots
of full hours?

regards,

Brian

···

On 13/08/05, James Edward Gray II <james@grayproductions.net> wrote:

On Aug 13, 2005, at 3:08 AM, Brian Schröder wrote:

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

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

(James Edward Gray II) #6

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

···

On Aug 13, 2005, at 3:01 PM, Brian Schröder wrote:

(Kero) #7

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

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 :slight_smile:

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

(Hans Fugal) #8

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

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. :wink: 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 :slight_smile:

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