Scheduling Assistant

What is Scheduling Assistant?

This project is a scheduling assistant for a campus organization known as Engineering Ambassadors (EA). In EA, student-led events are held each week where participants are scheduled based on their availability. The person in charge of scheduling must ensure that all 20-30 events are covered and that each of 35 members has a fair number of events. There are also specific roles during the event that must be assigned to people based on availability. Since this can take up to a week to do by hand, this project aims to automate the process with artificial intelligence.

What does Scheduling Assistant do?

• Gather availability by a survey (shown in Figure 1):
  • available data
  • available time interval

Figure 1: Scheduling survey

• Encode the survey data (shown in Figure 2):
  • each half hour is encoded by a number between 1 and 7
  • “Not available” represented by a 0.

Figure 2: Sample encoded output data

• Set up constraints
  • Events run from 8:30 to 11:30 and are subject to these constraints:
    1. At least 4 people but no more than 7 people must be present at all times between 9:00 and 11:00.
    2. All five roles must be filled for each event (see more about this below).
  • People who fill out the availability survey are subject to the following hard and soft constraints:
    1. Each person MUST be scheduled for at least 3 events, but no more than 6 events
    2. If possible, each person should have a role during at least a third of their events
    3. If possible, no person should have a Presenter or Lead role for more than two events
  • Finally, the roles that must be filled at events and their constraints are as follows:
    1. Presenter: TWO are required for each event and they must attend from 9:00 to 10:00
    2. Lead: ONE is required and that person must be available for at least two hours of the event
    3. Intro: ONE is required and that person must be available from 9:30 to 10:30
    4. Debrief: ONE is required and that person must be available from 10:30 to 11:30
• Output solution meet constraints

Algorithms

We have implemented three recommend algorithms in this project:

• Genetic Algorithm
• Hill-climbing

Data Structure

The general class diagram, as shown below in Figure 3, was chosen so that we could keep track of all the information about our constraints and more easily calculate the heuristic.

Figure 3: Class Diagram

Evaluation

To evaluate the correctness of a schedule, a function was created since the heuristic does not reveal any data about its weak points. The function counted how many roles were unfilled across all events, how many people were working at too many events, how many people worked too few, and how many people had too many Presenter or Lead roles. Since having too few roles was a soft constraint, it was not included, and the function covered all of the hard constraints. After the heuristic was tuned, the algorithms were tested. For the hill climbing algorithm, assessment was done by varying the time the algorithm was given to search for good schedules. Values of 3, 6, 12, 24, and 48 minutes were used as input times because they are sufficiently spread out. The genetic algorithm was also tested by different time intervals, but because the running speed for forming a new generation is much faster than forming possible schedules of hill climbing, 90 seconds, 3 minutes, 6 minutes, 12 minutes and 34 minutes were used for input times.

Results

For each event in our final schedule, a Gantt Chart can be plotted like the one shown in Figure 4. The x-axis represents the time slots and y-axis shows the Person IDs. Different colors represents different roles in each event: light blue stands for “Presenter”, red is for the role of “Intro”, orange is for “Lead”, blue is for the role of “Debrief” and grey is for no role assigned. Thus, an end user can clearly see who will show up and take charge of which parts in a particular event.

Figure 4: Result Schedule for Event 1

The genetic algorithm was tested by running for different lengths of time as shown in Figure 5. As we can observe, as the genetic algorithm runtime increases, its performance is consistently better than the hill climbing algorithm (discussed later), but it does not improve as consistently. Based on our analysis, this is caused by the crossover function. Our crossover function only switches a person’s role between two schedules but does not guarantee removing roles from people or assigning people to new events.

Figure 5: Results from genetic algorithm tests

The hill climbing algorithm was tested by increasing the time provided to the algorithm once the heuristic had been tuned. The results, shown in Figure 6, indicate that increasing the time given to the algorithm increased the performance drastically. There was a sharp drop in the number of roles unfilled for each event, and the number of people with too many events scheduled slowly decreased. The number of people with too many roles remained relatively constant, reflecting the fact that it was a soft constraint, and almost nobody was ever scheduled for less than three events.

Figure 6: Results from hill climbing algorithm tests

Conclusion

Neither algorithm was wholly successful at creating a perfect schedule, because of how complex the data was and how much time it took to iterate through and test the algorithms. However, the schedules created were improvements from a completely random schedule. People were not assigned to events they could not attend and a majority of events were adequately staffed with all roles filled. Although most people were over-scheduled for events, they were not given too many roles and further adjustment of the heuristic or a new schedule validation function could potentially solve this problem. Additionally, human input possibly could be used to do the final cleanup when schedules are mostly created if a good user interface is provided. While we cannot say this project fully met the intended goal, it is a step in the right direction. With some more work, it could be ready to use next year in a real-world situation for Engineering Ambassadors. Using AI to create schedules instead of doing it by hand will be very helpful. Unlike humans, a computer can assess thousands of different options in a short amount of time–even though our algorithms were on the slow side. With the heuristic as the intelligence of the program, assessing the possible schedules is much faster than doing it by hand. Prior to seeing the lecture examples in this course, AI would not have come to mind as a way of solving a scheduling problem, but now it is quite obvious that it is a promising option for making scheduling fast and painless in the future.