COUPLED PLACEMENT OF ITEMS USING STABLE MARRIAGE TECHNIQUES

• US 20080291204A1
• Filed: 05/22/2007
• Published: 11/27/2008
• Est. Priority Date: 05/22/2007
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Korupolu, Madhukar R., Singh, Aameek
• Application Number:
  US11/752,288
• Publication Number:
  US 20080291204A1
• Time in Patent Office: Days
• US Class Current: 345/440
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

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.

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.

2. The computer program of claim 1, wherein the first profit value is determined from a first cost function and the second profit value is determined from a second cost function and the first cost function and the second cost function are each based on a distance value between the connected pair of first and second resource nodes.

3. The computer program of claim 1, further comprising program instructions for knapsack placement of more than one first element of the plurality of coupled items on at least one first resource node of the first resource node group.

4. The computer program of claim 3, further comprising program instructions for swapping placement of a pair of coupled items of the plurality of coupled items and keeping the change only if a lower cost to the resource graph results.

5. The computer program of claim 3, wherein each knapsack placement comprises maximizing a profit value while staying under a specified overall size.

6. The computer program of claim 5, wherein the profit value is determined by a cost difference between two different coupled item placements.

7. The computer program of claim 1, wherein each iteration comprises placement for every first element of each of the plurality of coupled items, followed by placement for every second element of each of the plurality of coupled items.

8. The computer program of claim 7, wherein each iteration further comprises a swap process comprising swapping the placement of a pair of coupled items of the plurality of coupled items, and keeping the change only if a lower cost to the resource graph results or else returning the pair of coupled items to the placement before the swap.

9. The computer program of claim 8, wherein the swap process is performed following placement for every second element of each of the plurality of coupled items.

10. The computer program of claim 8, wherein the iteration is repeated until a chosen termination criterion is met.

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.

12. The method of claim 11, wherein the first profit value is determined from a first cost function and the second profit value is determined from a second cost function and the first cost function and the second cost function are each based on a distance value between the connected pair of first and second resource nodes.

13. The method of claim 11, further comprising the step of knapsack placement of more than one first element of the plurality of coupled items on at least one first resource node of the first resource node group.

14. The method of claim 13, further comprising the step of swapping placement of a pair of coupled items of the plurality of coupled items and keeping the change only if a lower cost to the resource graph results.

15. The method of claim 13, wherein each knapsack placement comprises maximizing a profit value while staying under a specified overall size.

16. The method of claim 15, wherein the profit value is determined by a cost difference between two different coupled item placements.

17. The method of claim 11, wherein each iteration comprises placement for every first element of each of the plurality of coupled items, followed by placement for every second element of each of the plurality of coupled items.

18. The method of claim 17, wherein each iteration further comprises a swap process comprising swapping the placement of a pair of coupled items of the plurality of coupled items, and keeping the change only if a lower cost to the resource graph results or else returning the pair of coupled items to the placement before the swap.

19. The method of claim 18, wherein the swap process is performed following placement for every second element of each of the plurality of coupled items.

20. The method of claim 18, wherein the iteration is repeated until a chosen termination criterion is met.