Offline resource allocation algorithms
First Claim
1. A computer-implemented method comprising:
- collecting data regarding a plurality of requests for resources available from a service provider;
sampling, from the plurality of requests, a number of requests less than all of the plurality of requests to simulate random input of requests;
applying an online resource allocation algorithm with the sampled requests as stochastic input, the online resource allocation algorithm configured to, for each request, match said request to resources by evaluating a difference between a profit value and cost computed for different allocation options using an objective function that accounts for shadow costs assigned to the resources corresponding to each of the different allocation options, the shadow costs including computed or estimated costs that are assigned on an individual basis to the resources; and
determining whether a feasible solution exists to match the sampled requests to the resources based at least in part on the online resource allocation algorithm.
2 Assignments
0 Petitions
Accused Products
Abstract
Various embodiments provide offline algorithms for resource allocation. A known set of “offline” requests may be matched to available resources using an online resource allocation algorithm that models the offline resource allocation problem as though the requests were received stochastically. Requests may be scaled and then sampled to provide random, stochastic input for the online resource allocation algorithm. For each request, resources are allocated to the request by evaluating multiple options based upon shadow costs assigned to resources associated with the different options. After each request is processed, an adjustment is made to the shadow costs for remaining resources to reflect differences in rates for allocation and/or consumption of the resources and the updated shadow costs are used for a subsequent request. A scaled resource allocation determined using sampled requests in this manner may be scaled back up to obtain a solution for the offline resource allocation problem.
-
Citations
20 Claims
-
1. A computer-implemented method comprising:
-
collecting data regarding a plurality of requests for resources available from a service provider; sampling, from the plurality of requests, a number of requests less than all of the plurality of requests to simulate random input of requests; applying an online resource allocation algorithm with the sampled requests as stochastic input, the online resource allocation algorithm configured to, for each request, match said request to resources by evaluating a difference between a profit value and cost computed for different allocation options using an objective function that accounts for shadow costs assigned to the resources corresponding to each of the different allocation options, the shadow costs including computed or estimated costs that are assigned on an individual basis to the resources; and determining whether a feasible solution exists to match the sampled requests to the resources based at least in part on the online resource allocation algorithm. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. One or more computer-readable storage media storing instructions that, when executed by one or more server devices of a service provider, cause the one or more server devices to implement an allocation manager configured to:
-
randomly sample, from a database of requests collected by the service provider in advance, a number of requests for resources from the service provider less than all of the requests in the database to simulate receipt of the requests one by one from resource consumers; and process the sampled requests one by one to match the resources to the requests, including for each request; identifying one or more options of available resources to satisfy the request; evaluating a difference between profit and cost computed for each of the options using an objective function that accounts for shadow costs assigned to the resources corresponding to each of the options; selecting an option to fulfill the request that maximizes profit margin based on the evaluation of the differences between profits and costs; and allocating resources corresponding to the selected option to the request. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
-
16. A computing system comprising:
-
one or more processors; and computer readable storage media having one or more modules stored thereon, that, when executed via the one or more processors, cause the computing system to perform operations including; applying a scaling factor to scale down a number of requests for resources available from a service provider associated with an offline resource allocation problem to produce a representative sample of the requests for resources; sampling the scaled requests to provide random input of the requests one by one to an online resource allocation algorithm; processing the sampled requests one by one to compute a scaled resource allocation that matches resources to the scaled requests, including for each particular request; allocating resources to the particular request by evaluating multiple allocation options based in part upon shadow costs associated with corresponding resources; updating the shadow costs to reflect changes in rates of consumption for corresponding resources based on the allocation to the particular request; and using the updated shadow costs to evaluate options for allocation of resources to a next request. - View Dependent Claims (17, 18, 19, 20)
-
Specification