When solving a job scheduling problem that involves 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 users to fully specify their availability times is typically not reasonable. We consider and extend a scenario from the literature 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 round a small amount of information can be requested by suggesting alternative time intervals, which are accepted or rejected. We extend the scenario by another form of interaction that allows to request users to indicate alternative time intervals for their jobs. To make the best out of these limited interaction possibilities, we propose a stochastic programming approach that utilizes a Markov model to consider the users’ availabilities. The approach is experimentally evaluated and compared to the approach from the literature. Results show that the stochastic programming approach performs significantly better than the former method from the literature, especially when being able to request alternative time intervals from users.