Two-part job scheduling with capacity constraints and preferences

• US 10,261,837 B2
• Filed: 06/29/2018
• Issued: 04/16/2019
• Est. Priority Date: 06/30/2017
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Chen, Feng (Jason), Maxwell, Matthew Scott, Sanli, Tugrul, Yao, Xiaodong
• Primary Examiner(s): Rashid, Wissam
• Application Number:
  US16/023,949
• Publication Number:
  US 20190012210A1
• Time in Patent Office: 291 Days
• Field of Search: None
• CPC Class Codes: G06F 2209/501 Performance criteria
• CPC Class Codes: G06F 2209/5014 Reservation
• CPC Class Codes: G06F 2209/504 Resource capping
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5055 considering software capabilities, i.e. software resources associated or available to the machine
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G06N 3/084 Backpropagation, e.g. using gradient descent
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 47/781 Centralised allocation of resources
• CPC Class Codes: H04L 47/83 based on usage prediction
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Exemplary embodiments relate to the problem of allocating a finite number of units of a resource among requestors willing to offer different amounts of value for the resource. When different classes of requestors are permitted to cancel the request or fail to show up to collect the unit of the resource with different probabilities (collectively referred to as “wash”), the problem becomes difficult to solve efficiently. According to the procedures described herein, the capacity is artificially inflated to offset the impact of wash, and then protection levels are computed using the inflated capacity as if there was no wash. The capacity is then artificially inflated again based on the new protection levels, and the process is repeated until, e.g., the results converge. Using this procedure, overallocation limits and protection levels can be computed in real-time, and accordingly the resource can be allocated efficiently as new requests are received.

Claims

1. A non-transitory computer-readable medium storing instructions that, when executed by one or more processors, cause the one or more processors to provide a task management controller configured to allocate units of a resource having a predetermined capacity to different classes of requestors, each class having a distinct probability of failing to use an allocated unit of the resource and being associated with a value collected when a member of the class is assigned or consumes the allocated unit of the resource, the instructions comprising instructions for:

(1) determining an overallocation limit representing an upper limit to which the resource may be overallocated

(2) inflating the predetermined capacity by adding the overallocation limit determined in (1) to the capacity;

(3) determining a protection level for each of the different classes based on the inflated capacity, the protection level defining an amount of capacity to reserve for future requests for resources and being determined by maximizing an expected value for the different classes that arrive in the future given an amount of capacity allocated to a current class and a number of the different classes;

(4) updating, based on the protection levels determined in (3), each of the probability that the requestor fails to use the allocated unit of the resource and the average value loss in the event that the requestor fails to use the allocated unit of the resource;

(5) repeating (1)-(4) until a stopping condition is reached; and

providing the values of the overallocation limit and the protection levels set at a time the stopping condition is reached to the task management controller, the task management controller determining whether to allocate a unit of the resource to a requestor from the current class based on whether the overallocation limit has not yet been reached and based on whether capacity remains under the protection level.

2. The medium of claim 1, wherein the stopping condition is one or more of a maximum number of iterations of (1)-(4) or a predefined maximum amount of time allowed to elapse while repeating (1)-(4).

3. The medium of claim 1, wherein the stopping condition occurs when one or more of the overallocation limit or the protection levels converge to within a predetermined threshold range between subsequent iterations of (1)-(4).

4. The medium of claim 1, wherein the values of the overallocation limit and the protection levels are determined substantially in real-time as requests for units of the resource are received.

5. The medium of claim 1, wherein the overallocation limit is limited by a predetermined overallocation upper bound.

6. The medium of claim 1, wherein request for a unit of the resource occurs in two parts comprising:

a first part that does not consume any of the resource and is associated with a first preference value; and

a second part associated with a second preference value, the second part being capable of succeeding or failing, wherein the protection levels are determined, at least in part, based on the first preference value and the second preference value

and further storing instructions for;

determining whether the second part succeeds or fails;

based on the determination, consuming a unit of the resource if the second part succeeds, or

failing to consume a unit of the resource if the second part fails.

7. The medium of claim 6, wherein the second part is associated with a value loss in the event of a failure of the second part.

8. The medium of claim 6, wherein the task management controller is configured to attempt to maximize a sum of the first preference value and the second preference value for the requestors.

