2) Which algorithms do you use in your timetable (such as genetic
algorithms....)?
None - all done by hand. We have looked at using GATT, but it was too hard to
configure it to be 100% useful.
3) Do you have any program to produce the timetable?
No - I only have a program that checks for errors. It generates all the room,
staff and student timetables, plus the list of clashes/errors, all available
via my webpage.
4) Which algorithms or methods you find is most important To produce a
timetable?
Divide & conquer! O(e^n) is only possible if you can reduce n.
Then I use combinatorial methods (write out all possible combinations, or
something similar) and delete the ones that are invalid for some reason (e.g.
lecturers not available).
5) How do you evaluate your timetable?
Qualitatively rather than quantitatively.
If everyone can get to their lectures & labs it is a success.
(our timetable is so tight that this is not possible!)
Even better if we can avoid unpopular times, but that turns out not to have been a success this year - I did it, but students preferred to move the lectures back to those times rather than not be able to get to them at all because they clashed with something else.
6) Do you know any methods like a data mining for evaluating or construct
the timetables?
No. I can't see the relevance of data mining, probably because I don't really
know anything about it.
7) What do you think about the Cost function or Mathematical methods to
evaluate a timetable?
What should a cost be? The only thing I can think of is the number of students
(or staff) that can't get to a lecture because they have to be in 2 places at
once, and by definition we have to make this number as close to zero as
possible. I suspect at the moment that it is about 5 or 10, out of a maximum
600 students * (approx) 20 hours a week * 2 semesters a year = 24000.
The problem is that we don't know for certain what the students actually want to do until a fortnight into the semester, when they finally tell us for definite what they are doing, but then they don't bother to say what they would prefer to do if only the timetable allowed them! Before then, we just have a guess from about 1/2 or 2/3 students at May as to what they want to do the following year, but we don't know about students taking a year out, or coming in next year etc.
So although we would like to be able to check this, in practice it is so inaccurate that it is useless (noise >> error signal), or else it just tells us that students only attend lectures they can get to.
4) Which algorithms or methods you find is most important
Divide & conquer! O(e^n) is only possible if you can reduce n.
Could you explain more?
i.e. taking the worst constraints first - e.g. allocating room 1.1 - and then
slotting in the other room allocations around it, as there are more smaller
rooms than I need.
> Then I use combinatorial methods (write out all possible combinations, or
> something similar) and delete the ones that are invalid for some reason
> (e.g. lecturers not available).
e.g.
the lab in the 1st semester of the 1st year
Are you using actually graph colouring algorithms for this problem?
No. It is all done with paper & pencil (or text-editor).
how flexible is your timetable? for example if
one lecture become a ill, how do you can cover or reschedule that class.?
All I do is create the initial timetable. It is up to others to cope with
unexpected problems like someone being ill - not like a school timetable.
5) How do you evaluate your timetable?
Qualitatively rather than quantitatively.
What do you mean by that? Timetable may be feasible, but it doesn't mean the
best? For example, if I give you two timetables (both feasible) for your
department, how do you know which one is better?
Our timetable is so difficult that almost any solution is acceptable, but you
are right, I do make choices between alternatives. e.g. I have tried to avoid
unpopular times, but that has not worked very well. I try to make sure that,
if students have to come in to an early lecture (9am or 10am) then they have 2
or 3 lectures in a row, so there is no temptation to miss 1 lecture to get
several extra hours off. Similarly, I try to avoid situations for students
with activities early & late but with a big gap in between. It is all done in
my head, with not much written down. I find this very hard to get right,
because it is a fuzzy constraint - how big is "a big gap".
> How do you can reduce the gap in your timetable?
> for example offer the timetable in 3 days rather than 4 days.
That is impossible, so I haven't considered it. I do try to allow for staff
requirements, like having a specific day off for research (but I have no easy
way of giving them any 1 day off). As noted above, I try to avoid gaps in
various places for students.
7) What do you think about the Cost function or Mathematical methods to evaluate a timetable? What should a cost be? Could you please look at following method and let me know your idea about that
4.11.5 Mathematical model Tripathy [Tr84] describes the application of binary integer linear programming to the school timetabling problem. This may be easily adapted to the examination scheduling problem as follows [TT026].We define yik=1 if class i is scheduled in period k, or 0 otherwise, Cik to be the cost of scheduling class i in period k and Xij if class i conflicts with class j. We also define the number of class to be E and the number of possible periods to be P. E p We wish therefore to minimise SUM SUM Cik yik (1) i=1 k=1 p subject to SUM yik =1 i=1 to E (2) k=1 E E p and SUM SUM SUM yik yjk Xij =0 (3) i=1 j=1 k=1 Equation 1 thus gives us a cost rating if we choose to use the timetable, equation 2 specifies that each class/exam should be scheduled exactly once and equation 3 specifies that no two conflicting course/exams should be scheduled at the same time. Other constraints, for example a maximum number of students in any one period, may be similarly written in this very precise fashion. 4.12 Good and bad timetables Two important measures of timetable quality relate specifically to its feasibility and arise directly from the graph colouring and bin-packing problems classified in the previous section as NP-complete. These are the requirements that no student is required to sit two or more exams simultaneously and that there must be sufficient seats available for the number of students scheduled. As has been said, a timetable that satisfies these constraints is considered feasible but this does not necessarily mean that it is sufficiently good to be used by an institution. No institution would wish to use an infeasible timetable as it is defined above.I don't have a constant cost Cik - this is essentially zero. What I have is a variable cost, depending upon the rest of the timetable (e.g. Cik = 0 if class i+1 is at k+1, but = 1 if class i+1 is not at k+1 - except that I mean any of the other classes taken by the same group of students, not just class i+1, and then there is the problem of ensuring that students get a lunch break!)I don't think I can obtain (3) in general - there are always some clashes, that I am trying to minimise, and they have an associated cost, which is proportional to the number of students doing that combination of courses.
However, there are also similar constraints to (3) for rooms and for staff, as well as just for students.I do have to take the number of seats into account. Normally, I take this as a absolute restriction (i.e. I MUST NOT HAVE more students than there are seats) rather than anything more relaxed, particularly in working out how to use the biggest lecture theatre (1.1), and the smallest lab (Eng), but I tend to get sloppier about this in the middle, partly because I have no choice as the rooms are of a certain size, and partly because of "noise" in the number of students doing each course.
I prepare list of the material, which every one need to start timetabling. Could you please check it for me, whether I need any more material or not.Here are some CS@MU definitions that may help:
A course unit = e.g. 24 lectures and 5 labs and 5 examples classes or tutorials (used to be called module).
A programme of study = e.g. 5 course units per semester chosen from a dozen options (used to be called school).1)List of all of the course, which department will offer in each semester.
I assume this is programme of study, or programme + year. (Some programmes are just starting, or just finishing, so not all years exist.)2) List of the modules for each course, which should be schedule for first and second semester, and also how many hour each module need.
I assume this is course unit.We also need to know what components (lecture, lab, examples etc.) each course unit consists of, and how many instances of each (2 per week, 1 per fortnight, etc.) and how long each instance lasts (1/2/3/4 hours) and how many repetitions (e.g. lectures happen once, each lab is repeated 5 times, each examples class is repeated 4 times). For activities that happen per fortnight, we need to know if there is a preference for a particular week in each fortnight (e.g. to get enough lectures in before the first lab). (Some lecturers prefer one 2-hour lecture, most prefer two 1-hour lectures on separate days.)
The number of repetitions depends on how many seats we have for a particular activity and how many students need to do that activity, although I try to stick to one particular number of repetitions per student year for the majority of course units so that I can interleave the different groups of students into different rooms. (e.g. mainly 4 repetitions for 1st year and 3 for 2nd year, but many activities don't follow this plan.)
3) list of the group of student, who take the module.
I think this is equivalent to (1).The extra information we need is the likely number of students who choose/ have to take the course unit, to match up to (6) - we would also like to know the combinations of course units that students have chosen.
4) list of all of the lecturer, which shows who available to offer which module.
For us, the lecturer(s) for each course unit is fixed (assuming it is known at all!). For other departments, maybe there are several possible alternative lecturers, or maybe even a course unit will be run more than once. We run most (but not all) labs and examples classes several times (within the same week or fortnight), but we normally only give lectures once a year.5) Availability of the lecturer.
6) list of all of the available room for each semester with capacity of each room.
Yes7) list of all of the facility for each module.
Do you mean what lecture/lab facilities e.g. projector in a lecture, or software in a lab? We certainly need this, but I tend to go directly to the end-product, which is a list of rooms that can be used for each component (lecture, lab, etc.) of each course-unit. Some staff impose constraints e.g. the lecturer who gets a migrane with florescent lights so will only use rooms with windows. Some activities (tutorials) don't need a room, as we just use staff rooms. I find that it is important to sort out the activities that can only happen in 1 room first (i.e. in 1.1 and the labs).8) list of the group of student in each course(Number of student, who register for each course).
See (3), but for course units, not programmes of study (except in so far as that tells you how many students will be taking compulsory course units).9) How many hours is available for each week.(One row timetabling form, which it should schedule for these semester).
10) start and finish time(for example 9-5:30)
I need to know how many slots are available each day e.g. Mo/Tu/Th/Fr=8, We=4 At the moment those slots are 1 hour long, but I suppose they could be e.g. 45 minutes. Equally, we might start lecturing on saturday, or stop lecturing on friday. I really only care about days so that e.g. I don't split a 2-hour lab across 2 days, and I don't have 2 lectures for the same course-unit on the same day. I also need to know so that I can try to make most use of the "best" slots e.g. 10am-1pm.11) Date of start and finish of semester.
12) vacation time(Christmas time and Easter time)
11+12 don't really affect me, except to do all the EXTRA timetabling that I haven't mentioned yet to get in introductory activities at the start of the year etc., that can be scheduled e.g. in the weeks when the lectures have started but the labs haven't yet.13) Lunch time
This is not fixed, I just have to make sure that each student has 12-1 or 1-2 free on every day except wednesday (i.e. slot number 4 or 5 of the 8).14) Professor Meeting
What is that?15) Avoid time(should not schedule) and available time.
How is this different from (5)? If you mean for students, then I certainly need to know when non-CS activities are happening, that our students have as likely options or as compulsory (e.g. AI -> PS, CM -> MT, CSwBM -> BM/AF) and when other students are free that are supposed to come to our activities (e.g. ABIS, EE)16) copy of all of last year timetable's course.
Not necessary, but can help as a sanity check.