US5235508A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automated resource allocation cutting stock arrangement using random cut patterns
Assignee: Nokia Bell Labs
•
Filing: 1990-05-31
•
Granted: 1993-08-10
•
Expires: 2010-05-31
Abstract
Abstract An arrangement is disclosed for allocating a constrained common resource among a plurality of demands for the resource. The arrangement includes generating a set of patterns as candidates for a recommended solution, setting goals or constraints for a pattern to meet before the pattern becomes a candidate for the recommended solution, searching the set of patterns and determining those patterns that meet the goals, and appending those patterns that meet the goals to the recommended solution. A random distribution based on the demand for the resource over a multi-dimension space can be generated. Responsive to the random distribution, a plurality of feasible patterns can be generated. Responsive to the feasible patterns, a multiplicity ratio may be generated. Responsive to a multiplicity ratio and to its corresponding feasible pattern, the plurality of feasible patterns may be reduced to a single feasible pattern, which can be included in the recommended solution. The generating and reducing can be repeated until the goals are met whereupon the resultant multiplicity ratios and feasible patterns can be provided as the recommended solution, and, responsive to the recommended solution, the common resource can be allocated among the plurality of demands.
Inventors
- 👤 Yuval V. Lirov
- 👤 Moshe Segal
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 12:17
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/04; G06Q10/043
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
192 words
A method for allocating a constrained common resource among a plurality of different levels of demands for the resource, said method comprising the steps of: (a) generating a random distribution based on the plurality of demands for the resource, (b) generating as a function of the random distribution a plurality of feasible patterns each indicative of allocating the resource among the plurality of demands, (c) generating a multiplicity value for each of said feasible patterns as a function of the levels of the demands, (d) processing each said multiplicity value and its corresponding feasible pattern to reduce the plurality of feasible patterns to a single feasible pattern which meets a set of goals and which can be included in a partial recommended solution of allocating the resource, thereby reducing the levels of the demands to respective residual levels, (e) processing the residual levels of the demands by repeating steps (a), (b), (c) and (d) until the goals are met, (f) providing each said single feasible pattern and the associated multiplicity value as a recommended solution, and (g) allocating the common resource among the plurality of demands in accordance with the recommended solution.
Claim 2
Independent Claim
192 words
A method for allocating a constrained common resource among a plurality of different levels of demands for the resource, said method comprising the steps of: (a) generating a random distribution based on the plurality of demands for the resource, (b) generating as a function of the random distribution a plurality of feasible patterns each indicative of allocating the resource among the plurality of demands, (c) generating a multiplicity value for each of said feasible patterns as a function of the levels of the demands, (d) processing each said multiplicity value and its corresponding feasible pattern to reduce the plurality of feasible patterns to a single feasible pattern which meets a set of goals and which can be included in a partial recommended solution of allocating the resource, thereby reducing the levels of the demands to respective residual levels, (e) processing the residual levels of the demands by repeating steps (a), (b), (c) and (d) until the goals are met, (f) providing each said single feasible pattern and the associated multiplicity value as a recommended solution, and (g) allocating the common resource among the plurality of demands in accordance with the recommended solution.
Claim 3
Dependent Claim
58 words
The method defined in claim 1 wherein the step of generating a plurality of feasible patterns further comprises the steps of: (h) generating a plurality of random patterns as possible candidates for the recommended solution, and (i) selecting as the plurality of feasible patterns those ones of the random patterns which satisfy the constraints of the common resource.
Claim 4
Dependent Claim
82 words
The method defined in claim 1 wherein the step of generating a multiplicity value further comprises the steps of: (h) responsive to one of the feasible patterns and to the demands, generating a plurality of multiplicity ratios as candidates for the multiplicity value, (i) responsive to the multiplicity ratios, generating the multiplicity value for the feasible pattern to be the integer part of the smallest multiplicity ratio for the feasible pattern, and (j) repeating steps (h) and (i) for all feasible patterns.
Claim 5
Dependent Claim
84 words
The method defined in claim 1 wherein the step of reducing the plurality of feasible patterns to a single feasible pattern further comprises the steps of: (h) generating the residual demand for each feasible pattern, (i) generating an evaluation ratio as a function of the associated multiplicity value and the residual demand, (j) comparing the evaluation ratios for each feasible pattern, and (k) responsive to the smallest evaluation ratio, appending the corresponding residual demand, feasible pattern, and multiplicity value to the partial recommended solution.
Claim 6
Dependent Claim
195 words
Apparatus for allocating a constrained common resource among a plurality of demands for the resource, said demands having different levels of demand said apparatus comprising means for generating a random distribution based on the plurality of demands for the resource, means for generating as a function of the random distribution a plurality of feasible patterns each indicative of allocating the resource among the plurality of demands, means for generating a multiplicity value for each of said feasible patterns as a function the levels of the demands, means for processing each said multiplicity value and its corresponding feasible pattern to reduce the plurality of feasible patterns to a single feasible pattern which meets a set of goals and which can be included in a partial recommended solution of allocating the resource, thereby reducing the levels of the demands to respective residual levels, means for repeating the generating and processing using the residual levels of the demands until the goals are met, means for providing each said single feasible pattern and the associated multiplicity value as a recommended solution, and means for allocating the common resource among the plurality of demands in accordance with the recommended solution.
Claim 7
Dependent Claim
195 words
Apparatus for allocating a constrained common resource among a plurality of demands for the resource, said demands having different levels of demand said apparatus comprising means for generating a random distribution based on the plurality of demands for the resource, means for generating as a function of the random distribution a plurality of feasible patterns each indicative of allocating the resource among the plurality of demands, means for generating a multiplicity value for each of said feasible patterns as a function the levels of the demands, means for processing each said multiplicity value and its corresponding feasible pattern to reduce the plurality of feasible patterns to a single feasible pattern which meets a set of goals and which can be included in a partial recommended solution of allocating the resource, thereby reducing the levels of the demands to respective residual levels, means for repeating the generating and processing using the residual levels of the demands until the goals are met, means for providing each said single feasible pattern and the associated multiplicity value as a recommended solution, and means for allocating the common resource among the plurality of demands in accordance with the recommended solution.
Claim 8
Dependent Claim
65 words
The apparatus defined in claim 5 wherein the means for generating a plurality of feasible patterns further comprises: means responsive to the random distribution for generating a plurality of random patterns as possible candidates for the recommended solution, and means responsive to the random patterns for selecting generating as feasible patterns those ones of the random patterns, which satisfy the constraints of the common resource.
Claim 9
Dependent Claim
78 words
The apparatus defined in claim 5 wherein the means for generating a multiplicity value further comprises: means responsive to the feasible patterns and to the demands for generating a plurality of multiplicity ratios as candidates for the multiplicity value, means responsive to the multiplicity ratios for generating the multiplicity value for the feasible pattern to be the integer part of the smallest multiplicity ratio for the feasible pattern, and means for repeating the generating for all feasible patterns.
Claim 10
Dependent Claim
86 words
The apparatus defined in claim 5 wherein the means for reducing the plurality of feasible patterns to a single feasible pattern further comprises: means for generating the residual demand for each feasible pattern, means for generating an evaluation ratio as a function of the associated multiplicity value and the residual demand, means for comparing the evaluation ratios for each feasible pattern, and means responsive to the smallest evaluation ratio for appending the corresponding residual demand, feasible cut pattern, and multiplicity value to the partial recommended solution.
References Cited (Backward Citations)
US3339182A
Cited
US3488479A
Cited
UST918013I4
Cited
US4885686A
Cited
US4947322A
Cited
US5128860A
Cited
US5077661A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-08-09 | 1997-02-08 | 1997-08-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-08-09 | 2001-02-08 | 2001-08-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-08-09 | 2005-02-08 | 2005-08-10 | $7700.00 | Window Closed / Lapsed |