Method and apparatus for discrete activity resourse allocation through cardinality constraint generation

• US 5,216,593 A
• Filed: 01/24/1991
• Issued: 06/01/1993
• Est. Priority Date: 01/24/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Escudero, Laureano F., Dietrich, Brenda L.
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): Hazard, Jennifer L.
• Application Number:
  US07/645,385
• Time in Patent Office: 859 Days
• Field of Search: 364/401, 364/402, 364/403, 364/468, 364/156
• US Class Current: 345/467
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0875 Itemisation or classification of parts, supplies or services, e.g. bill of materials

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.