Patent US5216593A successfully refreshed from Google Patents.
US5216593A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for discrete activity resourse allocation through cardinality constraint generation
Assignee: International Business Machines Corp
•
Filing: 1991-01-24
•
Granted: 1993-06-01
•
Expires: 2011-01-24
Abstract
Abstract The required computational effort in the areas of production planning and logistics, scheduling, distribution and resource allocation is reduced by a procedure for solving a Discrete Activity Resource Allocation (DARA) problem. The procedure begins by reducing all activities and resources which do not contribute to maximizing benefit. Thus, all infeasible and non-profitable activities are discarded and all non-constraining resources are discarded, thereby considerably simplifying the solution to the problem. Next, an automatic mathematical model formulation of the DARA problem is performed. Based on this model, a list of cliques and covers are generated. The linear relaxation of the DARA problem using standard linear programming software is solved, and the generated list of clique and cover induced inequalities is scanned to select a set violated by the solution of the linear relaxation of the DARA problem. For those inequalities found, constraints are appended to the formulated DARA problem, forming another DARA problem with the same set of variables, but with additional constraints. The new DARA problem is then solved using the previous solution as the start of the solution. Based on this solution, the generated list of clique and cover induced inequalities is again scanned, and this process is continued until no violated inequalities are found. At this point in the procedure, conventional branch-and-bound or branch-and-cut routines are used to solve the enlarged DARA problem. The solution yields the optimal resource allocation producing the maximum benefit.
Inventors
- 👤 Brenda L. Dietrich
- 👤 Laureano F. Escudero
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 23:18
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/06; G06Q10/08; G06Q10/087; G06Q10/0875
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
291 words
A computer based system for discrete activity resource allocation in the manufacture of large, indivisible or highly customized products comprising: order entry/tracking means for collecting orders and maintaining a list of all outstanding orders; a bill of materials database and a machine/manpower requirements database; bill of material explosion means responsive to said order entry/tracking means for accessing said bill of materials database and transforming said orders into raw material requirements; machine requirements explosion means responsive to said order entry/tracking means for accessing said machine/manpower requirements database and determining machine and manpower requirements of each order; inventory sensor means for determining available quantity of raw material; shop floor sensor means for determining availability of machines and manpower; profit analyzer means responsive to said order entry/tracking means, said bill of material explosion means and said machine requirements explosion means for determining a profit associated with each order; data preprocessing means responsive to said inventory sensor means, said shop floor sensor means and said profit analyzer means for eliminating orders that cannot be produced and resources that will not affect order selection; model generator means responsive to said data preprocessing means for mathematically modeling consumption of resources by orders and an availability of resources; cardinality constraint generator means responsive to said model generator means for determining simple choices implied by a mathematical model generated by said model generator means; and interactive decision display means for displaying to a user choices generated by said cardinality constraint generator means to assist the user in deciding which orders to make and receiving from the user selection and rejection of orders, said interactive decision display means further providing inputs to said order entry/tracking means and said data preprocessing means based on said user selection and rejection of orders.
Claim 2
Dependent Claim
291 words
A computer based system for discrete activity resource allocation in the manufacture of large, indivisible or highly customized products comprising: order entry/tracking means for collecting orders and maintaining a list of all outstanding orders; a bill of materials database and a machine/manpower requirements database; bill of material explosion means responsive to said order entry/tracking means for accessing said bill of materials database and transforming said orders into raw material requirements; machine requirements explosion means responsive to said order entry/tracking means for accessing said machine/manpower requirements database and determining machine and manpower requirements of each order; inventory sensor means for determining available quantity of raw material; shop floor sensor means for determining availability of machines and manpower; profit analyzer means responsive to said order entry/tracking means, said bill of material explosion means and said machine requirements explosion means for determining a profit associated with each order; data preprocessing means responsive to said inventory sensor means, said shop floor sensor means and said profit analyzer means for eliminating orders that cannot be produced and resources that will not affect order selection; model generator means responsive to said data preprocessing means for mathematically modeling consumption of resources by orders and an availability of resources; cardinality constraint generator means responsive to said model generator means for determining simple choices implied by a mathematical model generated by said model generator means; and interactive decision display means for displaying to a user choices generated by said cardinality constraint generator means to assist the user in deciding which orders to make and receiving from the user selection and rejection of orders, said interactive decision display means further providing inputs to said order entry/tracking means and said data preprocessing means based on said user selection and rejection of orders.
Claim 3
Dependent Claim
72 words
The computer based system for discrete activity resource allocation recited in claim 1 further comprising: optimization model controller means for updating said mathematical model based on said user selection and rejection of orders; and optimization model solver means, including said cardinality constraint generator means, called by said optimization model controller means for generating an allocation of resources which is optimal among all allocations which said user selection and rejection of orders permits.
Claim 4
Dependent Claim
43 words
The computer based system for discrete activity resource allocation as recited in claim 2 further comprising floor control means responsive to said optimization model solver means for generating work orders and releasing inventory to a shop floor for orders selected by the user.
Claim 5
Dependent Claim
161 words
A computer performed process for discrete activity resource allocation in the manufacture of large, indivisible or highly customized products comprising: collecting orders and maintaining a list of all outstanding orders using an order entry/tracking system; accessing a bill of materials database and transforming orders into raw material requirements; accessing a machine/manpower requirements database and determining machine and manpower requirements of each order; determining available quantity of raw material using inventory sensors; determining the availability of machines and manpower using shop floor sensors; determining a profit associated with each order; eliminating orders that cannot be produced and resources that will not affect order selection; mathematically modeling consumption of resources by orders and an availability of resources; determining simple choices implied by a mathematical model generated by a model generator; and interactively displaying to a user the choices implied by said mathematical model to assist the user in deciding which orders to make and receiving from the user selection and rejection of orders.
Claim 6
Dependent Claim
161 words
A computer performed process for discrete activity resource allocation in the manufacture of large, indivisible or highly customized products comprising: collecting orders and maintaining a list of all outstanding orders using an order entry/tracking system; accessing a bill of materials database and transforming orders into raw material requirements; accessing a machine/manpower requirements database and determining machine and manpower requirements of each order; determining available quantity of raw material using inventory sensors; determining the availability of machines and manpower using shop floor sensors; determining a profit associated with each order; eliminating orders that cannot be produced and resources that will not affect order selection; mathematically modeling consumption of resources by orders and an availability of resources; determining simple choices implied by a mathematical model generated by a model generator; and interactively displaying to a user the choices implied by said mathematical model to assist the user in deciding which orders to make and receiving from the user selection and rejection of orders.
Claim 7
Dependent Claim
48 words
The computer performed process discrete activity resource allocation recited in claim 4 further comprising: updating said mathematical model based on said user selection and rejection of orders; and generating an allocation of resources which is optimal among all allocations which said user selection and rejection of orders permits.
Claim 8
Dependent Claim
32 words
The computer performed process for discrete activity resource allocation as recited in claim 5 further comprising generating work orders and releasing inventory to a shop floor for orders selected by the user.
Claim 9
Dependent Claim
139 words
An interactive computer performed method for discrete activity resource allocation to generate and evaluate a production plan comprising the steps of: inputting data related to inventory and machine availability; reducing the number of all activities and resources which do not contribute to maximizing benefit by discarding all infeasible and non-profitable activities and discarding all non-constraining resources, thereby simplifying the solution to the problem of allocating activities and resources; automatically formulating a mathematical model of a discrete activity resource allocation problem using activities and resources which remain after said reducing step; generating a list of cardinality constraints from said mathematical model; and displaying to a user choices implied by said mathematical model to assist the user in deciding which orders to be filled and receiving inputs from said user selecting and rejecting orders to be filled by said production plan.
Claim 10
Dependent Claim
139 words
An interactive computer performed method for discrete activity resource allocation to generate and evaluate a production plan comprising the steps of: inputting data related to inventory and machine availability; reducing the number of all activities and resources which do not contribute to maximizing benefit by discarding all infeasible and non-profitable activities and discarding all non-constraining resources, thereby simplifying the solution to the problem of allocating activities and resources; automatically formulating a mathematical model of a discrete activity resource allocation problem using activities and resources which remain after said reducing step; generating a list of cardinality constraints from said mathematical model; and displaying to a user choices implied by said mathematical model to assist the user in deciding which orders to be filled and receiving inputs from said user selecting and rejecting orders to be filled by said production plan.
Claim 11
Dependent Claim
170 words
The interactive computer performed method for discrete activity resource allocation to generate and evaluate a production plan recited in claim 7 further comprising the steps of: solving a linear relaxation of the discrete activity resource allocation problem by linear programming; scanning a generated list of constraints to select a set violated by the solution of the linear relaxation of said discrete activity resource allocation problem; for inequalities found, appending constraints to the formulated mathematical model of a discrete activity resource allocation problem to thereby form a new discrete activity resource allocation problem with the same set of variables but with additional constraints; solving the new discrete activity resource allocation problem using a previous solution as a start of the solution of the new discrete activity resource allocation problem; and based on the solution of the new discrete activity resource allocation problem, scanning the generated list of constraints again and repeating the steps of appending constraints and solving the new discrete activity resource allocation problem until no violated inequalities are found.
Claim 12
Dependent Claim
49 words
The interactive computer performed method for discrete activity resource allocation to generate and evaluate a production plan recited in claim 8 further comprising the step of using conventional branch-and-bound or branch-and-cut routines, solving an enlarged discrete activity resource allocation problem to yield an optimal resource allocation producing maximum benefit.
Claim 13
Dependent Claim
44 words
The interactive computer performed method for discrete activity resource allocation to generate and evaluate a production plan recited in claim 9 further comprising the step of controlling execution of said plan by generating work orders and releasing inventory for orders selected by the user.
References Cited (Backward Citations)
US4459663A
Cited
US4827423A
Cited
US4821197A
Cited
US4887208A
Cited
US5101352A
Cited
US5089970A
Cited
US5119307A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-05-31 | 1996-11-30 | 1997-06-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-05-31 | 2000-11-30 | 2001-06-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-05-31 | 2004-11-30 | 2005-06-01 | $7700.00 | Window Closed / Lapsed |