Cotiro 0.7.8 ManualCopyright (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
- What Does This Program Do?
- How To Use This Program
- Running the Program
- Cotiro Interface Basics
- Creating the Input Files For College Time and Room Scheduling
- Creating the Input File For Shift-Based Employee Scheduling
- Generating a Schedule
- Importing / Exporting Data
- Searching / Browsing the Schedule
- Developers: How To Build Cotiro
- Frequently Asked Questions
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 WindowsIn 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.
- "Quick Add" Button - At the bottom of each table is a button labeled "Quick Add". This button will bring up a user-friendly dialog box which allows you to enter the data required for a new row. This is an alternative to manually editing the table. The dialog box will ensure that data is entered correctly.
- "Edit Selected Row" Button - At the bottom of each table is a button labeled "Edit Selected Row". This button brings up the same dialog described above for Quick Add, but instead allows you to edit an existing row.
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 ParametersThe 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.
5.3 Defining CoursesSpecific 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 roomsInformation 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:
- 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. 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.
Importing allows you to enter data using other spreadsheet software, and then load that data into Cotiro. Several steps are involved:
- 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.
- 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.
- 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.
- 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.
- From within the spreadsheet software, save each spreadsheet as a separate CSV (comma separated values) file.
- 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.
- 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.
- When you're done selecting files, click "Import", and the data from the CSV files will be brought into the Cotiro tables.
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:
- Open the file you wish to export in Cotiro.
- 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.
- 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.
- 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.
- 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.
- 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 - 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.
10.1 "Hard" vs. "Soft" constraintsThere 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 imposedWhat 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)
11. Developers: How To Build CotiroNote: 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 QuestionsIt 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. CreditsThis 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.