US6044361A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast inventory matching algorithm for the process industry
Assignee: Google LLC
•
Filing: 1998-03-24
•
Granted: 2000-03-28
•
Expires: 2018-03-24
Abstract
Abstract A fast computer implemented method generates near-optimal solutions to the multi-objective inventory matching problem by solving for multiple objectives simultaneously and generating multiple non-dominating solutions. The method implements a multi-assignment backjumping algorithm that consists of three steps. The first step is a rappeling step in which a feasible solution is created by applying Iterative Bipartite Matching and maximum flow algorithm. Near-optimal feasible solutions are stored in a non dominated set. The second step is to use a multi-key sort to identify undesirable matches in a given feasible solution. The third step is backlifting the solution by removing undesirable matches from the feasible solution and places those undesirable matches on a no good set of matches. If the feasible solution is non-dominated, a copy is stored in a non-dominated set. The feasible solution is finally provided as input to the repelling step.
Inventors
- 👤 Jayant R. Kalagnanam
- 👤 Ho Soo Lee
- 👤 Mark Elliot Trumbo
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 13:30
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/04; G06Q10/08; G06Q10/087; G06Q10/0872; G06Q10/0875
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
131 words
A computer implemented method for quickly finding multiple non-dominated near optimal inventory matching results comprising the steps of: creating a feasible solution by applying iterative bipartite matching on a given initial solution and a no good set of matches, wherein the no good set of matches is initially empty; refining the feasible solution to decrease unused weight using max flow analysis; using a multi-key sort to identify undesirable matches in the given feasible solution; backlifting the feasible solution by removing the undesirable matches from the feasible solution and placing the removed undesirable matches in a no good set; and if the feasible solution is near optimal, storing the feasible solution in a non dominated set and providing a copy of the feasible solution as input to the iterative bipartite matching step.
Claim 2
Dependent Claim
131 words
A computer implemented method for quickly finding multiple non-dominated near optimal inventory matching results comprising the steps of: creating a feasible solution by applying iterative bipartite matching on a given initial solution and a no good set of matches, wherein the no good set of matches is initially empty; refining the feasible solution to decrease unused weight using max flow analysis; using a multi-key sort to identify undesirable matches in the given feasible solution; backlifting the feasible solution by removing the undesirable matches from the feasible solution and placing the removed undesirable matches in a no good set; and if the feasible solution is near optimal, storing the feasible solution in a non dominated set and providing a copy of the feasible solution as input to the iterative bipartite matching step.
Claim 3
Dependent Claim
89 words
The computer implemented method recited in claim 1 wherein creating a feasible solution comprises the steps of: creating an edge weighted bipartite graph, said graph comprising nodes corresponding to unfilled orders, nodes corresponding to slabs with unused weight, and edges corresponding to feasible matches avoiding the set of no good matches; setting each edge weight of the graph using a monotone function of a feasibly applicable order weight and a resulting unused weight of the slab; and performing a maximum weight bipartite matching of the edge weighted bipartite graph.
Claim 4
Dependent Claim
111 words
The computer implemented method recited in claim 1, wherein refining the feasible solution using max flow analysis comprises the steps of: creating a flow graph comprising a source node s and a sink node t, intermediate nodes representing unfilled orders, intermediate nodes representing slabs with unused weight, edges corresponding feasible matches avoiding the set of no good matches with a very large flow capacity, edges from source nodes to order nodes with a feasible capacity based on unfilled order quantity, and edges from slab nodes to the sink node with a feasible capacity based on unused slab weight; and finding a maximum flow from the source node to the sink node.
Claim 5
Dependent Claim
54 words
The computer implemented method recited in claim 1, wherein using a multi-key sort comprises the steps of: determining a ratio of unused weight and applied quantity for each slab; sorting slabs in a non-decreasing order of the ratio; and identifying a set of n slabs whose aggregate ratio does not exceed a prespecified limit.
Claim 6
Dependent Claim
30 words
The computer implemented method recited in claim 1, further comprising the step of providing application instructions, where the instructions may be used by a shop floor manager in decision making.
Claim 7
Dependent Claim
24 words
The computer implemented method recited in claim 1, further comprising the step of displaying the feasible solution in graphical form on a display device.
References Cited (Backward Citations)
US5251290A
Cited
US5712989A
Cited
US5463555A
Cited
US5737728A
Cited
US5826236A
Cited
US5841958A
Cited
US5699259A
Cited
US5671362A
Cited
US5734592A
Cited
US5831857A
Cited
US5691895A
Cited
US5808891A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-28 | 2003-09-27 | 2004-03-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-28 | 2007-09-27 | 2008-03-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-28 | 2011-09-27 | 2012-03-28 | $7700.00 | Window Closed / Lapsed |