Cotiro 0.7.1 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
Running the Program
Cotiro Interface Basics
1. File Operations
2. Table Operations
Creating the Input Files For College Time and Room Scheduling
Creating the Input File For Shift-Based Employee Scheduling
Generating a Schedule
Searching / Browsing the Schedule
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 Cotiro is to be an efficient, intelligent scheduling system that can tackle complex scenarios that would be very hard (or impossible) for a human to handle manually. Cotiro currently has two scheduling modes that take care of two types of hard scheduling problems -- college time and room scheduling, and shift-based employee scheduling.

The goal of the college time and room scheduling mode 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.

The goal of the shift-based employee scheduling mode is to handle the slightly more generic case of having to schedule a set of employees to cover a series of shifts, potentially at different physical locations, where each shift may require employees with certain skill sets.

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

Whether you are interested in college time and room scheduling, or shift-based employee scheduling, the overall process remains the same:

First, you enter the information about your specific scheduling problem. Obviously, there is different information depending on which of the two kinds of scheduling problems you have. See here for information on doing this for college scheduling, or see here for how to do it for shift-based employee scheduling.
Once the information has been entered, you tell Cotiro to generate a schedule from it. The point of using Cotiro versus doing this scheduling process yourself by hand is that Cotiro can take a large number of complicated constraints into account and produce a schedule that satisfies all of them, if one exists. See the section on constraints for more information on this core feature of Cotiro.
Once Cotiro has run, it will produce a schedule, in three formats (.txt for viewing in a text editor such as Notepad, .html for viewing in a web browser such as Internet Explorer, and .xml for future processing by Cotiro). For more information on this output, see here.
For college time and room scheduling, you can use the XML output file to explore the schedule (e.g., see all courses taught by a particular teacher). For information on this feature, see here.

That's all there is, at a high-level, to using Cotiro. Read on for detailing information on each step.

3. Running The Program

3.1 Windows

In Windows, use Windows Explorer to browse to the directory where you unzipped Cotiro. At the top level of this directory, there should be a "cotiro.jar" file. Double-click on this .jar file to run Cotiro. 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.

3.2 Linux / Unix

In Linux and Unix systems, simply execute the following command in the top-level Cotiro directory:

java -jar cotiro.jar

Note: You 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. The JRE must also be on your PATH.

4. Cotiro Interface Basics

No matter which of the two types of scheduling problems you are working with, all data entry and schedule generation is done within the Cotiro user interface. As such, knowing how to use the interface is useful knowledge across both types of scheduling problems.

4.1 File Operations

Create a New File - To create a new, blank scheduling information file, click on the "File" menu, then "New...". You can then choose between the two types of scheduling problems, each of which requires different information.
Open an Existing File - If you've previously created a file, you can open it by clicking on the "File" menu, then "Open", which will bring up a file selection window. Navigate to where you saved the file to open it.
Save the Currently Open File - If you have been editing an open scheduling file, you may periodically want to save it. To do so, click on the "File" menu, then either "Save" or "Save As". "Save" is only available if you have already saved the file at least once, and will simply save the file using the existing file name. "Save As" will bring up a window allowing you to choose a name and location for the file to be saved to.
Exiting the Program - To quit the program, click on the "File" menu, then "Exit".

4.2 Table Operations

Data entry in Cotiro is all done through the use of spreadsheets.

Insert a row into the table - To insert a row into the table, select an existing row. Click on the "Table" menu, then "Insert Row". A new row will be inserted below the row that you selected.
Delete a row from the table - To delete a row from the table, select the row you wish to delete. Then, click on the "Table" menu, then Delete Row". The row will be removed.

5. College Time and Room Scheduling

First, an overview of this particular scheduling problem. You will need to provide the following information to Cotiro:

A set of courses, each with an associated teacher.
For each teacher, you can define information such as when they're available to work and what building they prefer to teach in.
A set of buildings and rooms, and for each room, how many people it can hold.
Information about what types of schedules are possible at your institution, such as having one schedule that allows classes to meet for an hour Monday/Wednesday/Friday, and one that allows for 90 minutes on Tuesday/Thursday.

Cotiro's mission here is to assign courses to a particular span of time at a particular room, taking several constraints into account, which will be discussed later.

5.1 Entering the Data

To create a new file for your scheduling problem, within the Cotiro GUI, click on "File", "New", and then "College Time and Room Schedule". You inform Cotiro about the scheduling problem you have by entering information about it into the set of spreadsheets that will have now appeared on screen. There is a separate tab (each with one spreadsheet) for each type of information required.

To see an example, there is an sample input file in the "data" directory named "cotiro_college.xml", which shows a sample scheduling problem. Click on "File", and then "Open" to open this file.

5.2 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.

Schedule information is entered into the spreadsheet found on the "Schedules" tab. There should be one row for each different possible schedule. You can add new schedules easily by clicking the "Quick Add Schedule" button, which brings up a window which asks for the required information. You can also hand-edit the spreadsheet itself if you wish. To delete a schedule, click on "Table", then "Delete Row(s)".

