Cotiro 0.4 Manual

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

For details on the GPL and what rights it gives you, refer to the included GPL.txt.

Table of Contents

What Does This Program Do?
How To Use This Program
Constraints
1. "Hard" vs. "soft" constraints
2. What Constraints Are Imposed
Developers: How To Build Cotiro
Frequently Asked Questions
Credits

1. What Does This Program Do?

The goal of this program is to produce a time and room schedule for college courses, given a set of available rooms, courses, and teachers. This may seem trivial, but this system takes into account all sorts of factors, such as the fact that a professor can only teach one class at a time, a class must fit in the room it is assigned, and so on. For details on all the contraints imposed by the system, look at the section on that topic.

This system was intended as a research system into constraint satisfaction (a field of artificial intelligence), so it may lack many production-caliber features that you desire. You are invited to email me, and if I have time / see enough interest in this program, I may very well make a new version which incorporates your ideas plus some of my own. Or, the source code is available (under the GPL license), so if you are motivated enough you can add needed features yourself. But the thing to remember is, this was never intended for end-use as-is. I make no warranty that it works 100% correctly, or has 100% of the features it should. It is, however, pretty darn good.

For more details about this program, be sure to read the paper I wrote about it, available on my website: http://www.leedberg.com/glsoft

2. How to Use This Program

Using this program is pretty simple. You just create a series of XML files that supply the information about the course scheduling problem, run the program, and a schedule will be output. Below, we discuss what files need to be created, and what they contain. It should be noted that this program ships with examples of all of these, so you can also look at the included data\schedules.xml, data\courses.xml, data\rooms.xml, and data\teachers.xml files to see the formats. Or, you can actually just run the program on these example files to see it produce an example schedule.

2.1 Defining the Schedule Parameters

The first thing to do is to define the different possible schedules that classes can be scheduled according to. For example, you may want to allow two types of schedules -- a one-hour-a-day Monday-Wednesday-Friday schedule, and a ninety-minute-a-day Tuesday-Thursday schedule. For each possible schedule, you will define some overall parameters. Namely, the days of this schedule, the start of the day, the end of the day, the length of a class period, and the length of time in between class periods. You must have at least one possible schedule, but you may define as many as you want. When producing a final schedule, Cotiro will only put classes on one of the schedules defined here.

To define possible schedules, edit/create a file called "schedules.xml" in the "data" directory of the Cotiro distribution. Probably the best way to learn how to construct this file is simply by examining the example that ships with Cotiro, and starting from there. If you are fluent in XML, you may benefit from reading the schema, which is "resources\schedules.xsd".

Beyond the example and schema, I will also outline the file structure here (and in doing so will assume no prior knowledge of XML):

First, the schedules file always starts with the line:

<schedules xmlns="http://www.leedberg.org/cotiro">

and always ends with the line:

</schedules>

In between these lines, there will be one "schedule" section for each possible schedule you want to define. Each schedule section starts with the line:

<schedule>

and ends with the line:

</schedule>

In between these lines, there is one entry for each of the scheduling parameters mentioned above. They can be in any order, but all must exist. To define the days for this schedule, enter a line with the following format:

<days>DAYS</days>

where you would replace DAYS with a sequence of letters that define the days. Here, you use "M" for Monday, "T" for Tuesday, "W" for Wednesday, "H" for Thursday, and "F" for Friday. For example, you may define this to be "MWF" (without the quotes).

To define the time of day that classes start, enter a line with the following format:

<dayStart>START_TIME</dayStart>

where you would replace START_TIME with the actual start time, in 24-hour format (i.e., no "AM" or "PM"). To define the time of day that classes stop, enter a line with the following format:

<dayEnd>END_TIME</dayEnd>

where, like above, you would replace END_TIME with the actual end time, in 24-hour format. Classes will only be scheduled within the timespan defined by these two times.

To define the length of a class period, enter a line with the format:

<courseDuration>LENGTH</courseDuration>

where LENGTH is the length of class periods, in minutes.

To define the amonut of time in between class periods, enter a line with the format:

<courseBreak>BREAK</courseBreak>

where BREAK is the number of minutes between the end of one period and the start of the next. This, of course, can be 0 if there is no break between class periods.

An example of this file is:

