Johannes Varga, Guenther Raidl, Elina Rönnberg, Tobias Rodemann, "Interactive Job Scheduling with Partially Known Personnel Availabilities", OLA 2023: Optimization and Learning, vol. 1824, no. 236--247, 2023.

When solving a job scheduling problem that involves many humans, the times in which they are available must be taken into account. For practical acceptance of a scheduling tool, it is further crucial that the interaction with the humans is kept simple and to a minimum. Requiring each users to fully specify her or his availability times is typically no reasonable option, nor can a user be requested to indicate possible job starting times from an exuberant amount of suggestions. We consider a scenario in which initially users only suggest single starting times for their jobs and an optimized schedule shall then be found within a small number of interaction rounds. In each such round each user may only be suggested a small set of alternative time intervals, which she or he accepts or rejects. To make the best out of this limited interaction possibilities, we propose an approach that utilizes integer linear programming and a theoretically derived probability calculation for the users’ availabilities based on a two-stage Markov model. Educated suggestions of alternative time intervals for performing the jobs are determined on the basis of these acceptance probabilities as well as the optimization’s current state. Further user availabilities are thus determined by active learning. The approach is experimentally evaluated on artificial test instances and compared to diverse baselines. Results show that an initial schedule can be quickly improved over few interaction rounds, and the fi nal schedule may come close to the solution of the ideal full-knowledge case despite the restricted user interaction.