Lucent Technologies Inc.

Michael A Bender

Shanmugavelayut Muthukrishnan

Soumen Chakarbarti

In accordance with one embodiment of the invention, a server system computes a feasible stretch value for use in scheduling job requests. A stretch value provides an indication of the delay experienced by each job to complete, when the server processes many jobs concurrently. For a set of job requests, a processing time is calculated for each job request based on, for example, the characteristics of the job and the server system. Thereafter, an estimated stretch value for the set is selected. The server system computes a deadline for each job to be the arrival time of the job request plus the product of the processing time and the estimated stretch value. Thereafter, each job request is scheduled, based on an 'earliest deadline first' arrangement, wherein the job request that has the earliest deadline is scheduled first, the job request having the next earliest deadline is scheduled second, etc. The selected stretch value is deemed feasible if each pending job in the set can be completed prior to its deadline. If the selected stretch value is deemed not feasible, it is adjusted iteratively until an appropriate feasible stretch value is found. The appropriate stretch value is then utilized to schedule the job requests to be serviced or processed by the system. According to one embodiment, the feasible stretch value is adjusted until an optimal feasible stretch value is found, which equals the smallest feasible stretch value which permits all pending jobs to be completed prior to their deadline.

Growing community of inventors

St. Louis, MO, United States of America

Michael A Bender