In many dynamic application domains, the environment changes during problem solving. A problem solver, in these applications, is required to use up-to-date information that becomes available on line. Real-time applications, on the other hand, require a problem solver to produce an answer within a given deadline. Moreover, a real-time problem solver is expected to predict whether it can meet a deadline or not. Due to the changes over time, real-time problem solving in dynamic domains is a di.~cult task. Meeting deadlines andlor minimizing tardiness under varying degrees of dynamicity is difficult to model and guarantee. In this paper, we propose an algorithm which performs realtime problem solving on line, in order to obtain new information about the availability of resources in the system. We provide empirical analyses of our algorithm for a routing problem in a dynamic model. Our results show that the proposed technique can minimize tardiness and that it can reasonably predict deadline compliance in the proposed dynamic environment.