<schedules xmlns="http://www.leedberg.org/cotiro">
  <schedule>
    <days>MWF</days>
    <dayStart>8:10</dayStart>
    <dayEnd>20:00</dayEnd>
    <courseDuration>60</courseDuration>
    <courseBreak>10</courseBreak>
  </schedule>
  <schedule>
    <days>TH</days>
    <dayStart>8:10</dayStart>
    <dayEnd>20:00</dayEnd>
    <courseDuration>90</courseDuration>
    <courseBreak>10</courseBreak>
  </schedule>
</schedules>

2.2 Defining Courses

This first thing to do is to define what courses are offered. To do this, edit/create a file called "courses.xml" in the "data" directory of the Cotiro distribution. Probably the best way to learn how to construct this file is simply by examining the example that ships with Cotiro, and starting from there. If you are fluent in XML, you may benefit from reading the schema, which is "resources\courses.xsd".

Beyond the example and schema, I will outline the file structure here (and in doing so will assume no prior knowledge of XML):

First, the courses file always starts with the line:

<courses xmlns="http://www.leedberg.org/cotiro">

and always ends with the line:

</courses>

These two lines tell Cotiro where the courses data begins, and where it ends.

Now, for each individual course that needs to be scheduled, there will be a "course" section within the file, which has the following format:

  <course>
    <title>MY_TITLE</title>
    <instructor>MY_INSTRUCTOR</instructor>
    <size>MY_SIZE</size>
  </course>

To explain this: Each course section within the file starts with <course> and ends with </course>. Between these tags, there are are lines for title, instructor, and size. You would replace the text "MY_TITLE" with the title of the course that you want displayed in the schedule, for example "CS730". You would replace the text "MY_INSTRUCTOR" with the name of the instructor teaching the course. This name may correspond with a name listed in the "teachers" file, discussed later. You would replace the "MY_SIZE" text with the number of students expected to take the course.

You can, of course have multiple course sections within the larger courses section. An example of this file with two courses is:

<courses>
  <course>
    <title>CS 481</title>
    <instructor>Johnson</instructor>
    <size>40</size>
  </course>
  <course>
    <title>PHIL 447</title>
    <instructor>Brewster</instructor>
    <size>120</size>
  </course>
</courses>

2.3 Defining available rooms

Next you'll want to define what buildings and rooms are available to hold these classes. To do this, edit/create a file called "rooms.xml" in the "data" directory of the Cotiro distribution. Probably the best way to learn how to construct this file is simply by examining the example that ships with Cotiro, and starting from there. If you are fluent in XML, you may benefit from reading the schema, which is "resources\buildings.xsd".

Beyond the example and schema, I will outline the file structure here (and in doing so will assume no prior knowledge of XML):

First, the rooms file always starts with the line:

<buildings xmlns="http://www.leedberg.org/cotiro">

and always ends with the line:

</buildings>

These two lines tell Cotiro where the rooms data begins, and where it ends.

It's worth a quick explanation on how the file is laid out. There is a block of the file that defines each building, and within that block, we also the define each room that exists within that building.

Now, for each individual building that exists, there will be a "building" section within the file, which has the following general format:

<building> <name>MY_NAME</name> // PUT ROOMS HERE </building>

To explain this: Each building section within the file starts with <building> and ends with </building>. Between these tags, there is a line for "name", where you would replace MY_NAME with the name of the building. The "// PUT ROOMS HERE" line indicates that here, there can be any number of blocks that define the rooms within this building.

A room section has the following format:

<room> <num>ROOM_NUM</num> <size>ROOM_SIZE</size> </room>

To explain this, for each room within the building, you can define the number by replacing ROOM_NUM with the number of the room (for instance, 101E, 4, or Bradford Lecture Hall). You can define the size by replacing ROOM_SIZE with the number of seats in the room.

As said above, you can have any number of room sections within a building definitions, and any number of building sections within the overall buildings file. Below is an example of this file:

<buildings xmlns="http://www.leedberg.org/cotiro">
  <building>
    <name>Nesmith</name>
    <room>
      <num>326</num>
      <size>30</size>
    </room>
    <room>
      <num>430B</num>
      <size>100</size>
    </room>
  </building>
  <building>
    <name>Horton</name>
    <room>
      <num>4</num>
      <size>200</size>
    </room>
  </building>
