Subject: Question about the difficulty of a timetabling problem.

From: Bryan Norman <[email-masked]>
Date: Fri, 6 Nov 1998 16:01:38 -0500 (EST)

Hello, I am trying to understand the complexity of certain timetabling
problems and was hoping that people on this list could help me.

If I have a problem with the following characteristics:

1. I have five periods (days).
2. I have classes that can be one or more of the days (up to five)
   and I know which periods the classes are on. For example,
   class one may be on days 1 and 2, class two is on days
   3, 4, and 5, etc. Note the classes always span adjacent days
   (no 1, 3 combinations for example.)
3. I have a pool of teachers and each teacher can teach some subset
   of the classes. For example, teacher 1 can teach courses A, B, and
   C but teacher 2 can teach courses A, B, D, E, and Z, etc.

If I want to know if there is a feasible assignment of teachers to
courses is this problem NP-hard?

Does the complexity (in terms of NP-hardness) change if I let the days
of the courses be a variable? (I know the problem becomes
more difficult - what I am getting at is if the above problem is not
NP-hard does changing characteristic 2 result in a problem that is NP-hard.)
In characteristic 2 above I assumed that
we knew what days the course would meet on. What if I just knew the duration
of the course but had the flexibility to change its starting date?

Please reply by e-mail.

Thanks in advance,

Bryan 

*********************
Bryan A. Norman, PhD.
Assistant Professor
Industrial Engineering Department
University of Pittsburgh
1033 Benedum Hall
Pittsburgh, PA 15261
PH:  (412) 624-9841
FAX: (412) 624-9831
email: [email-masked]
*********************