US 10,853,144 B2Granted

Rules based decomposition of tasks for resource allocation

AssigneeMicrosoft Technology Licensing, LLC

InventorsRekha Nanda, Michael V. Ehrenberg, Yanfang Shen, Malvika Malge

Life of this patent

Estimating the term…

Loading patent…

Abstract

According to examples, an apparatus may include a processor and a memory on which are stored machine readable instructions that when executed by the processor, cause the processor to identify a plurality of tasks, identify a plurality of resources configured to execute the tasks, and decompose the plurality of tasks into multiple groups of tasks based on a plurality of rules applicable to the multiple groups of tasks. The instructions may also cause the processor to, for each group in the multiple groups of tasks, model the group of tasks and a subset of the plurality of resources as a respective resource allocation problem and assign a respective node of a plurality of nodes to solve the resource allocation problem.

Claims14

Dependent claims

An apparatus comprising:

a processor;
and
a memory on which is stored machine readable instructions that are to cause the processor to:
identify a plurality of tasks;
identify a plurality of resources configured to execute the tasks;
decompose the plurality of tasks into multiple groups of tasks based on a plurality of rules applicable to the multiple groups of tasks;
and
for each group in the multiple groups of tasks,
model the group of tasks and a subset of the plurality of resources as a respective resource allocation problem;
assign a respective processing device of a plurality of processing devices to solve the resource allocation problem;
direct the assigned processing device to solve the resource allocation problem;
receive solutions to the resource allocation problems;
determine whether execution of a received solution of the received solutions violates a rule of the plurality of rules;
based on a determination that execution of the received solution violates a rule of the plurality of rules,
reject the received solution;
identify the resource allocation problem corresponding to the rejected solution;
and
assign a processing node to solve the identified resource allocation problem while complying with the violated rule as a constraint to the identified resource allocation problem;
and
based on a determination that execution of the received solutions does not violate any of the rules in the plurality of rules,
generate a fulfillment plan based on the received solutions;
and
output the fulfillment plan.

20 more elements

A method comprising:

identifying, by a processor, a first rule applicable to a first set of tasks in a pool of tasks;
identifying, by the processor, a second rule applicable to a second set of tasks in the pool of tasks;
creating, by the processor, a first resource allocation problem for the first set of tasks;
creating, by the processor, a second resource allocation problem for the second set of tasks;
directing, by the processor, a first processing device to solve the first resource allocation problem;
directing, by the processor, a second processing device to solve the second resource allocation problem;
generating, by the processor, a task fulfillment plan using solutions to the first resource allocation problem and the second resource allocation problem;
receiving, by the processor, solutions to the first resource allocation problem and the second resource allocation problem;
determining, by the processor, whether execution of a received solution of the received solutions violates a rule of a plurality of rules;
based on a determination that execution of the received solution violates a rule of the plurality of rules, by the processor,
rejecting the received solution;
identifying the resource allocation problem corresponding to the rejected solution;
and
assigning a processing device to solve the identified resource allocation problem with the violated rule as a constraint to the identified resource allocation problem;
and
based on a determination that execution of the received solutions does not violate any of the rules in the plurality of rules, by the processor,
generating the fulfillment plan based on the received solutions;
and
outputting the fulfillment plan.

16 more elements

A non-transitory computer readable medium on which is stored machine readable instructions that when executed by a processor cause the processor to:

identify a pool of tasks;
identify a first rule applicable to a first task in the pool of tasks;
identify a second rule applicable to a second task in the pool of tasks;
generate an execution plan for implementation of the tasks;
determine a first resource allocation problem for implementation of the first task according to the execution plan while complying with the first rule;
determine a second resource allocation problem for implementation of the second task according to the execution plan while complying with the second rule;
direct a first processing device to solve the first resource allocation problem;
direct a second processing device to solve the second resource allocation problem;
generate a fulfillment plan for the tasks based on solutions to the first resource allocation problem and the second resource allocation problem;
receive solutions to the first resource allocation problem and the second resource allocation problem;
determine whether execution of a received solution of the received solutions violates a rule of a plurality of rules;
based on a determination that execution of the received solution violates a rule of the plurality of rules,
reject the received solution;
identify the resource allocation problem corresponding to the rejected solution;
and
direct a processing device to solve the identified resource allocation problem with the violated rule as a constraint to the identified resource allocation problem;
and
based on a determination that execution of the received solutions does not violate any of the rules in the plurality of rules,
generate the fulfillment plan based on the received solutions;
and
output the fulfillment plan.

18 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/917,422Filed 9 Mar 2018 · us provisional application
Priority: 9 Mar 2017
Published: US 2018/0260253 A113 Sep 2018
Granted: 1 Dec 2020
Term ends: Not estimatedThe source records don’t support an estimate.

Classification10 codes

G06F 9/5038
The resource being a machine, e.g. CPUs, Servers, Terminals: considering the execution order of a plurality of tasks, e.g. taking priority or time…
G06F 9/4806
Program initiating; Program switching, e.g. by interrupt: task transfer initiation or dispatching
G06F 9/5027
To service a request: the resource being a machine, e.g. CPUs, Servers, Terminals
G06F 11/3476
Performance evaluation by tracing or monitoring: data logging