The time table puzzle

A school timetable is quite a problem to solve. The details that are involved range from mandatory requirements to nice to have. Think of such things as courses that must take place but also it would be nice to not use the last hours on a day for a theoretical course.

Combining these requirements into a rock solid algorithm is hard if doable at all. There are proofs like the one by Dr. Ir. Roy Willemen that this problem is NP-complete which is the mathematicians way to say that it is unsolvable within reasonable bounds.

A game like approach

A timetable can be seen as a multidimensional grid in which the required entities must be placed. These entities can have conflicting properties which limits the freedom of placement in that grid.

To make the whole more concrete: these entities or building blocks in a school timetable are called sessions which have the properties

  • A name like Concurrency. This first property is the only one that can be used freely
  • A non-empty set of teachers. Example: ODE, HOM and some 60 more
  • A named non-empty group with atributes size and members, examples: TIKA, TIKB and some 60 more
  • Room requirements such as size and equipment
  • The length of a session, expressed in standard time units like one class-hour. Typically 50 minutes or so. Students and Teachers tire easily.

To be able to plan a session, the people (teachers and students) as well as the resources (rooms and equipment) must be available. In the model we propose, the resources are the most scarce and fixed (you cannot simply add or remove class rooms.) The sessions have to be placed in the time-table, of which two dimensions are the day and the timeslot on that day. The third dimension of this table are the resources, i.e. mostly (equiped) rooms or more abstractly locations

The purpose of this exercise is to design a program that optimally uses parallel hardware, in that the highest number of valid an qualified plans should be computed, such that these plans can be presented, ranked and chosen (by a human). The approach is that we simply try to throw together valid plans from a randomized set of all sessions. If the plan produced is valid, it is measured or qualified. This qualification may have several dimensions.

Requirements and design hints

Requirements

  • A Session can have different lengths with different requirements (rooms, groups and teachers) in the timeblocks. This allows the planner to start a session with a theory block in one room and the lab session in another room with a different set of teachers directly afterwards. Such extended block may not cross a day-border.
  • Any human (students and teachers) may not be planned for more than 5 consecutive hours. Then either a break (pause) or the end of the day plan is due. This forces at least one break in one of the 4th, 5th or 6th hour for teachers and classes that have a long day.
  • The resources can be preoccupied, meaning that they are not available on certain moments in the grid. This allows for teachers or students working part time or rooms being let for other extra curricular purposes.
  • A simplyfied class model is als available: use this model VPP Model. The most important diagrams can also be read with a svg capable browser like firefox:
    1. Overview
    2. Grid
    3. Resource management through sets
    4. Resource registry
  • The input data (sessions to be planned, available rooms) will be provided in csv files similar to this one for the plannable sessions and this one for the locations. Every resource will have a unique identifier. You can find these files in the repository.
    Since concurrency is not an XML parsing course, we will provide an Abstract Factory that will provide methods the signatures
    List <Location> getLocations(String locationFilename);
    List <Session> getSessions(String sessionFilename);
  • The order in the grid dimensions will be room, time and day.
  • The output data for each plan will be one string per plan, in the order created by concatenating the pairs room:session-identifier with a semi-colon (';'). format room1:session-id1;room1:session-id2;...
  • At the end of the string, the quality metrics is appended, using the '=' equal sign to separate the plan from its quality metrics. The order of the metrics is fixed and will be provided.

Your task

This years exercise is still in an experimental stage.
Your tasks consist of the following:
  • In your group, investigate the code you find in the repository.
  • Annotate the classes you find with appropriate annotations using the annotations jar form the JCIP web site.
  • The code you get is incomplete and immature at the same time. Many classes are untested (some of which may remain so. Which ones?
  • Complete the code in the sense that you create solution finder tasks which produce a valid schedule per task and combine the found solutions in a data structure you see fit.
  • Configure you executor
  • Next week (week 2 2010) we will try to run your application on our multi core Suns sparc machines (Max 32 thread in hardware) and test the application for scalability.

Hints

  • The key ingredient is the Data model and the way you can test possible combinations or availability of a required resource(rooms, room sizes, persons) for a session.
  • When using the proposed grid, for each day add a column that holds the preoccupations. It is wise to also keep book (=cache) of the resources already planned on a certain hour in a day. You can call this Occupied. Initially you can initialize Occupied with the preoccupations. This improves the search for fit of a block to be dropped.
  • The ingredients for a well tuned system are (of course) the highest possible parallelism. It is possible to use a private grid for each thread that calculates.
  • Using or implementing a fast set implementation will help very much when determining the availability of resource and of claiming a resource.
  • A preliminary data set can be found int the repository:
    1. groups.csv: Classes/groups.
    2. modulesActivities.csv: activities that have to be planned
    3. tutors.csv: Tutors
    4. locations.csv: Rooms
    They are all in csv format. Creating objects from those should be easy.
  • Of course some sources to start with, also in the repository. Start by making an export of the sources and then import them in your own project.