Cotiro 0.7.8 Manual

Copyright (c) 2003-2008, Gregory G. Leedberg

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

  1. What Does This Program Do?
  2. How To Use This Program
  3. Running the Program
  4. Cotiro Interface Basics
    1. File Operations
    2. Table Operations
  5. Creating the Input Files For College Time and Room Scheduling
    1. The Cotiro Input File
    2. Defining Schedule Parameters
    3. Defining Courses
    4. Defining Rooms
    5. Defining Teachers
  6. Creating the Input File For Shift-Based Employee Scheduling
    1. The Cotiro Input File
    2. Defining Employee Information
    3. Defining Shift Information
    4. Defining Travel Times
  7. Generating a Schedule
    1. Checking for Errors
    2. Generating a Schedule
  8. Importing / Exporting Data
    1. Importing
    2. Exporting
  9. Searching / Browsing the Schedule
  10. Constraints
    1. "Hard" vs. "soft" constraints
    2. What Constraints Are Imposed
  11. Developers: How To Build Cotiro
  12. Frequently Asked Questions
  13. 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:

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

4.2 Table Operations

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

5. College Time and Room Scheduling

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

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.

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.

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

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.

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 semicolon, 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.

The skills entered should correlate with skills required in shifts (discussed later). You can have several skills per employee, by separating them with semicolons. 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 semicolon, 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.

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.

7. Generating a Schedule

7.1 Checking for Errors

Once you've entered all of the schedule information as described above, you'll probably want to have Cotiro generate a schedule. However, before you do that, you'll want to have Cotiro check and make sure that there aren't any problems with the data you've entered. This is called "Validating" the data.

To do this, click on the "Tools" menu, and select "Validate". This will run through all of the tables and check for common errors that would prevent Cotiro from producing a schedule. For example, it will verify that times are in the correct format, and that cross-references between tables are valid (such as, if a teacher is specified to favor a particular building, that building should exist in the buildings table).

When the validation is done, a window will appear with a list of each problem found. Each problem will be in this format:

[table name] : [row number] : [summary of row contents] : [error description]

Double-clicking on an error will scroll the main Cotiro window to that table and row.

7.2 Generating the Schedule

Once you've entered the data and validated it, 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:

8. Importing / Exporting Data

It is possible to use other spreadsheet software (such as Microsoft Office Excel) to enter data, and then read that data here ("importing"). It is also possible to output the data entered here into a format readable by other spreadsheet software ("exporting"). This is intended to give users a choice, in case you are already proficient with another data entry system.

8.1 Importing

Importing allows you to enter data using other spreadsheet software, and then load that data into Cotiro. Several steps are involved:

  1. First, make sure that the spreadsheet software you are using supports .CSV (comma separated values) files. This is the only format that can be imported.
  2. In the other spreadsheet software, create a separate spreadsheet for each table in Cotiro. For example, in shift-based scheduling this would mean having a spreadsheet for Shfits, Employees, and Travel Times.
  3. Within each spreadsheet, use the same column layout as Cotiro does. For example, in shift scheduling mode, this means that the spreadsheet for "Shifts" should have the first column be "Location", the second be "Skills Needed", and so on.
  4. Within each cell, make sure you use the same textual format that Cotiro uses. Refer to earlier parts of this manual for more information of these formats. For example, in the shift scheduling mode, in the "Shifts" spreadhseet, in the "Skills Needed" column, each cell should have a comma-separated list of skills.
  5. From within the spreadsheet software, save each spreadsheet as a separate CSV (comma separated values) file.
  6. In Cotiro, either create a new blank Cotiro file, or open an existing file. If you have a new blank file, importing will bring the data into the blank tables. If you have a file with existing data in it, the data from the CSV files will be added to that existing data. If you would rather replace the existing data, use the Table | Clear Table menu option before importing, which will delete all of the data in the table.
  7. Click on Table, then Import. This will bring up the Import Data dialog. For each table in Cotiro, you will be able to specify a CSV file you want to use to populate that table. Make sure that the CSV files you select correspond to the table you are selecting them for! You don't need to select a CSV file for every table -- any table left blank will be left as-is.
  8. When you're done selecting files, click "Import", and the data from the CSV files will be brought into the Cotiro tables.

8.2 Exporting

Exporting allows you to enter data using the Cotiro user interface, and then export that data to a format that will be readable by other spreadsheet software. If desired, you can edit the data in other spreadsheet software, and then import it back into Cotiro, using the method described above. Several steps are involved in exporting:

  1. Open the file you wish to export in Cotiro.
  2. Click on Table, then Export. All tables within this Cotiro file will be exported, so it doesn't matter which one is visible when you click Export.
  3. This will bring up the Export dialog. Exporting will produce several CSV (comma separated values) files; one for each table in Cotiro. First, select the directory into which you want all of these files to be stored.
  4. Next, select a file name prefix for each file. This prefix will be added on to the beginning of each table name. For instance, if you are exporting a Shift-based scheduling file, and select the file name prefix "schedule", you'll end up with files named "schedule-shifts.csv", "schedule-employees.csv", and "schedule-traveltimes.csv". The prefix is a way to group files from the same Cotiro input file.
  5. Use the "Overwrite existing files" checkbox if you want to overwrite any files that exist with the same name. If you leave this unchecked and files already exist with these names, the export will fail.
  6. Click "Export". Each file will be produced in the specified directory.

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

10. Constraints

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

10.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:

For Shift-Based Employee Scheduling:

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

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

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