@inproceedings {pub6464,
	title = {Timing of Queries in Interactive Job Scheduling},
	author = {Johannes Varga AND Harald Korinek AND Guenther Raidl AND Tobias Rodemann},
	year = {2026},
	month = {February},
	abstract = {Motivation and Problem: We consider the Interactive Job Scheduling Problem in which human users, e.g. patients in radiation therapy [2], regularly require access to a limited and high-demand resource, e.g. linear accelerators for the treatment of cancer. To avoid no-shows and frustration of the users, it is important to consider the preferences of the users, in particular the times in which they are available to use the resource. Usually, it is not practical for the users to specify their full availabilities in all detail. Instead, we assume that users initially propose only few timeslots in which they are available to access the resource and
then a scheduling system interacts with the users to find out more about the relevant parts of their preferences. During interaction, the scheduling system proposes alternative timeslots to the users, who accept or reject them depending on their availability times. Previous work [1] does this in multiple interaction
rounds, and in each round, the scheduling system sends out a small number of queries and awaits all replies before starting the next round. We refer to this as blocking approach. In practice, some queries will be answered immediately, while others remain unanswered for a longer time. Since the scheduling system waits
for all of them, each round takes up a significant amount of time, reducing the total amount of queries that can be sent in a fixed timeframe. In this work, we explore different strategies for the timing of interaction in the Interactive Job Scheduling Problem to mitigate this drawback.

Approaches. We consider two models for the durations users require for their reply after having received queries: One with normally distributed, the other with exponentially distributed durations. We develop two interaction approaches to reduce the overall interaction time that is required to achieve a schedule of
good quality, see also Algorithms 1 and 2. In the first approach, the responsive approach, the scheduling system starts by computing and sending out one query per user. Whenever a reply is received, another query is computed and sent until the time budget is reached. A disadvantage of this approach is that a
reoptimization is necessary for each reply and that a lot of queries are sent in total. Therefore, we refine it to the more advanced hybrid approach. Here, we also start with one query per user. Once the first reply arrives, we wait for a fixed amount of time twait. Then, we compute and send out one new query for
each reply that was received during waiting and continue the cycle by waiting again for the next reply. This is repeated until the time budget is exhausted.

Results. To evaluate the approaches, we extend the simulation of the interaction between scheduling system and users from Varga et al. [1] with the reply-time characteristics of the users. Each approach is given a time budget of 600 time units and we evaluate the payoff between the number of queries and final schedule
quality in form of operational costs. We evaluate the approaches on 30 instances with two machines, twelve users and 48 jobs and take the mean over all instances for the results. User delays for answering queries follow a normal distribution with mean 100 and standard deviation 50 and an exponential distribution with
scale parameter 100, respectively. Figure 1 shows the development of the mean objective value over the number of received replies to the queries for both user timing models and the shaded areas depict the variations between the instances. All approaches have a similar objective development over the number of queries. But while the blocking approach is only able to send approximately 50 and 35 queries, respectively, the responsive approach is able to send more than 80 queries and therefore reaches a better objective value. The hybrid approach reduces the number of query computations from >=60 (responsive) to around 20 (twait = 20).},
	publisher = {EuroCAST},
	booktitle = {20th International Conference on Computer Aided Systems Theory}
}