</buildings>

2.4 Defining teachers

Lastly, if you wish, you can define preferences involving specific instructors. To do this, edit/create a file called "teachers.xml" in the "data" directory of the Cotiro distribution. Probably the best way to learn how to construct this file is simply by examining the example that ships with Cotiro, and starting from there. If you are fluent in XML, you may benefit from reading the schema, which is "resources\teachers.xsd".

Beyond the example and schema, I will outline the file structure here (and in doing so will assume no prior knowledge of XML):

First, the courses file always starts with the line:

<teachers xmlns="http://www.leedberg.org/cotiro">

and always ends with the line:

</teachers>

These two lines tell Cotiro where the teachers data begins, and where it ends.

Now, for each teacher that has scheduling preferences, there will be a "teacher" section within the file, which has the following format:

<teacher> <name>TEACHER_NAME</name> <building>BUILDING</building> <startTime>START_TIME</startTime> <endTime>END_TIME</endTime> </teacher>

To explain this: Each teacher preference section within the file starts with <teacher> and ends with </teacher>. Between these tags, there are are lines for name, building, start time, and end time. You would replace the text "TEACHER_NAME" with the name of the teacher you are currently defining, for example "Rubenstein". The teacher name should correspond to an instructor listed in the courses file. You would replace "BUILDING" with the name of the building that this teacher prefers to teach in. Cotiro will make a best effort to try and assign this teacher to this building, however, if this assignment is simply not possible then the teacher's courses will be assigned elsewhere. START_TIME and END_TIME set the start and end times between which the teacher wants to teach. These should be in 24-hour time format (i.e., "15:00" rather than "3:00"). Like the building preference, every attempt will be made to stay within this timespan. If this is not possible due to complex conflicts with other courses, Cotiro is capable of assigning during other time periods. See the Constraints section for more information on "soft" versus "hard" constraints.

Note that you may, if you wish, only specify a building preference, or only specify a time preference -- you don't necessarily need to specify both. However, you DO NOT have to specify these preferences at all if an instructor does not care about these attributes. If a teacher exists in the courses file as a teacher, they will be associated with those courses they teach. Only list them here if they have extra constraints about when and where they teach.

You can, of course have multiple teachers within the larger courses section. An example of this file with two teachers is:

<teachers xmlns="http://www.leedberg.org/cotiro">
  <teacher>
    <name>Rubenstein</name>
    <building>Nesmith</building>
    <startTime>15:00</startTime>
    <endTime>21:00</endTime>
  </teacher>
  <teacher>
    <name>Feldman</name>
    <building>Kingsbury</building>
    <startTime>8:00</startTime>
    <endTime>12:00</endTime>
  </teacher>
</teachers>

2.5 Running the program

Once those three files are created in the "data" directory, simply run the program. This is done by running a script from the top-level Cotiro directory. Which script you run depends on what operating system you are using.

2.5.1 Windows

In Windows, simply execute the cotiro.bat file in the top-level Cotiro directory.

The files will be processed and, eventually, a schedule will be output that satisifies all constraints, if one exists.

Note: You must already have a JRE installed, and it must be in your path (this is probably handled automatically by the installer). If you don't already have a JRE, you can download and install it from Sun's Java site.

2.5.2 Linux / Unix

In Linux and Unix systems, simply execute the cotiro.sh script in the top-level Cotiro directory.

The files will be processed and, eventually, a schedule will be output that satisifies all constraints, if one exists.

Note: This script uses the Bash shell, so you must have Bash installed (most Unixes do, though).

You also must already have a JRE installed. If you don't already have a JRE, you can download and install it from Sun's Java site.

Additionally, your JAVA_HOME environment variable must be set and must point to a valid JRE. For example, if your JRE is installed to the directory /usr/java/jdk1.5.0_06, you must issue the command

export JAVA_HOME=/usr/java/jdk1.5.0_06

To have this set every time you log in, you can add the above command to your ~/.bash_profile file (assuming you use Bash).

2.6 Advanced arguments

You can also specify advanced arguments on the command line:

