Exam Scheduler Technical Manual

System Design

    As introduction before, the main goal of our system is to make a schedule for qualification examination of our department. The system needs user provide information like candidates' selection of courses and professors' expertise level of courses, then run the scheduling algorithm to get a "good" schedule, and finally output the schedule to users. Accordingly, the whole system can be divided to three modules: input module, scheduler module and output module.

    Input module reads some input file from users and set up the data consumed by scheduler module. Basically users should provide three files: candidate-course file which indicate 6 courses selected by each candidate, faculty-course file in which each professor expresses an expertise level for all courses and course file in which listed all possbile courses. Input module will construct all internal data structure to be used by scheduler module.

    Scheduler module runs on the certain scheduling algorithm to generate a possible schedule based on the information from input module. Our algorithm is sort of random. The basic point is we first assign a competent professor to each candidate for each selected course. Here a competent professor of one course means this professor has expressed at least 1.8 expertise level in this course. When we split 6 courses to 3 sessions, each session will have two competent professors who cover one course respectively, so the total competence of each sessions will be at least 3.6. A point here is that when we randomly split 6 courses to 3 sessions for each candidate, we do not decide the third professor besides two competent professors and leave it to the process of scheduling all sessions. The reason is to reduce the conflicts in schduling sessions otherwise we can't schedule many sessions at the same timeslot so that the total timeslots of the whole exam will enlarge. We will take greedy algorithm to schedule sessions. We know that there will be at most one third of total number of professors sessions simutaneously because no professor is allowed to attend more than one sessions at the same time. We search all sessions, and if the session will not cause conflicts with currently scheduled sessions, we schedule this session to the current timeslot. However, we don't schedule any sessions for one certain timeslot if the total scheduled sessions has reached upper bound. After we determine all sessions in this timeslot, we assign all rest of professors in turn to sessions' third professor. To balance the workloads of professors, we maintain a workloads array of professors. Whenever possible, we will first introduce those professors with less workloads so far. A interesting thing is that when we schedule sessions, it is possible that we cannot assign the third professor for some session. The reason is that we have to guarantee that one candidate is examed by 9 different professors so the rest professors will probably attends other sessions of the same candidate. In this case, we said that the scheduling failed. We do not guarantee that each round of scheduling will succeed.

    Output module is relatively simple. It is responsible to output the schedule to external files with human-readable formats. Basically it will output three files: candidate schedule file, faculty schedule file and workload file. In candidate schedule file, each line lists one session including the candidate name, two courses, three professors, date&time and location. Each candidate could look at this file to check his schedule. While faculty schedule file indicate all the sessions for one professor, so each professor will be present in the correct location in the certain time. As to workload file, it is only internally used by users. Since we will probably run many times of our scheduling algorithm, it is quite possible to output many potencial schedules. We will put the information of all schedules including workloads of faculty, minimum timeslots, minimum competence and average competence into the workload file so that users can decide a "best" schedule based on this file.

    The whole system just sequentially executes input module to make sure the data ready, then scheduler module to get a schedule, and output module to export it. Since our algorithm is sort of random, we will run our scheduling algorithm many times (for example, 10000). We could record some "good" schedules and leave users to decide which one is finally used. To evaluate a schedule, we first check how many timeslots it used. Since we hope the whole exam is ended as early as possbile, the less timeslot it used the better. Furthermore, we are very interested in the minimum competence of all sessions and average competence of all sessions in each schedule. Based on these three criteria, we can get some qualified "candidate" schedules. A point here is that we are no need to record all prospective schedules when we run our sheduling algorithm. The only thing we need to do is just record the random seed we used if we want to record the result of one round of scheduling. After we finish all rounds of running, we just use all these recorded seeds to reproduce the schedules and export them.

    Please check the individual module to learn details of our design.


Updated on April 23, 2000.