9. The medium of claim 1, wherein a penalty is associated with allocating a unit of the resource but failing to provide the unit of the resource, at least one of the overallocation limit or the protection levels being determined at least in part based on the penalty.

10. The medium of claim 1, wherein the overallocation limit is initially determined by:

(a) determining an average wash probability representing a probability among the requestors that the requestors fail to use the allocated unit of the resource, averaged over the requestors, based on historical wash probabilities for the resource among the classes of requestors,

(b) determining an average value loss representing an amount of value lost in an event that a given requestor fails to use the allocated unit of the resource, averaged over the requestors, based on historical value loss percentages or a preconfigured default value,

(c) using the average wash probability and the average value loss to determine an estimated total value lost among requestors that are predicted to fail to use the allocated unit of the resource,

(d) using the average wash probability and a probability distribution representing a quantity of demand for the units of the resource to determine an estimated net capacity utilization,

(e) determining an average value representing a value among the requestors that are predicted to show up to utilize the allocated unit of the resource given the net capacity utilization; and

(f) adjusting the overallocation limit to maximize an expected value among the different classes of requestors, based at least in part on the average value as determined in (e) and the estimated total value lost as determined in (c).

11. A method for providing a task management controller configured to allocate units of a resource having a predetermined capacity to different classes of requestors, each class having a distinct probability of failing to use an allocated unit of the resource and being associated with a value collected when a member of the class is assigned or consumes the allocated unit of the resource, the method comprising:

(1) determining an overallocation limit representing an upper limit to which the resource may be overallocated

(2) inflating the predetermined capacity by adding the overallocation limit determined in (1) to the capacity;

(3) determining a protection level for each of the different classes based on the inflated capacity, the protection level defining an amount of capacity to reserve for future requests for resources and being determined by maximizing an expected value for the different classes that arrive in the future given an amount of capacity allocated to a current class and a number of the different classes;

(4) updating, based on the protection levels determined in (3), each of the probability that the requestor fails to use the allocated unit of the resource and the average value loss in the event that the requestor fails to use the allocated unit of the resource;

(5) repeating (1)-(4) until a stopping condition is reached; and

providing the values of the overallocation limit and the protection levels set at a time the stopping condition is reached to the task management controller, the task management controller determining whether to allocate a unit of the resource to a requestor from the current class based on whether the overallocation limit has not yet been reached and based on whether capacity remains under the protection level.

12. The method of claim 11, wherein the stopping condition is one or more of a maximum number of iterations of (1)-(4) or a predefined maximum amount of time allowed to elapse while repeating (1)-(4).

13. The method of claim 11, wherein the stopping condition occurs when one or more of the overallocation limit or the protection levels converge to within a predetermined threshold range between subsequent iterations of (1)-(4).

14. The method of claim 11, wherein the values of the overallocation limit and the protection levels are determined substantially in real-time as requests for units of the resource are received.

15. The method of claim 11, wherein the overallocation limit is limited by a predetermined overallocation upper bound.

16. The method of claim 11, wherein request for a unit of the resource occurs in two parts comprising:

a first part that does not consume any of the resource and is associated with a first preference value; and

a second part associated with a second preference value, the second part being capable of succeeding or failing, wherein the protection levels are determined, at least in part, based on the first preference value and the second preference value

and further storing instructions for;

determining whether the second part succeeds or fails;

based on the determination, consuming a unit of the resource if the second part succeeds, or

failing to consume a unit of the resource if the second part fails.

17. The method of claim 16, wherein the second part is associated with a value loss in the event of a failure of the second part.

18. The method of claim 16, wherein the task management controller is configured to attempt to maximize a sum of the first preference value and the second preference value for the requestors.

19. The method of claim 11, wherein a penalty is associated with allocating a unit of the resource but failing to provide the unit of the resource, at least one of the overallocation limit or the protection levels being determined at least in part based on the penalty.

20. The method of claim 11, wherein the overallocation limit is initially determined by:

(a) determining an average wash probability representing a probability among the requestors that the requestors fail to use the allocated unit of the resource, averaged over the requestors, based on historical wash probabilities for the resource among the classes of requestors,

(b) determining an average value loss representing an amount of value lost in an event that a given requestor fails to use the allocated unit of the resource, averaged over the requestors, based on historical value loss percentages or a preconfigured default value,

(c) using the average wash probability and the average value loss to determine an estimated total value lost among requestors that are predicted to fail to use the allocated unit of the resource,