--noconstraints
This argument means that no scheduling constraints are considered. Therefore, every possible combination of courses and rooms will be made.
--noconsistency
This means that arc-consistency is not used for implementing the constraint satisfaction algorithm. This is mostly for comparison purposes. The same schedule will be produced, but it will be slower.
--noheuristics
This turns off heuristics on variable ordering. Like consistency, this does not affect the resulting schedule, but slows down the processing.
--nosoft
Use this option to turn off "soft" (or "preference") constraints, so that all constraints in the system MUST be satisfied in order to produce a schedule.
--showstates
Entirely for debugging purposes, this displays all of the states visited during the backtracking search.

3. Constraints

3.1 "Hard" vs. "Soft" constraints

There are to types of constraints in the Cotiro system: hard and soft. A hard constraint is one which must be satisfied in order to produce a schedule. A soft constraint is one for which a best effort will be made to satisfy it, but if it turns out to not be possible, Cotiro will continue to explore other options. Currently, Cotiro has several specific scheduling constraints built in and each constraint is classified as hard or soft based on technicial considerations involving the algorithm in use. See the next section to see which constraints are hard and which are soft. It is possible to make all constraints hard through the use of command line options, discussed here.

It is worth noting that, generally, it is ideal to have a constraint be soft rather than hard. Soft and hard constraints are actually handled the same until it becomes apparent that there is no way the constraint can be satisified. If this happens with a hard constraint, the entire process is aborted and no schedule is produced. If this happens with a soft constraint, the process continues and explores other options. Making a constraint hard doesn't give it a higher precedence, it simply means alternative options will never be considered.

3.2 What constraints are imposed

What constraints are imposed on the schedule is not configurable, but they are mostly common sense constraints:

No two courses can be scheduled for the same room at the same time (hard)
A professor cannot teach two courses at the same time (hard)
All courses must be scheduled for rooms which can accommodate their class size. (soft)
If a teacher has a building preference, they can only teach in that building. (soft)
If a teacher has a timespan preference, they can only teach during that timespan. (soft)

4. Developers: How To Build Cotiro

Note: This section is only of interest to software developers who are interested in building Cotiro from scratch and, potentially, making modifications to it.

Cotiro was developed using the Eclipse development environment, so it's easiest if you also use Eclipse to build Cotiro. Of course it is possible to use any other environment (or simply command line tools), but this document will only cover Eclipse.

To begin, you have to import the Cotiro project into your Eclipse workspace. The Cotiro sources are included in the distribution zip file, so you merely need to download that and unzip it.

Next, in Eclipse, click on "File", "Import...". From the resulting dialog, select "Existing Project". You will need to browse to the root of the Cotiro directory you previously unzipped. This will bring the existing Cotiro Eclipse project into your workspace.

Within the Cotiro project, there will be a tree node named "src", which is what is of the most interest to you. This contains all of the Cotiro sources. At the top-level of the Cotiro project, there are also several jar files which are on the build path (including some produced by xmlbeans for XML processing).

It's worth noting that this project is set up to put .class files in the "classes" directory, so as you make changes and Eclipse compiles your code, you will be overwriting the class files in that directory.

5. Frequently Asked Questions

It always annoys me when programs include FAQs that really aren't frequently asked questions, but rather "information that the manual-writer couldn't figure out where to put in the manual." I rather enjoy making my FAQs from questions that really do appear frequently in my email in reference to a program. Since I can't possibly know what questions will arise, I will link to a FAQ page on my website, rather than make up questions here. If questions come in over email, rest assured they will also show up on the FAQ webpage.

FAQ page on the Cotiro website

6. Credits

This program was developed entirely by Gregory G. Leedberg.

Cotiro was originally part of my undergraduate studies in artificial intelligence at the University of New Hampshire, in 2003. Active development resumed in 2005 during my graduate studies at Cornell University.

This program makes use of the excellent open-source XMLBeans technology to handle XML file processing.

News

March 14, 2008 - Released Cotiro 0.7.8. For details on what's new in this release, refer to the history page.

January 25, 2008 - Released Cotiro 0.7.7. For details on what's new in this release, refer to the history page.

More...

Donate

Cotiro is provided free of charge. However, if you like it, you are encouraged to donate any amount you feel it is worth to help fund future development.

Feedback

Cotiro is developed by Gregory G. Leedberg. If you have any suggestions, questions, or comments, feel free to send it to me.