5.3 Defining Courses

Specific course information is entered into the spreadsheet found on the "Courses" tab. There should be one row for each course that needs to be scheduled. You can add new courses easily by clicking the "Quick Add Course" button, which brings up a window which asks for the required information. You can also hand-edit the spreadsheet itself if you wish. To delete a course, click on "Table", then "Delete Row(s)".

5.4 Defining available rooms

Information about rooms and buildings is entered into the spreadsheet found on the "Rooms" tab. There should be one row for each individual room that can be scheduled. You can add a new room by clicking the "Quick Add Room" button, which will then prompt you for the necessary information. If you want to add a room to a building which has already been entered, highlight a row corresponding to an already-entered room in that building, and click the "Quick Add Room to Selected Building" button. You can also hand-edit the spreadsheet itself. To delete a room, click on "Table", then "Delete Row(s)".

5.5 Defining teachers

Lastly, if you wish, you can define preferences involving specific instructors.

Information about teachers is entered into the spreadsheet found on the "Teachers" tab. There should be one row for each teacher. You can add a new teacher's preferences by clicking the "Quick Add Teacher" button, which will then bring up a window asking for the necessary information. You can also hand-edit the spreadsheet itself. To delete a teacher's preferences, click on "Table", then "Delete Row(s)".

The teacher name should correspond to an instructor listed in the courses table. Cotiro will make a best effort to try and assign this teacher to the specified 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. 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.

Lastly, for each teacher, there is a column in the spreadsheet labelled "Properties". These are additional, free-form properties that you can add to a teacher for your own purposes. They won't get used when generating a schedule, but they will appear in the output of the final schedule each time that teacher appears. They are intended to be used to enable you to track extra information about teachers. To add a property, hand-edit that cell in the spreadheet, and use the format "propert1=value1,property2=value2". Each property should be separated by a comma, there should be no spaces.

6. Shift-Based Employee Scheduling

First, an overview of this particular scheduling problem. You will need to define a set of employees, each of which has a name (of course), a set of skills they posses, and a start/end time for a set of days during which they are available to work.

Additionally, you have a set of buildings (maybe just one!), each of which has a set of shifts. Each shift exists during a defined time span on a particular set of days, and each shift requires employees with a certain skill.

Cotiro's mission here is to assign employees to shifts, taking several constraints into account, which will be discussed later.

6.1 Entering the Data

To create a new file for your scheduling problem, within the Cotiro GUI, click on "File", "New", and then "Shift-Based Employee Schedule". You inform Cotiro about the scheduling problem you have by entering information about it into the set of spreadsheets that will have now appeared on screen. There is a separate tab for each type of information required.

To see an example, there is an sample input file in the "data" directory named "cotiro_shift.xml", which shows a sample scheduling problem. Click on "File", and then "Open" to open this file.

6.2 Defining Employee Information

On the employee tab, we define the various employees, their availabilities, and the skills they have. For each skill an employee has, you can also set a limit on how many times they can be assigned to a shit based on that skill.

Information about employees is entered into the spreadsheet found on the "Employees" tab. There should be one row for each employee. You can add a new employees by clicking the "Quick Add Employee" button, which will then bring up a window asking for the necessary information. You can also hand-edit the spreadsheet itself. To delete an employee, click on "Table", then "Delete Row(s)".

The skills entered should correlate with skills required in shifts (discussed later). You can have several skills per employee, by separating them with commas. If you want to limit how many times the employee can be scheduled based on this skill, put the limit in parentheses after the skill, e.g., "cashier(2)".

Lastly, for each employee, there is a column in the spreadsheet labelled "Properties". These are additional, free-form properties that you can add to an employee for your own purposes. They won't get used when generating a schedule, but they will appear in the output of the final schedule each time that employee appears. They are intended to be used to enable you to track extra information about employees. To add a property, hand-edit that cell in the spreadheet, and use the format "propert1=value1,property2=value2". Each property should be separated by a comma, there should be no spaces.

6.3 Defining Shift Information

A shift is defined by specifying a time span, a set of days, and a particular skill required for that shift.

Information about shifts is entered into the spreadsheet found on the "Shifts" tab. There should be one row for each shift that needs to be scheduled. You can add a new shift by clicking the "Quick Add Shift" button, which will then bring up a window asking for the necessary information. You can also hand-edit the spreadsheet itself. To delete a shift, click on "Table", then "Delete Row(s)".

6.4 Defining Travel Times

When producing a shift-based schedule, Cotiro is capable of taking into account the amount of time it takes to travel between two locations. If two locations are 30 minutes apart, and have shifts that are 10 minutes apart, the same employee should not be scheduled for those two shifts.

So, you can optionally define travel times between locations. You don't have to do this -- and if you don't, the travel time between each pair of locations will be considered to be zero.

Travel time information is entered into the spreadsheet found on the "Travel Times" tab. There should be one row for each travel time definition. You can add a new travel time by clicking the "Quick Add Travel Time" button, which will then bring up a window asking for the necessary information. You can also hand-edit the spreadsheet itself. To delete a teacher's preferences, click on "Table", then "Delete Row(s)".

