Project: Sports Scheduling

As you may know, the task of scheduling competitions in a league is complex and difficult. There are many criteria that you attempt to meet (e.g., you want to limit travel) and many criteria conflict with each other. If you have to build schedules by hand, your approach might simply to be to put together something that seems “good enough” and then adjust as necessary. But computers allow you to quickly try many more adjustments, as well as to think about other approaches.

What kinds of criteria might you have? You might want to limit how many games in a row a team plays at home or away. You might want to make sure that all the games in a time period (e.g., a weekend) are played in similar locations (e.g., both at home or at two schools that are near to each other). You might have certain dates that teams have to be home or away. And so on and so forth.

Sports scheduling is complex enough that many leagues pay a service to do it for them. For example, a typical service, advertised at http://www.uwsp.edu/cols-ap/cas/Pages/default.aspx, charges $300 to generate a schedule, and $450 for a “rush” schedule (generated in two or three weeks).

Why does it cost so much to schedule? In part, it's because it's hard to do it by hand, and $300 might be less than you'd pay someone for the number of hours it costs to do so by hand. And, even if you have a program, someone needs to translate the informally stated requirements into a formal representation.

The following are a variety of examples taken from the Midwest Conference. I believe that the goal is to schedule for 2016-17. You can find mileage information on the Midwest conference at http://midwestconference.org/sports/2010/7/20/GEN_0720102356.aspx.

RC   SNC  LU   BC   LFC  IC   GC   CC   KC   MC
GC   CC   IC   GC   MC   LU   RC   SNC  LU   LFC
IC   KC   KC   MC   CC   RU   BC   LFC  SNC  BC

Your goal is to write a well-designed program that will generate schedules using criteria like those described above. To write such a program, you will need to

You will also need to provide information to your clients about your program, its features, and any related issues.

At minimum, your program should be able to read in two sets of data: The list of potential dates for competitions and the restrictions on when schools must and cannot play. Optionally, your program might read in the distances between schools, the criteria we use for scheduling games, and other data your program could use. (If you don't read it in, you'll still need to use much of the information in your program, but you can hardcode it. The scheduling criteria can be implicitly hardcoded into your algorithm.) Ideally, these data would be stored in one or more files (e.g., one for dates, one for restrictions,one for distances).

At minimum, your program should print out the schedule of competitions. You might also find some other clever forms of output.

At minimum, your program should be able to develop schedules that meet one of the two sets of restrictions given above (or that come close to developing such schedules and report the points of departure). Optionally, your program would be able to develop schedules that could incorporate other kinds of restrictions. (You'll need to talk to someone about what those other kinds of restrictions might be.)

At minimum, the program's UI should allow one to specify the input files (e.g., on the command line) and should send the schedule to standard output. Optionally, you could develop a graphical user interface or even just provide a more sensible textual user interface.

Stage one: Planning (due 10:30 p.m., Wednesday, 19 November 2014). In this stage, you will develop the big picture of the program as well as do some preliminary coding. At the end of this stage, you should present me with (a) a high-level design of the objects you expect to use in the program and their relationships; (b) a high-level design of the algorithm you expect to use for scheduling and a casual analysis of its asymptotic running time; (c) an implementation of the input and output subsystems, along with the related classes. This stage is worth 30% of your grade. You may present your high-level design pictorially, in text, or in code.

Stage two: Production (due 10:30 p.m., Tuesday, 25 November 2014). In this stage, you will implement the algorithms and objects from your prior stage. You should make sure that the result is a program that is well documented. Your program should generate schedules and, ideally, use randomness to ensure that it does not always generate the same schedule every time. A well-documented program includes at least three kinds of documentation: internal documentation in the code, to help the maintainer; an overview of the parts of the code and their relationships, to help those maintaining and extending the code; and user documentation, to explain how to use the program. The programmer documentation should be written for people with similar experience to your peers. The user documentation should be written for someone with more limited technical knowledge, but who at least knows how to open a terminal and look at your documentation. This stage is worth 45% of your grade.

Because you will be writing code that others may want to use. Hence, must decide how to license your code. You can pick one of the open source licenses or you can choose a commercial license. (If you choose a commercial license, you must grant me royalty-free permission to use the work in the class this semester.)

Stage three: Presentation (on Tuesday, 2 December 2014). In this stage, you will present your project to a public audience. That audience will certainly include your peers from the class. It may also include other faculty and students from the department. Some of those students may be working on an improved version of the project next semester. I wll also invite Director Benning and some of the PE faculty to attend. One of your goals in the presentation is to convince others that your solution is better. I wll ask members of the audience to rank the projects. Those who receive higher rankings are likely to receive a prize or prizes that may include a bit of extra credit. This stage is worth 15% of your grade. You will have four or five minutes to give your presentation and I will need your slides (no more than four, including title slide) the day before the presentation.

In stage three, you will also provide me with a report that describes key aspects of the project, including the following:

Stage four: (Ap)praise. In this stage, you will write a short assessment of each of the peer group projects. This stage is worth 10% of your grade. Note that I do not have to agree with your assessment, but you must do a thoughtful assessment. (I will provide you with a rubric to help you assess peer projects.)

The idea for this assignment came from Heather Benning, Executive Director of the Midwest Conference. Director Benning also provided the descriptions of the criteria for basketball scheduling (although I've modified them somewhat; any errors are probably mine).

Some text about projects in general came from a JSON project in a prior section of CSC 207. That assignment is available at http://www.cs.grinnell.edu/~rebelsky/Courses/CSC207/2014S/assignments/json.sect.