Method and apparatus for optimally allocating resources

• US 5,343,388 A
• Filed: 10/29/1993
• Issued: 08/30/1994
• Est. Priority Date: 08/31/1990
• Status: Expired due to Term

• Current Assignee: Dag Wedelin
• Original Assignee: Dag Wedelin
• Inventors: Wedelin, Dag
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): BAI, ARI
• Application Number:
  US08/143,235
• Time in Patent Office: 305 Days
• Field of Search: 364/400, 364/401, 364/402, 364/403
• US Class Current: 705/7.13
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change

Abstract

A method and apparatus for optimizing resource allocation is disclosed which uses a probabilistic relaxation network technique for obtaining an optimal or near optimal assignment solution. A network of nodes and arcs is created. Inputs to the arcs are calculated disregarding the old outputs from the arcs, the influences on the nodes are calculated based on the inputs to the arcs and the new values for the nodes are calculated based on the influences on the node.

Claims

1. A method of outputting the assignment of available personnel to the plurality of tasks so as to effectively accomplish the tasks, using an apparatus for outputting an optimized assignment of available personnel to a plurality of tasks so as to reduce the cost of accomplishing the tasks using a programmed computer, the apparatus comprising preprocessor means for inputting a plurality of legality constraints and outputting a plurality of capacity constraints and variables which are influenced by the capacity constraints, the preprocessor means including a node generator for generating a plurality of nodes representing each possible assignment, a translator for translating a plurality of legality constraints into compatable q-functions, and an arc generator for generating a plurality of arcs forming constraints on the assignments, wherein the variables represent the nodes and the constraints represent the arcs, the method comprising the steps of:

determining the plurality of tasks to be filled by the available personnel;

assigning costs for each of said tasks;

outputting the plurality of variables and influences on said variables in the form of the capacity constraints, from said plurality of tasks and costs using said preprocessor means;

iteratively updating the influences on said variables using a probabilistic relaxation network technique so as to minimize the total of the costs of said tasks;

terminating said iterative updating steps when the influences remain stable for a predetermined number of iterations;

assigning said personnel to said tasks in accordance with the updated influences; and

outputting the assignment of personnel to said tasks.

2. An apparatus for outputting an optimized assignment of available personnel to a plurality of tasks so as to reduce the cost of accomplishing the tasks using a programmed computer, the apparatus comprising:

preprocessor means for inputting a plurality of legality constraints and outputting a plurality of capacity constraints and variables which are influenced by the capacity constraints;

first processor means for calculating inputs for each of the variables to the capacity constraints;

second processor means for updating the influences for each capacity constraint;

third processor means for calculating updated values for the variables;

stopping processor means for determining when a predetermined stopping criteria has been satisfied;

means for assigning the available personnel to the tasks in accordance with the updating values of the variables when the predetermined stopping criteria is satisfied; and

output means for outputting the assignments of available personnel to the tasks, wherein said preprocessor means comprises;

a node generator for generating a plurality of nodes representing each possible assignment;

a translator for translating a plurality of legality constraints into computable q-functions; and

an arc generator for generating a plurality of arcs forming constraints on the assignments, wherein said variables represent said nodes and said constraints represent said arcs and wherein said arcs and nodes are passed to said first, second, third, and stopping processor means, successively.

3. A method of outputting an optimal allocation of available resources and available facilities using an apparatus for outputting an optimized assignment of available personnel to a plurality of tasks so as to reduce the cost of accomplishing the tasks using a programmed computer, the apparatus including preprocessor means for inputting a plurality of legality constraints and outputting a plurality of capacity constraints and variables which are influenced by the capacity constraints, the preprocessor means including a node generator for generating a plurality of nodes representing each possible assignment, a translator for translating a plurality of legality constraints into computable q-functions, and an arc generator for generating a plurality of arcs forming constraints on the assignments, wherein the variables represent the nodes and the constraints represent the arcs, comprising the steps of:

creating a network of said nodes and said arcs using said preprocessor means, said arcs connecting various ones of said nodes, where the nodes represent assignments of a resource and a facility and the arcs represent constraints on the assignments;

iteratively performing the following steps until a stopping criteria is reached representing that the network is in a stable state;

calculating inputs to the arcs r_ik (x_i) disregarding the old outputs from the arcs s_ik (x_i);

calculating the influences on the nodes s_ik (x_i) based on the inputs to the arcs r_ik (x_i); and

calculating the new values for the nodes p(x_i) based on the influences on the nodes s_ik (x_i);

allocating said resources and facilities in an optimal manner in accordance with the stable state reached by the network; and

outputting the optimal allocation of resources and facilities allocated in said step of allocating.

4. The method as set forth in claim 3, wherein the step of iteratively performing is performed for all k in parallel.

5. The method as set forth in claim 4, wherein the inputs to the arcs are calculated in accordance with the formula, for all i,x_i ε

X_k in parallel;

##EQU19##

6. The method as set forth in claim 5, wherein the influences on the nodes are calculated in accordance with the formula, for all i,x_i,ε

X_k in parallel;

##EQU20##

7. The method as set forth in claim 6, wherein the new values for the nodes are calculated in accordance with the formula, for all i,x_i,ε

X_k in parallel;

space="preserve" listing-type="equation">p(x.sub.i)∝

r.sub.ik (x.sub.i)s.sub.ik (x.sub.i).