Scheduling jobs using queries to interactively learn human availability times
研究如何在有限交互轮次中，通过查询用户对少量时间区间的接受与否，利用整数线性规划和概率计算，逐步优化包含人类可用时间的作业调度方案。
The solution to a job scheduling problem that involves humans as well some other shared resource has to consider the humans’ availability times. For practical acceptance of a scheduling tool, it is crucial that the interaction with the humans is kept simple and to a minimum. It is rarely practical to ask users to fully specify their availability times or to let them enumerate all possible starting times for their jobs. In the scenario we are considering, users initially only propose a single starting time for each of their jobs and a feasible and optimized schedule shall then be found within a small number of interaction rounds. In each such interaction round, our scheduling approach may propose each user a small number of alternative time intervals for scheduling the user’s jobs, and then the user may accept or reject these. To make the best out of these limited interaction possibilities, we propose an approach that utilizes integer linear programming and an exact and computationally efficient probability calculation for the users’ availabilities assuming two different stochastic models. In this way, educated proposals of alternative time intervals for performing the jobs are determined based on the computed availability probabilities and the improvements these time intervals would enable. The approach is experimentally evaluated on a variety of artificial benchmark scenarios, and different variants are compared with each other and to diverse baselines. Results show that an initial schedule can usually be quickly improved over few interaction rounds even when assuming a quite simple stochastic model, and the final schedule may come close to the solution of the full-knowledge case despite the strongly limited interaction.