blue_cowdawg has asked for the wisdom of the Perl Monks concerning the following question:

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?

Replies are listed 'Best First'.
Re: Interesting scheduling application problem.
by kvale (Monsignor) on Mar 13, 2005 at 20:08 UTC
    Forgetting SQL at the moment, you have workers, dogs, participation events and ringside events. It sounds like participation events are fixed and dogs have already been assigned to participation events by some algorithm. That means that workers have been assigned to participation events along with the dogs. And we'll assume that if a worker has more than one dog, then they have resolved which participatory events they will attend with each dog.

    So what we are left with are workers, with some free spots available, and 5-10 ringside spots available for each event. There are many ways to go about solving this. If you want to minimize the number of different people working ringside, for instance, this problem becomes the vertex set covering problem. A greedy algorithm to solve it is provided by Algorithm::SetCovering. For other optimization criteria, other schemes need to be used.

    If one can formulate the optimization criteria as an numerical optimization function, then a genetic algorithm can be useful. see the thread Looking for help with AI::Genetic and classroom scheduling for good ideas.

    Update: fixed typos and improved wording.

    -Mark

[reply]
Re: Interesting scheduling application problem.
by gam3 (Curate) on Mar 13, 2005 at 21:24 UTC
    I would make the following change to you schema. Since # of dogs in a ring can be calculated and you say that end_time is detirmined by the # of dogs. 
    create table ring_event (
ring_event_id   integer,
event_name      varchar(20)
ring_id         integer references ring(ring_id),
start_time      time,
time_per_dog    time,
);
-- you can then use 
select a.ring_event_id, a.event_name,
       a.ring_id, a.start_time, 
       ADDTIME(a.start_time, time_per_dog * count(b.dog_id))
         as end_time, count(b.dog_id) as num_dogs
 from ring_event a, tda b
 where a.ring_event_id = b.ring_event_id 
 group by a.ring_event_id;
-- to get the end_time and number of dogs.

    [download]
    A picture is worth a thousand words, but takes 200K.
[reply]
[d/l]
Re: Interesting scheduling application problem.
by talexb (Chancellor) on Mar 13, 2005 at 20:25 UTC

    I think kvale has already described the outlines of a solution, but I would create a 'schedule' for each person, then based on that information find out when they are free. Once you have that information, you can assign people to rings, starting with the time slots that are hardest to fill (that is, have the fewest people), and move from there to the time slots that are the easiest to fill (the ones that have lots of people).

    Alex / talexb / Toronto

    "Groklaw is the open-source mentality applied to legal research" ~ Linus Torvalds

[reply]
Re: Interesting scheduling application problem.
by salonmonk (Beadle) on Mar 14, 2005 at 12:59 UTC
    Brute force is certianly not the way most people go for scheduling - merlyn asked a similar question not so long ago. Genetic Algorithms are the way forward - and are not difficult to programme, despite the rather intimidating name. Check http://perlmonks.org/index.pl?node_id=432801 to see the replies given. I can post more pseudo GA code if this piques your interest.
[reply]
Re: Interesting scheduling application problem.
by perlfan (Parson) on Mar 13, 2005 at 18:07 UTC
    Brute force is typically the way to go for scheduling. I seriously doubt you can do what you want with SQL.
[reply]
Re: Interesting scheduling application problem.
by gam3 (Curate) on Mar 18, 2005 at 04:13 UTC
    This is a good as I could do with MySQL 4.1.10 
    CREATE TEMPORARY TABLE Temp1
select a.ring_event_id, a.event_name,
       a.ring_id, a.start_time,
       ADDTIME(a.start_time, time_per_dog 
               * count(b.dog_id)) as end_time,
       count(b.dog_id) as num_dogs
 from ring_event a, tda b
 where a.ring_event_id = b.ring_event_id
 group by a.ring_event_id;

CREATE TEMPORARY TABLE Temp2
select a.ring_event_id, a.event_name,
       a.ring_id, a.start_time,
       ADDTIME(a.start_time, time_per_dog 
               * count(b.dog_id)) as end_time,
       count(b.dog_id) as num_dogs
 from ring_event a, tda b
 where a.ring_event_id = b.ring_event_id
 group by a.ring_event_id;

select ring_event_id, person.name, group_concat(skill.skill) as skills
  from person
  join skill_entry on person.person_id = skill_entry.person_id
  join skill on skill_entry.skill_id = skill.skill_id
  join ring_event
 where person.person_id not in (
  select person.person_id
    from tda a
     join dog on a.dog_id = dog.dog_id
     join person on dog.person_id = person.person_id
     join Temp1 b
       on a.ring_event_id = b.ring_event_id
     join Temp2 c
       on (b.start_time < c.end_time and b.end_time > c.start_time)
    where b.ring_event_id = ring_event.ring_event_id )
 group by ring_event_id, name
 order by ring_event_id, name;

drop table Temp1;
drop table Temp2;

    [download]
    The subselect is getting all people that are busy while ring_event.ring_event_id is in progress. And then the main select gets all the people that aren't busy.
    A picture is worth a thousand words, but takes 200K.
[reply]
[d/l]

Back to Seekers of Perl Wisdom