Computer Science 5th Year Master's Thesis Presentation
— 1:00pm
Location:
In Person and Virtual - ET
-
Gates Hillman 6121 and Zoom
Speaker:
PEERAT VICHIVANIVES
,
Master's Student, Computer Science Department, Carnegie Mellon University
Towards Efficient Near-Optimal Agenda Scheduling using Human-Centered Heuristics
A person’s agenda often has appointments with both location and temporal constraints, like doctor’s appointments, along with tasks that can be completed at any time and at one of multiple available locations, like using an ATM. When faced with a new task to add to their agenda, people may find it cognitively challenging to consider the many constraints involved causing them to make mistakes and miss other agenda events. A tool could help schedule these tasks to mitigate these challenges, but optimal schedulers are computationally expensive as they consider many potential combinations, especially when tasks have multiple potential locations.
This work contributes near optimal computational heuristics for adding tasks into existing agendas that are more computationally efficient than optimal schedulers. We study human strategies for scheduling tasks that have multiple potential locations. Results show that people primarily use 3 heuristic strategies for scheduling: checking in chronological order, checking the longest open time slot, or checking time slots between activities that are closest to the new task. We implemented human-centered heuristics in line with these strategies along with other computational heuristics and measured their run-time and inefficiency of their schedule length compared to optimal. We tested two types of task insertions, Single Task and Order Specific Task (a pair of tasks that must be temporally ordered such as a pickup and delivery).
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,000,000 times faster at inserting a Single Task, but the schedules are on average 2-6% longer. Our other computational heuristics are 2x-600x faster than the optimal scheduler and find schedules that are closer to optimal. For Order Specific Tasks, our human-centered heuristics are still 100,000 to 1,000,000 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 with schedules that are closer to optimal. We conclude that it is possible to select a heuristic that balances the trade-offs in run time and schedule length depending on the situation requirements.
Thesis Committee:
Stephanie Rosenthal (Chair)
Aaron Steinfeld
Laura Hiatt (Naval Research Laboratory)
Additional Information
In Person and Zoom Participation. See announcement.