COUPLED PLACEMENT OF ITEMS USING STABLE MARRIAGE TECHNIQUES
First Claim
1. A computer program embodied on a computer readable medium, comprising:
- program instructions for ranking a first resource node group for each first element of a plurality of coupled items, each of the plurality of coupled items having a first element and a second element;
program instructions for determining placement of each first element of the plurality of coupled items on one first resource node of the first resource node group by iteratively comparing in order of ranking a first profit value associated with each placement and placing the first element having a highest first profit value;
program instructions for ranking a second resource node group for each second element of the plurality of coupled items; and
program instructions for determining placement of each second element of the plurality of coupled items on one second resource node of the second resource node group by iteratively comparing in order of ranking a second profit value associated with each placement and placing the second element having a highest second profit value;
wherein each of the first element and the second element are to be placed on a connected pair of first and second resource nodes and the first profit value and the second profit value are based on a relationship between the connected pair of first and second resource nodes.
1 Assignment
0 Petitions
Accused Products
Abstract
A program and method are disclosed for placing coupled items in a resource graph using stable marriage techniques. Each coupled item requires resources of a first resource and a second resource in a resource graph. The resource nodes in the graph provide either the first resource or the second resource or both. Coupled placement defines each item as having two elements, one representing the first resource requirement and the other representing the second resource requirement, which must be placed on a pair of connected resource nodes. The objective is to place the coupled item elements among nodes of the resource graph without exceeding the first resource capacities and second resource capacities at resource nodes while keeping the total cost over all items small. A stable marriage process guides the placement that may also employ knapsacking of multiple elements on resource nodes and a swapping analysis to further optimize placement.
-
Citations
20 Claims
-
1. A computer program embodied on a computer readable medium, comprising:
-
program instructions for ranking a first resource node group for each first element of a plurality of coupled items, each of the plurality of coupled items having a first element and a second element; program instructions for determining placement of each first element of the plurality of coupled items on one first resource node of the first resource node group by iteratively comparing in order of ranking a first profit value associated with each placement and placing the first element having a highest first profit value; program instructions for ranking a second resource node group for each second element of the plurality of coupled items; and program instructions for determining placement of each second element of the plurality of coupled items on one second resource node of the second resource node group by iteratively comparing in order of ranking a second profit value associated with each placement and placing the second element having a highest second profit value; wherein each of the first element and the second element are to be placed on a connected pair of first and second resource nodes and the first profit value and the second profit value are based on a relationship between the connected pair of first and second resource nodes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method, comprising the steps of:
-
ranking a first resource node group for each first element of a plurality of coupled items, each of the plurality of coupled items having a first element and a second element; determining placement of each first element of the plurality of coupled items on one first resource node of the first resource node group by iteratively comparing in order of ranking a first profit value associated with each placement and placing the first element having a highest first profit value; ranking a second resource node group for each second element of the plurality of coupled items; and determining placement of each second element of the plurality of coupled items on one second resource node of the second resource node group by iteratively comparing in order of ranking a second profit value associated with each placement and placing the second element having a highest second profit value; wherein each of the first element and the second element are to be placed on a connected pair of first and second resource nodes and the first profit value and the second profit value are based on a relationship between the connected pair of first and second resource nodes. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification