Subject: Timetabling summary ...

From: Saleh Elmohamed <[email-masked]>
Date: Wed, 7 Oct 1998 18:07:57 -0400 (EDT)

Hi Bart, Carla,

Sorry for the delay in sending you this. have been pretty busy
with the class.
Well, here is something to start with. I sort of put it together
quickly so apologies if I missed something.

-saleh
----------------------------------------

                   Course Timetabling

Here is a rough outline of the timetabling we dealt with. The
objective of the problem is to establish the schedule of lectures
subject to (or accounting for) individual student registration and
professor as well as classroom availabilities.

* Lectures of different length are allowed.
* Starting times are resources and lectures are items to be allocated
to these resources.

* Each lecture has a set of admissible times associated with it, for
example (Ji) is the admissible starting times for lecture (i).

* For (i=1; <= n; i++) &&  (j in Ji)
      
	x(i,j) = 1  if lecture i start at j
               = 0  otherwise.

* For professor preferences, the objective function is something like:

        f(x) = Sum_{i=1 ...n}{j in Ji} ( c(i,j) * x(i, j))
 where c(i,j) is the cost of starting lecture (i) at (j) specified in
terms of professor preferences (c(i,j) = 0 if (j) is the most
preferred starting time for lecture i). Many lectures will come with
pre-determined starting time which will have to be considered first.

* A first set of side constraints is specified to eliminate 
conflicting situations where students or professors are involved in
classes taking place simultaneously (this considered to be hard
constraint). One possible definition of this is:

 Gamma(ij) = {(k,l): classes i and k have students or professors in
                     common, and they overlap in time if class i starts at
                     j and class k at l}.

So we could may be specify the conflicting constraints as follow:

   x(i,j)x(k,l) <= 0  where (k,l) in Gamma(i,j), 1<= i <= n, and j in
    Ji.

* Other constraints introduced to account for classroom
availability. Take the overall set of available classrooms and
partition them into several subsets each of the same type. Let say
define

 B = number of classroom types
 Ub = number of classrooms of type b, 1<= b <= B.

Now, for each class, a unique classroom type is specified. So we
define something like this:

  Kbt = {(i,j): class (i) requires a classroom of type (b) and takes
                place during teaching hour (t) of the week whenever its
                starting time is (j)}. 

* The class availability constraints can be written as follows:

 Sum_{(i,j) in Kbt} x(i,j) - Ub <= 0  such that  1<= b <= B  and
                                                 1<= t <= T.
where T is the total number of teaching hours of the week.

A summary of the course timetabling problem is as follows :

   Min Sum_{i=1 ...n}Sum_{j in Ji} c(i,j) x(i,j)

                    subject to

    1. x(i,j)x(k,l) <= 0   where (k,l) in Gamma(ij), 1 <= i <= n,
                                 and j in Ji
    2. Sum_{(i,j) in Kbt} x(i,j) - Ub <= 0   such that 1<= b <= B and
                                                     1<= t <= T.
    3. x in X(1).

Now, we sort of formulate the associated problem of handling any
constraint violation. For this, various weights are used to indicate
the relative importance of violating the corresponding constraints.

For clashing constraints, the weights account for the length of the
clash and the number of individuals involved. So we can define that 
as follows:

 L(ijkl) = length (in minutes) of the conflict (k,l) in Gamma(ij),
                                  1 <= i <= n, and j in Ji.

 delta(ik) = number of students taking both lectures (i) and (k), 
                                  1 <= i <= n, and  1<= k <= n.

           |
           |  M + delta(ik)   if class i and k have professors in common.
           |
 phi(ik) = |
           |
           |  delta(ik)       otherwise.
           |
                                           1 <= i <= n, and
                                           1 <= k <= n

 where M is a parameter to indicate the relative importance of
conflicts due to professors.

Then, we have the penalized version as follows:

  Min_{x in X(1)} Sum_{i=1 ... n}Sum_{j in Ji} [ alpha c(i,j) x(i,j) +
         Sum_{(k,l) in Gamma(ij)} phi(ik) L(ijkl) x(i,j) x(k,l)] 
                           
                            +

         rho Sum_{b=1 ... B}Sum_{t=1 ... T}  Max[0, Sum_{(i,j) in Kbt}
                                             x(i,j) - Ub].

The weight parameters alpha, rho, and M are selected according to the
specific context. For instance, if the priority is to reduce the
conflicts, then alpha and rho take smaller values.

Sample of hard constraints:

Category 1: Must not overlap in time -

 * classes taught by the same professor.
 * classes held in the same room
 * a class and a recitation or lab of the same class.