(d) using the average wash probability and a probability distribution representing a quantity of demand for the units of the resource to determine an estimated net capacity utilization,

(e) determining an average value representing a value among the requestors that are predicted to show up to utilize the allocated unit of the resource given the net capacity utilization; and

(f) adjusting the overallocation limit to maximize an expected value among the different classes of requestors, based at least in part on the average value as determined in (e) and the estimated total value lost as determined in (c).

21. An apparatus comprising:

a processor circuit; and

a non-transitory computer-readable medium storing instructions that, when executed by the processor circuit, causes the processor circuit to provide a task management controller configured to allocate units of a resource having a predetermined capacity to different classes of requestors, each class having a distinct probability of failing to use an allocated unit of the resource and being associated with a value collected when a member of the class is assigned or consumes the allocated unit of the resource, the instructions comprising instructions for;

(1) determining an overallocation limit representing an upper limit to which the resource may be overallocated

(2) inflating the predetermined capacity by adding the overallocation limit determined in (1) to the capacity;

(3) determining a protection level for each of the different classes based on the inflated capacity, the protection level defining an amount of capacity to reserve for future requests for resources and being determined by maximizing an expected value for the different classes that arrive in the future given an amount of capacity allocated to a current class and a number of the different classes;

(4) updating, based on the protection levels determined in (3), each of the probability that the requestor fails to use the allocated unit of the resource and the average value loss in the event that the requestor fails to use the allocated unit of the resource;

(5) repeating (1)-(4) until a stopping condition is reached; and

providing the values of the overallocation limit and the protection levels set at a time the stopping condition is reached to the task management controller, the task management controller determining whether to allocate a unit of the resource to a requestor from the current class based on whether the overallocation limit has not yet been reached and based on whether capacity remains under the protection level.

22. The apparatus of claim 21, wherein the stopping condition is one or more of a maximum number of iterations of (1)-(4) or a predefined maximum amount of time allowed to elapse while repeating (1)-(4).

23. The apparatus of claim 21, wherein the stopping condition occurs when one or more of the overallocation limit or the protection levels converge to within a predetermined threshold range between subsequent iterations of (1)-(4).

24. The apparatus of claim 21, wherein the values of the overallocation limit and the protection levels are determined substantially in real-time as requests for units of the resource are received.

25. The apparatus of claim 21, wherein the overallocation limit is limited by a predetermined overallocation upper bound.

26. The apparatus of claim 21, wherein request for a unit of the resource occurs in two parts comprising:

a first part that does not consume any of the resource and is associated with a first preference value; and

a second part associated with a second preference value, the second part being capable of succeeding or failing, wherein the protection levels are determined, at least in part, based on the first preference value and the second preference value

and further storing instructions for;

determining whether the second part succeeds or fails;

based on the determination, consuming a unit of the resource if the second part succeeds, or

failing to consume a unit of the resource if the second part fails.

27. The apparatus of claim 26, wherein the second part is associated with a value loss in the event of a failure of the second part.

28. The apparatus of claim 26, wherein the task management controller is configured to attempt to maximize a sum of the first preference value and the second preference value for the requestors.

29. The apparatus of claim 21, wherein a penalty is associated with allocating a unit of the resource but failing to provide the unit of the resource, at least one of the overallocation limit or the protection levels being determined at least in part based on the penalty.

30. The apparatus of claim 21, wherein the overallocation limit is initially determined by:

(a) determining an average wash probability representing a probability among the requestors that the requestors fail to use the allocated unit of the resource, averaged over the requestors, based on historical wash probabilities for the resource among the classes of requestors,

(b) determining an average value loss representing an amount of value lost in an event that a given requestor fails to use the allocated unit of the resource, averaged over the requestors, based on historical value loss percentages or a preconfigured default value,

(c) using the average wash probability and the average value loss to determine an estimated total value lost among requestors that are predicted to fail to use the allocated unit of the resource,

(d) using the average wash probability and a probability distribution representing a quantity of demand for the units of the resource to determine an estimated net capacity utilization,

(e) determining an average value representing a value among the requestors that are predicted to show up to utilize the allocated unit of the resource given the net capacity utilization; and

(f) adjusting the overallocation limit to maximize an expected value among the different classes of requestors, based at least in part on the average value as determined in (e) and the estimated total value lost as determined in (c).