Greetings fellow monks,

I post this more as an intellectual excersize than a question. I've already developed one brute force solution to it and after I did I became curious as to what elegant solution others might think up.

Here's the setup

I am writing an online application that takes a list of workers and schedules them to work specific time slots within a dog show. The complication comes in that these same (some or all) workers are also performing in this dog trial during specfic time slots with one or more dogs. Here is a subset of what the database schema looks like in pseudo UML sort of way. 


person ---> has one or more skill
       +--> has zero or more dogs 

dogs --> have one or more show appearance (see events) 

show --> one or more rings 

rings --> one or more events

events -> have 5 to 10 worker slots 
       -> have aproximate start time
       -> have approximate end time

[download]
More closely the SQL tables sorta look like this in a very oversimplified way: 
;
; A person who has volunteered to help run the trial
;
create table person (
person_id     integer,
name          varchar(80)
);

;
; What skill(s) they have
;
create table skills (
skill_entry_id  integer,
person_id       integer references person(person_id),
skill           varchar(20)
);
;
; Their dog(s)
;
create table dog (
dog_id         integer 
dog_name       varchar(20),
person_id      integer references person(person_id)
);
;
; What rings are defined for this trial on this day
;
create table ring (
ring_id       integer,
ring_name     varchar(20)
);
;
; The events scheduled for that ring
;
create table ring_event (
ring_event_id   integer,
event_name      varchar(20)
ring_id         integer references ring(ring_id),
start_time      time,
end_time        time,
num_dogs        int       ; used to calc end_time
);
;
; When a given dog is scheduled to appear in any given ring
;
create table_dog_appearance (
tda_id       integer,
dog_id       integer  references dog(dog_id),
ring_event_id integer references ring_event(ring_event_id)
);
;
; What skills are needed for a given ring/ring event
create table workers_needed (
wn_id      integer,
skill      varchar(50),
ring_event_id  integer references ring_event(ring_event_id)
);

[download]
I've left a lot of detail out for clarity and brevity.

What has to happen here is each of the show rings needs to have workers assigned to work ringside for each event without conflicts. In other words I don't want to schedule someone to work ringside if they are supposed to be running their dog either in the ring event running in that ring or elsewhere. The result ends up in a table called "worker_schedule" that I've left out of this explaination for now.

I tried using a big SQL query to do this and couldn't quite wrap my head around the requisite SQL to make it happen. I'm not a SQL guru given that I've only been messing with SQL in a serious way for the last 4 years and then only sporadicly.

The method I did come up with was brute force at best. Essentially I read in all the people into an array and then loop through all their dogs and see if they are showing in an event that overlaps the one I'm trying to schedule them for. It is time consuming but gets the job done.

Any ideas anybody?

In reply to Interesting scheduling application problem. by blue_cowdawg

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.