A person's agenda often has appointments with both location and temporal constraints, like doctor's appointments, as well as tasks that can be completed at any time and at one of multiple available locations, such as going to an ATM. When faced with a new task to add to their agenda, people are capable of doing so quickly but may find it cognitively challenging to consider the many constraints involved causing them to make mistakes and miss other agenda events. A tool that could help schedule these tasks could mitigate these challenges, but optimal schedulers can be very computationally expensive as they consider many potential completion times, especially when tasks have multiple potential locations.

In this work, we aim to contribute computational heuristics that are nearly optimal for adding tasks into existing agendas, yet are more computationally efficient compared to optimal schedulers. Towards this goal, we first study human strategies for scheduling tasks that can be completed in multiple locations. We found that people primarily use 3 heuristic strategies for scheduling: a) fitting the task as early in the day as possible, b) in the longest open time slot, or c) in a time slot between other activities that are spatially close by the new task. We then implemented human-centered heuristics in line with these strategies along with several other computational heuristics that could be utilized within an automated scheduling framework, and compare them in terms of their run-time and the inefficiency of the schedule length compared to optimal. Additionally, we tested two types of task insertions, a Single Task and a pair of tasks that must be temporally ordered (Order Specific Task) (such as a pickup and delivery), in order to understand how our human heuristics perform in varied conditions.

We found that our heuristics offer different trade-offs between computational run-time and schedule length inefficiency. Relative to the optimal scheduler, our human-centered heuristics are 100,000 to 1 million times faster at inserting a Single Task, but the resulting schedules are an average of 2-6% longer. Our other computational heuristics are slower than the human-centered heuristics, but are still 2x-600x faster than the optimal scheduler, and they find schedules that are closer to optimal. When scheduling Order Specific Tasks, we find similar results where our human-centered heuristics are still 100,000 to 1 million times faster at computing a schedule but are on average 7-14% longer. Our other computational heuristics perform 8-700 times faster than the optimal scheduler again with schedules that are closer to optimal. We conclude that it is possible to select a heuristic that balances required trade-offs in run time and schedule length depending on the needs of a particular scheduling task.

45 pages

Thesis Committee: Stephanie Rosenthal (Chair)
Aaron Steinfeld
Laura Hiatt (Naval Research Laboratory)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu