A method, system, and computer program product for computing an optimal time interval between polling requests to determine whether an asynchronous operation is completed, in a data processing system. A Polling Request Interval (PRI) utility determines the optimal time interval between successive polling requests, based on historical job completion results. The PRI utility first determines an average job time for previously completed operations. The PRI utility then retrieves a pair of preset configuration parameters including (1) a first parameter which provides the minimum time interval between successive polling requests; and (2) a second parameter which provides the fraction of the average task time added to the first parameter to obtain the time interval between (successive) polling requests. The PRI utility calculates the optimal time between polling requests based on the average job time and the retrieved configuration parameters.