Johannes Varga, Guenther Raidl, Tobias Rodemann, "Selecting User Queries in Interactive Job Scheduling", Eurocast 2024, 19th International Conference on Computer Aided Systems Theory, 2024.

We consider a class of job scheduling problems in which human users, e.g., the personnel of a company, need to perform jobs on some shared machines and the availabilities of these users as well as the machines is critical. In such situations it is rarely practical to ask users to fully specify their availability times. Instead we assume 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 make a small number of queries to users to find out more about their availabilities. We investigate two diff rent forms of queries. For the first one, the approach proposes alternative time intervals for the users’ jobs, which the users either accept or reject, and for the second, users are asked to provide alternative possible starting times for their jobs restricted to certain time intervals. The problem we benchmark our approach on includes multiple machines and only one job can be performed in a non-preemptive manner on one machine at any time. As planning horizon we consider several days and time is discretized. Jobs have individual but machine-independent durations. Scheduling a job induces time-dependent costs and we allow that jobs remain unscheduled at additional penalty costs.