7. Generating a Schedule

Once you have entered all of the schedule information as described above, you'll probably want to have Cotiro generate a schedule, taking into account all of the constraints. When Cotiro produces a schedule, it will produce three output files that contain the schedule in three different formats. The primary Cotiro storage file is an XML file. In the future, this format will allow for editing and exploration of the schedule after it has been produced. Additionally, an HTML file and a TXT (text) file are produced for the purpose of viewing the schedule.

To do this, click on "Tools", then "Generate". This will bring up a window prompting you for information about where and how to output the scheduling results. "Output directory" is the destination directory where you want the three output files placed. "File prefix" is the name you want to give to the three files. For example, if the prefix is "schedule", then the three files produced will be named "schedule.xml", "schedule.html", and "schedule.txt".

Additionally, this window gives you several other options:

Overwrite existing files - If the output .xml, .txt, or .html files already exist in the specified directory, this gives Cotiro permission to overwrite the files.
Ignore constraints - No scheduling constraints are considered. Therefore, every possible combination of courses and rooms will be made.
Show all visited state - Entirely for debugging purposes, this displays all of the states visited during the backtracking search.
No arc consistency - 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.
Don't display final schedule - Create the .xml, .txt, and .html files, but do not display the schedule on the screen upon completion.
No soft constraints - 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.

8. Searching / Browsing the Schedule

Note: This only applies to college time and room schedules!

As discussed above, once you have run Cotiro, three files are produced. Two of these (the .txt and .html files) are intended for viewing / distribution. The third (.xml) is a data file that stores the produced schedule in a format that Cotiro can read and understand. Once this XML file has been produced, you can use Cotiro to search and browse the schedule, for instance, to retrieve a list of courses taught by a particular teacher.

The BrowseSchedule tool within Cotiro is an interactive console program that allows you to enter search "queries" on a particular XML schedule file, and can produce new XML, HTML, or TXT files containing the results of your queries.

You can search schedules based on four criteria: course name, teacher name, building name, and room number.

To use the BrowseSchedule tool, open a command line window (in Windows: Start, Run, "cmd.exe"), "cd" to the directory where Cotiro is installed, and run the "browse.bat" (or browse.sh if you are using Unix) file. This file must be run from a command line window rather than from Windows Explorer because it requires command line arguments in order to run.

The arguments expected by BrowseSchedule are the following:

browse.bat inputfile [-t outputfile | -h outputfile | -x outputfile]

inputfile - This is the XML file that BrowseSchedule should read in and search. You must always specify an input file.
-t outputfile - This tells BrowseSchedule to output the search results in human-readable text form in the specified output file.
-h outputfile - This tells BrowseSchedule to output the search results in HTML in the specified output file, which can then be opened using a web browser.
-x outputfile - This tells BrowseSchedule to output the search results in non-human readable XML format in the specified output file. This is useful if you will want to perform further searches on these results (since this XML file can then be supplied as an input file to the tool).

"inputfile" is the only required argument. If you do not specify an output format/file, then the results will only be printed to the screen in text format. Additionally, you can only specify one output format, i.e., you cannot output both HTML and XML.

Once you have executed browse.bat/.sh as above, you will be prompted for the text to search on for each search criteria. You will be prompted individually for "Course", "Teacher", "Building", and "Room". If you wish to search on a particular field, enter what you wish to search for. If you don't want to search on a particular field, leave it empty and press return.

Once you have entered your search criteria, BrowseSchedule will search the schedule for scheduled courses that match all of your criteria exactly. What this means is if you enter criteria "xxx" for "Course" and "yyy" "Building", BrowseSchedule will search for courses that are named "xxx" AND that are scheduled for a building named "yyy". Any fields you don't enter are not searched for.

BrowseSchedule will output search results (which are really a sub-schedule of the original schedule) to the screen, as well as to the output file if you have specified one. This tool is useful if you want to produce a sub-schedule for an individual teacher, or a particular room, etc.

9. Constraints

9.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.

9.2 What constraints are imposed

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

For College Time and Room Scheduling:

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)

For Shift-Based Employee Scheduling:

An employee must have the skill required by the shift in order to be assigned to it. (hard)
If two shifts overlap, the same employee cannot be assigned to both. (hard
If the same employee is assigned to two shifts at different locations on the same day, there must be enough time between the shifts to allow for travel. (hard)

10. 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 NetBeans 5.5 development environment, so it's easiest if you also use that same version of NetBeans to build Cotiro. Of course it is possible to use any other environment (or simply command line tools), but this document will only cover NetBeans.

To begin, you have to open the Cotiro project in NetBeans. The Cotiro source project is included in the Cotiro distribution zip file, within the "src" directory. In NetBeans, click on "File", "Open Project...". You will need to browse to the root of the Cotiro directory you previously unzipped, select the "src" directory, and click "Open Project Folder". This will bring the existing Cotiro project into your NetBeans.

11. 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

12. 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.