Information elicitation in scheduling problems

Ulas Bardak

Ph.D. Thesis, Language Technologies Insitute, Carnegie Mellon University, 2007.


When we work on a practical scheduling task, we usually do not have complete knowledge of the related resources and constraints. For example, when scheduling a conference, we may not know the exact sizes of available rooms or equipment needs of some speakers. The task of constructing a schedule based on incomplete data gives rise to several related problems, including the representation of uncertainty, efficient search for schedules, and elicitation of additional data that help to reduce uncertainty.

In this thesis we introduce a new information elicitation approach aiming to resolve uncertainty in order to increase quality of optimization while keeping the number of questions the user has to answer to a minimum. The approach differs from other approaches in terms of working with a continuous domain with a large number of uncertain variables, not having a need for bootstrapping, tight integration with the optimization process and integration of multiple approaches to elicitation.

The approach estimates the potential impact of asking a question on the schedule quality, based on available information such as stated user preferences or information about the uncertainty itself such as a probability distribution of typical values. The elicitation approach unifies three different elicitation algorithms which we also developed as a part of this work. The unified elicitor is a part of a scheduling system that supports the use of incomplete data. This work has been part of the RADAR project at Carnegie Mellon University, which is aimed at building an intelligent system for assisting an office manager.

The purpose of this thesis is to introduce a new elicitation algorithm and to confirm the following hypothesis: Using the presented elicitation procedure we can pick questions that improve the quality of produced schedules significantly better than picking questions randomly or by using simple heuristics.

We present evaluation results in the conference scheduling domain using different problem sizes, even though theoretically our approach is generalizable to optimization under uncertainty in any other domain. We show that we perform better than random picking of questions and simple heuristics and the difference becomes more prominent as the problem size increases.