Interface
We centered our interface design around two questions: if we were users, what would we want to do? and How can we make it easy to do it?
Firstly, we want to “send and receive” events. We wanted to be able to create an event, add participants, resources, and specify the constraints. We wanted to be able to send it to the participants, who would then respond. Then the administrator would look over the responses and finalize the event.
Secondly, we want easy navigation and shallow learning curve.
These two elements reminded us of something familiar: email!
This kills two birds with one stone.
By using the email interface as a jumping off point, we didn’t have to reinvent the wheel with our design. Plus, since so many people are familiar with how email works, people would already have an intuitive sense as to how to use our site.
So without further ado, here’s an image of our inbox, which we call the “My Events” page:
My Events
As with an email inbox, the “My Events” page, is the hub where you manage all of your events. Each event is treated as a separate item with its own separate options, like an email message.
We also have a “New Event” button, color-coding for unresponded events, and tools for organizing and filtering. These icons let you edit events as well as hide old or unwanted events.
In addition, we can see the status of an event – whether participants can respond, whether the assignments are posted. If you are the administrator of an event, you can see how many participants have responded. You can also view their responses.
Groups
We also have a “groups” functionality, which allows you to create and save lists of users and add them to events with a single click instead of having to individually enter each user’s name. This is a bit like email list servers.
Public Events
Finally, though we took inspiration from email, it was important for us to recognize where the email paradigm did not quite fit our site’s. In email, all messages are only sent to the specified recipients. But many times we want anyone to be able to join an event. Thus, we added something called a public event and the “Public Events” tab, which allows anyone on our site to sign up for an event. Public Events were especially valuable to the Career Center, which wanted to make its meetings with alumni available to anyone on campus.
Here, we have all of the public events grouped by the date in which they were created. You can see who posted the event, and use the search box to find an event that you want to join.
Database
For our database, besides having the ability to store a lot of data (like Carleton users) and add and remove data (like Events), it needed the additional quality of robustness: for example, if we want to add an event that has new set of constraints for matching participants to resources, we needed to be able to implement this without having to completely redesign the database. So our database needs to both be powerful enough to handle a lot of information and robust enough to adapt to changes.
What you see now is an example of our approach to database design. The specific details aren’t too important, but what is important is that we have users and events tables. Each row in the users table represents a user and has a unique user_id. Each row in the events table represents an event and also has a unique event_id.
The database allows us to search for rows in the tables by running something called a database query.
But, users are related to events, either by being participants or administrators!
Thus, we have the user2event table, which stores information about the relationship between users and events. We can see the unique user and event id’s here as well as information about the relationship between the user and event. In this first column, we can see that user 1, “levyd,” is a participant and an admin in event 1, “comps.”
The last thing to note is this algorithm_id column in the events table, which speaks a little to the robustness idea we emphasized earlier. Elsewhere in the database, we have an algorithms table with descriptions and unique ids for our algorithms that find matching’s between participants and resources. If we create a new algorithm that we want to add to our site, all we need to do is add a new row to the algorithms table. Then, to use that algorithm, we set the algorithm_id column for an event to the id of that algorithm.
Here we have a diagram of our overall database design. Again, the specifics aren’t important, but as in the example we just showed you, the arrows show the relationships between the information in different tables in our database. You can see the relationship between users and events that we showed you in the image above.
Algorithms
Algorithms is the part of our project with the most room for development. Because our project is so user-focused, we necessarily had to spend a bit more time getting our website useable than actually making it schedule people in cool ways. However, we were able to solve some basic scheduling problems with far-reaching applications, as well as make some significant progress on more specific (and cooler) scheduling problems.
Our simplest algorithm is first-come-first-serve. It is so simple that it probably cannot really be called an algorithm in the conventional sense. Rather, it is a strategy for scheduling people. A user picks his or her most preferred resource and the next user picks his or her most preferred from the remaining resources. The advantage here is that users can choose a resource and know immediately what their assignment are. However, it has a major disadvantage. If one user is only available for resources that other users have already chosen, that user cannot be scheduled, even if the other users are available for unassigned resources as well. Our next algorithm addresses this problem, and allows us to implement a notion of optimality.
We call our next algorithm "Bipartite Matching," and it allows as many users as possible to be assigned to resources. For this algorithm, users input all resources for which they are available, and we use this information to construct a bipartite graph with edges between users and the resources they have input. We then wrote a C++ implementation of the Ford-Fulkerson Algorithm to find a maximum flow in the graph. This maximum flow uses edges between users and resources in an optimal matching, so this set of edges becomes the assignments for the problem.
Our final algorithm in the website takes a different approach to scheduling. We call this algorithm "Many-to-One," because it gives the best matching of many users to one resource. Alternately, we call this algorithm our "Group Meeting" algorithm, because it outputs the best way for groups of users to meet together. The algorithm is quite simple; it simply adds up the number of users who choose each resource, and selects the resource with the maximum value. However, it also allows administrators to add "priority" to users, making their vote count more. Users can choose multiple resources for which they are available. In essence, the algorithm itself is very simple, but the interface on our website is what makes it interesting
These are all the algorithms we actually implemented on our website. However, we explored many other more interesting problems and their corresponding algorithms, and made very good progress on actually solving some of them.
The best example of a complicated algorithm we worked very hard on and got good results is the "Dining Hall Problem." This is a Carleton-specific problem in which dining hall workers are assigned by dining hall managers to different available work shifts. It is similar to bipartite matching, but with significantly more constraints. For example, multiple participants are assigned to "Monday breakfast," but they are assigned different tasks, which can each take up different amounts of actual time. Additionally, we are assigning based on scheduled hours, not number of shifts. We struggled with this problem for quite a while, after which we came to the conclusion that it is most likely NP-hard, but that we can make a really good approximation algorithm.
Our dining hall algorithm greedily assigns users to the "hardest to fill" shifts; that is, shifts with the fewest number of available workers. This gets us pretty close to an optimal output, but there are many pathological cases whereby this will give really bad output. Luckily, it is close enough that it can almost always get managers close enough to a point where they can fix up any lingering problems themselves.
This is the state of Schedaroo right now and going forward. We have all the framework to make scheduling possible, but more complicated algorithms and their corresponding interfaces take a lot of time to solve and to implement. The dining hall problem is most of the way done, but it would take a lot of tweaking before we're comfortable "going live" with it. Other problems, like the "KRLX Scheduling Problem," are much further away from having a workable solution and interface on our site.