Category 2:

 * A class cannot be assigned to a particular room unless the capacity 
   of the room is greater than or equal to the class enrollment.

  Let Rc = room capacity,
      Ce = class enrollment,

  The assignment always seek to minimize the difference between Rc and 
  Ce. A cost (Ec) is associated with any violation. 

  One representation of this constraint and hence the derivation of
  the cost (Crs) is roughly like this :

          | Ce - Rc              if Ce > Rc
          |
          |
    Crs = | tanh((1.0 - Ce/Rc - beta) tau pi)(Rc - Ce)
          |                                              otherwise.
          |

  parameters beta and tau are set to small values (0.5, 0.8) or
something close to that.

Sample of medium constraints:

Need to be minimized and preferably --> 0

 * avoid time conflicts for classes with students in common ...
 * eligibility criteria for the class must be met.
 * enrollment of athletes in classes that conflict with their
   sport practice, etc.

Sample of soft constraints:

 * for each student, balance the three-day (mon, wed, fri) as well
   as the two-day (tue, thu) schedule.

 * balance or spread out the lectures over the week.

 * balance enrollment in multi-section classes.

 * professors may request periods in which their classes are not
   taught.
 * specify lunch and other break times.

 * professors may have preferences for specific rooms or type of
   rooms.
 * minimize the distance between the room where the class is assigned
   and the building housing its home department.

Some soft constraints may have higher priority (thus higher cost) than 
others. For example, preferences involving professors will have higher 
priority than those involving students.

The cost function measures the quality of the current schedule and
generally involves the weighted sum of penalties associated with
  class constraints, professor constraints, student constraints, room
constraints, and some other kind of constraints.

The aim is to minimize the cost function.

                  --------------------------
                  --------------------------

Kind of data we have:

Inclusion data:
--------------

college_x   dept1 dept2 dept3 ...    (depts belonging to college_x)

Building and Room data:
----------------------

bldg_name   
room_number    
room_capacity   
room_type  
scheduling_priority

If available, name(s) of dept(s) it is assigned to.

Dept building preference:
------------------------

This is according to either distance from the department or teaching 
resources a particular bldg has.

dept name     option 1   option 2     option 3  option 4 ....
--------      --------   --------     --------  --------
CS            bldg_A      bldg_B        bldg_C     bldg_E  ...

Distance data:
-------------
dept_1 (char *)    bldg_1 (char *)    distance (int)
dept_2 (char *)    bldg_2 (char *)    distance (int)
...

etc.

Professor-class data:
--------------------

***if already available***

prof_name   class_name  meeting_time  meeting_day class_type
room_type_requested  enrollment  college_name   dept_name

prof_name   class_name  days_per_week meeting_day meeting_time
class_type room_type_requested_1 room_type_requested_2 ... enrollment
  college_code   dept_code

...

etc.

Class data:
----------

class_name  class_type  associated_class_1  associated_class_2
associated_class_3   max_enrollment  type_of_room_needed  
max_meeting_days_per_week  projected_meeting_time   duration

...

etc.

example: 

BIO-121-001-64510   lecture   section   laboratory recitation
398   AUDITORIUM   2   01040   01135   55 

Professors data:
---------------

1. option_1_professor  option_2_professor(if available)
option_3_professor(if available)   class_name

2. ...
3. ...

etc.

Students data:
-------------

student_name  number  major  dept  academic-status   

    main selection: class_1 class_2 class_3 ...   

    optional(1): class_1 class_2 class_3 ...

    optional(2): class_1 class_2 class_3 ...

    optional(3): class_1 ...

...

...

etc.

-----------------------------------------------------------

This is a rough summary of the whole thing. If you would like more
details on a specific constraint, etc. let me know. 

Hope we can come up with something interesting with this.

Will talk to you soon.

---

From: Bart Selman <[email-masked]>
Date: Wed, 7 Oct 1998 18:26:49 -0400 (EDT)

looks good. i'm traveling next week. will look at this when i get
back. -- bart

---

From: Carla Gomes <[email-masked]>
Date: Wed, 7 Oct 1998 18:29:58 -0400 (EDT)

Hi Saleh,

Sorry for not having got back to you earlier, with the references,
but I was traveling.

Here is the url:

	http;//hermes.dis.uniroma1.it/~aschaerf/index.html.

The timetabling paper is in "selected publications".

Thanks for all the info on the timetabling - wow, it will keep us busy
for a while.  I'll go over it and probably have lots of questions ...
Bart is also going to be away, so let's see if you get back to you
within two weeks.

-- Carla

---

From: Carla Gomes <[email-masked]>
Date: Mon, 19 Oct 1998 13:51:54 -0400 (EDT)

|>BTW, did you read that ijcai paper? I'm currently going over

a long time ago...i'm afraid i don't recall any details...

--carla