From: Nick
Subject: Time scheduling algorithm
Date: 
Message-ID: <1168905659.942014.104590@l53g2000cwa.googlegroups.com>
Hi all,

Im interested in the ideas you will generate on the following problem.
I chose to post this here since I have been trying to write this in
lisp (im a noob in every sense of the word).

Say you have 11 departments and each department has come up with their
own innovative brand of products and there is a scheduled presentation
day for all these products.  Each brand has 1 - 3 creators (a team)
that will be both presenting their product for one hour (to three
teams) and evaluating other products (each team evaluates 3 other teams
in 20 min intervals) for another hour. The presentation lasts 8 hours
and the goal is to have the presentation and evaluations back to back
(or as much as possible). Note that there could be as many as 140 teams
across different departments which all need to grade and be graded.
However, there are some restrictions:

1 - Certain departments can not grade/evaluate other departments.
2 - The teams have different hours of availability but should atleast
be available for 2 - 1 hour time slots to do the presentation and
evaluations.
3 -  Although rare, a team may have developed more than one product
across different departments and therefore that team would not be
allowed to grade/evaluate their own work (even though they dont belong
to that department).
4 - A team can only grade/evaluate another team once.

I can already sense the irritation among some of you but I can assure
you that even though I am a student, this is not a homework assignment
and I AM NOT INTERESTED IN ANY LISP CODE. I am merely fishing for
ideas/suggestions from you if you were faced with writing code to do
this scheduling. To be fair, I will outline my suggestion (which I
think isnt that good hence my post).

- Have a list (linked list) of all teams and their products
- Since the number of teams is not fixed, divide the number of teams by
total available hours and get how many evaluations take place each hour
(the flaw in this is that based on availability this number may not be
attained)
- Come up with a rule for interdepartmental evaluation to enforce
restriction 1.
- For each hour, go through the list and retrieve teams available at
that hour and form a new list.
- With the new list, generate evaluations as much as possible.
- Repeat for all available hours

The problem to my approach is that its not a guaranteed approach of
solving this problem. I would appreciate any help/suggestions you can
provide. I originally didnt want to seek help coz i wanted to figure it
out on my own but my arrogance was way ahead of my limited
understanding of coding/algorithms. Also, I wanted to get it done
before school started.

Thanks in advance

Nick../

From: ·····················@gmail.com
Subject: Re: Time scheduling algorithm
Date: 
Message-ID: <1168926436.304355.318300@s34g2000cwa.googlegroups.com>
> Say you have 11 departments and each department has come up with their
> own innovative brand of products and there is a scheduled presentation
> day for all these products.  Each brand has 1 - 3 creators (a team)
> that will be both presenting their product for one hour (to three
> teams) and evaluating other products (each team evaluates 3 other teams
> in 20 min intervals) for another hour. The presentation lasts 8 hours
> and the goal is to have the presentation and evaluations back to back
> (or as much as possible). Note that there could be as many as 140 teams
> across different departments which all need to grade and be graded.
> However, there are some restrictions:
>
> 1 - Certain departments can not grade/evaluate other departments.
> 2 - The teams have different hours of availability but should atleast
> be available for 2 - 1 hour time slots to do the presentation and
> evaluations.
> 3 -  Although rare, a team may have developed more than one product
> across different departments and therefore that team would not be
> allowed to grade/evaluate their own work (even though they dont belong
> to that department).
> 4 - A team can only grade/evaluate another team once.

Your problem smells like an NP-hard one (you might want to look this up
if you don't know what it means) and one with no guarantee that a
solution will exist.
This means that to find the optimal solution you *must*  use brute
force combinatorics although I would expect that you normally would
find a valid solution in polynomial time rather than exponential time.

Anyway, some brute force methods are stupider than others.  You want to
eliminate bad solutions as soon as they occur so your code should
probably  look like a bunch of nested loops of the form:

(loop (aref state team-number) across (possible-states team-number) do
 (when (test-state team-number)
             (loop (aref state (+1 team-number))...... ))

You can get code like this by using a recursive function or writing a
macro to embed loops within themselves which would be faster on the
innermost loops.

Good luck!

Chris
From: Willem Broekema
Subject: Re: Time scheduling algorithm
Date: 
Message-ID: <1168934607.037386.182890@v45g2000cwv.googlegroups.com>
Nick wrote:
> 1 - Certain departments can not grade/evaluate other departments.
> 2 - The teams have different hours of availability but should atleast
> be available for 2 - 1 hour time slots to do the presentation and
> evaluations.
> 3 -  Although rare, a team may have developed more than one product
> across different departments and therefore that team would not be
> allowed to grade/evaluate their own work (even though they dont belong
> to that department).
> 4 - A team can only grade/evaluate another team once.

That's an interesting problem!

In my eyes, a time-scheduling problem with such restrictions begs to be
expressed as a "constraint programming"[1] problem. Therefore I'd
formulate it using linear constraints on integer-valued variables, and
then use an existing solver to find a solution.

I'd suggest looking into Gecode[2], an existing c.p. solver in C++
under active development. Someone recently created CFFI bindings[3],
which means using Lisp you can instantiate a problem and add
constraints one by one, and finally command it to search for a schedule
that fits all requirements. The gecode library is called under the
hood, but everything you have to do is using Lisp expressions.

Alternatively, you could try Screamer[4], a Lisp library which offers
"non-deterministic programming". I think it should also be able to
handle these kind of problems.

[1] http://en.wikipedia.org/wiki/Constraint_programming
[2] http://www.gecode.org/
[3] http://common-lisp.net/project/gecol/
[4] http://www.cis.upenn.edu/~screamer-tools/screamer-intro.html

Cheers,
- Willem