Johannes Varga, Guenther Raidl, Elina Rönnberg, Tobias Rodemann, "Scheduling Jobs Involving Humans with few Interaction Rounds for Learning Human Availabilities", Computers & Operations Research, vol. 167, pp. 106648, 2024.

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, which the user may accept or reject. To make the best out of these limited interaction possibilities, we propose an approach that utilizes integer linear programming and an exact computationally efficient probability calculation for the users’ availabilities assuming an underlying Markov model. 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 very simple Markov model, and the final schedule may come close to the solution of the full-knowledge case despite the strongly limited interaction.