Optimization of manufacturing resource planning5630070Abstract A method for constrained material requirements planning, optimal resource allocation, and production planning provides for an optimization of a manufacturing process by designating the amounts of various manufactured products to be produced, which products include both end products as well as subassemblies to be employed in the manufacture of one or more of the end products. In order to accomplish the optimization, the method employs an objective function such as the maximization of income in a situation wherein there are limitations on the inventory of raw materials and tools to be employed in the manufacturing process. Data describing elemental steps in the manufacturing process for the production of each end product, as well as the quantity or demand for each end product which is to be supplied, are presented as a set of linear mathematical relationships in matrix form to be inserted in a computer which determines the optimum number of each end product in accordance with an LP optimization algorithm. The matrix contains bill of material data, and various constraints such as a constraint on the sum of products shipped and used as subassemblies, and constraints based on inventory, on available time for use of resources such as tools, and on inventory left over from an early production run for a later run. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
TABLE 1
______________________________________
Plain omelet $2.00 Plain sandwich $1.00
3 eggs 2 slices bread
1 tsp butter
Cheese omelet
$3.00 Cheese sandwich $1.50
1 plain omelet 1 plain sandwich
3 oz. cheese 3 oz. cheese
Ham omelet $3.50 Ham sandwich $2.50
1 plain omelet 1 plain sandwich
3 oz. ham 3 oz. ham
Ham & Cheese $4.00 Ham & cheese $2.50
omelet sandwich
1 plain omelet 1 plain sandwich
2 oz. cheese 2 oz. ham
2 oz. ham 2 oz. cheese
Vegetable omelet
$2.75 Ham & egg sandwich
$3.50
1 plain omelet 1 plain sandwich
2 oz. mushrooms 1 egg
2 oz. green pepper 1 oz. ham
______________________________________
The invention deals with a constrained production planning problem. It is an object of the invention to determine the quantity to produce of each type of omelet and sandwich. The methodology of the invention is explained, in terms of the foregoing working situation as follows. The mathematical formulation of this problem requires 10 decision variables. We define: X.sub.1 =number of plain omelets to produce x.sub.2 =number of cheese omelets to product x.sub.3 =number of ham omelets to produce x.sub.4 =number of ham and cheese omelets to produce x.sub.5 =number of vegetable omelets to produce x.sub.6 =number of plain sandwiches to produce x.sub.7 =number of cheese sandwiches to produce x.sub.8 =number of ham sandwiches to produce x.sub.9 =number of ham and cheese sandwiches to produce x.sub.10 =number of ham and egg sandwiches to produce The mathematical formulation of this problem requires 9 material balance constraints, one for each of the 7 raw ingredients (eggs, butter, mushrooms, peppers, ham, cheese, bread) and one for each of the two "subassemblies" (plain omelet, plain sandwich). The formulation is presented in two sets of constraints, set forth in equation sets (1) and (2). Equation set (1) has nine lines corresponding to the nine constraints. The variables to the left of the inequality sign are arranged so that variables representing the same food product in a plurality of the lines appear in the same column. The column of variables to the right of the inequality signs are recognized as being the inventory of Table 3. The first seven lines relate to the seven raw food ingredients of the inventory, and the last two lines relate to the two subassemblies (plain omelet and plain sandwich) of the inventory. In the first ten columns of variables from the left, each column represents a specific one of the food products to be manufactured as listed in Table 1. Also, the first seven row elements of each column, presents the ingredients, exclusive of any required subassembly, for producing the food product. The coefficient for each variable designates the quantity of the food product to be employed in accordance with the recipes of Table 1. The first column of variables at the left side of the equation set discloses, in its first seven row elements, the amount of eggs and butter to be employed in making a single plain omelet. The second column of variables from the left discloses, in its first seven row elements, the amount of cheese to produce a single cheese omelet. In similar fashion, the remaining ones of the first ten columns from the left, in their respective first seven row elements, disclose ingredients for the remaining food products of Table 1. The eighth row of equation set (1) deals with the constraint that the sum of all plain sandwiches employed in subassemblies minus the amount of plain sandwiches produced must not exceed inventory. The ninth row, which includes an entry (to be described hereinafter) in the eleventh column from the left, deals with the constraint that the sum of all plain omelets employed in subassemblies plus the amount of plain omelets eaten directly minus the amount of plain omelets produced must not exceed inventory. With respect to equation set (2), it is noted that in the production of any one of the foregoing ten food products of Table 1, the number produced cannot be less than zero. This presents a set of non-negativity constraints for production of the food products which are set forth in equation set 2. The variables representing the respective food products are set forth individually in separate lines of the equation set, and are arranged in columnar form corresponding to the columns of equation set 1. ##STR1## These two sets of constraints describe the set of all possible combinations of products that can be made with the available ingredients. Note that these constraints permit combinations that are inconsistent with the product demand. For example, the point x.sub.1 =12, x.sub.2 =12, x.sub.3 =0, x.sub.4 =0, x.sub.5 =0, x.sub.6 =0, x.sub.7 =0, x.sub.8 =0, x.sub.9 =0, x.sub.10 =0, which corresponds to making 12 cheese omelets and 12 plain omelets that are used in the cheese omelets and none of the other items, satisfies all of the material availability constraints and the non-negativity constraints. However, since the demand for cheese omelets is only 4, the point (12, 12, 0,0,0,0,0,0,0,0) is not likely to represent a good allocation of the available ingredients. In order to restrict the formulation to include only production combinations that are consistent with the product demand, additional decision variables must be introduced, and the material availability constraints (1) must be altered to include these additional variables. For each product that has a demand, a "shipment" variable, representing the amount of that demand that is satisfied, is required. Specifically, for this example we let: s.sub.1 =number of plain omelets served s.sub.2 =number of cheese omelets served s.sub.3 =number of ham omelets served s.sub.4 =number of ham and cheese omelets served s.sub.5 =number of vegetable omelets served s.sub.7 =number of cheese sandwiches served s.sub.8 =number of ham sandwiches served s.sub.9 =number of ham and cheese sandwiches served s.sub.10 =number of egg and ham sandwiches served Note that s.sub.6 is not needed, since there is no demand for plain sandwiches. The material availability constraints for subassemblies that have demand (e.g., plain omelet) are altered to reflect the facts that the sum of the quantity that is served, plus the quantities that are used in other products, cannot exceed the quantity that is available from production and inventory. Thus the final equation of (1) is given by -x.sub.1 +x.sub.2 +x.sub.3 +x.sub.4 +x.sub.5 +s.sub.1 .ltoreq.0(plain omelet) For each of the end products, we add constraints that say that the amount of the produced served cannot exceed the amount of the product available from production and inventory. -x.sub.2 +s.sub.2 .ltoreq.0 (cheese omelet) -x.sub.3 +s.sub.3 .ltoreq.0 (ham omelet) -x.sub.4 +s.sub.4 .ltoreq.0 (ham and cheese omelet) -x.sub.5 +s.sub.5 .ltoreq.0 (vegetable omelet) -x.sub.7 +s.sub.7 .ltoreq.0 (cheese sandwich) -x.sub.8 +s.sub.8 .ltoreq.0 (ham sandwich) -x.sub.9 +s.sub.9 .ltoreq.0 (ham and cheese sandwich) -x.sub.10 +s.sub.10 .ltoreq.0 (ham and egg sandwich) An additional set of constraints is required to reflect the fact that one cannot serve more than has been demanded: ##EQU1## Finally, the quantity of each product served must not be less than 0. ##EQU2## When writing formulas such as (1)-(5) above in matrix notation, the not-negatively constraints (2) and (5) are usually not included in the matrix. Thus we can rewrite (1)-(5) above as: ##EQU3## The A matrix and b vector are shown in FIG. 8 and represent constraints (1), (3), (4). x=(x.sub.1, x.sub.x, x.sub.3, x.sub.4, x.sub.5, x.sub.6, x.sub.7, x.sub.8, x.sub.9, x.sub.10) s=(s.sub.1, s.sub.2, s.sub.3, s.sub.4, s.sub.5, s.sub.7, s.sub.8, s.sub.9, s.sub.10) The A matrix has ten columns on the left part of the matrix for the ten components of the variable x as set forth in the equation set (1), and nine columns on the right part of the matrix for the nine components of the variable s as set forth in the equation sets (3) and (4). The coefficients of the first eight rows are the same as the coefficients of the x components as set forth in the first eight lines of equation set (1). The coefficients in the ninth row of the matrix correspond to the coefficients of the ninth line of the equation set (1) such that the coefficients of the first five columns in the ninth row of the matrix are the same as the five x coefficients of the ninth line of the equation set (1), and the coefficient of the first s column of the matrix is the same as the coefficient of the sole s component in the ninth line of the equation set (1). The entries at the right side of the inequality signs in the nine lines of equation set (1) are found in the corresponding nine places of the b vector of FIG. 8. The next eight rows (row 10 through row 17) of the A matrix have coefficients which are the same as the coefficients of the x and the s components set forth in the eight lines of equation set (3). The entries at the right side of the inequality signs in the eight lines of equation set (3) are found in the corresponding eight places of the b vector. In similar fashion, the entries in the last nine rows of the A matrix and the last nine places of the b vector correspond to the entries in the nine lines of equation set (4). Note that the upper left hand corner of A gives the bill of material, that is, if the row i corresponds to material i and the column j corresponds to the production of product j then aij (the entry in the ith row, jth column of A) is usage of material in i product j. The upper portion of the b vector corresponds to the availability of materials, while the lower portion of the b vector corresponds to demands. The constraints (1)-(5) describe the set of all combinations of production and shipments (quantity served) that satisfy the material availability and do not exceed any demand. In order to determine which of the many possible points is "best" one needs to formulate an objective function. In this case we will use total revenue as our objective. Our goal will be to maximize revenue, that is the point (x,s) that among all points satisfying, (1)-(5) maximizes the expression: 2s.sub.1 +3s.sub.2 +3.5s.sub.3 +4s.sub.4 +2.75s.sub.5 +1.50s.sub.7 +2.50s.sub.8 +3.00s.sub.9 +3.50s.sub.10 wherein the coefficients of the s components are the prices of the various food products as set forth in Table 1. We let c denote the vector (2, 3, 3.5, 4, 2.75, 1.5, 2.5, 3, 3.5) wherein the vector components are the set of prices. The problem of determining the revenue maximizing production and shipment schedule then becomes a maximizing of the dot product, namely, ##EQU4## This problem is a linear program, which can be solved by a variety of techniques, such as Dantzig's simplex algorithm or Karmarkar's interior point algorithm. The optimal solution to this particular LP is: ##EQU5## Notice that this solution is feasible with respect to the inventory availability. That is, if we apply standard MRP logic to the shipment vector s, treating it as a demand, no material shortages result. In this particular case, translating the LP solution in to an actual production plan is quite easy. A total of 12 plain omelets are made; 4 are used for cheese omelets, 1 is used for a ham omelet, 2 are used for ham and cheese omelets and 5 are used for vegetable omelets, all of which are served. No plain omelets are served. The cheese sandwich from inventory is served. A total of 10 plain sandwiches are made. These, together with the three plain sandwiches in inventory are used to make 1 cheese sandwich, 3 ham sandwiches, 5 ham and cheese sandwiches, and 4 ham and egg sandwiches, all of which are served. Note that a total of 40 eggs are used (36 in omelets, and 4 in egg and ham sandwiches), 30 ounces of ham are used, 20 slices of bread plus 3 plain sandwiches are used, and 10 green peppers are used. There is no remaining inventory of these items. A total of 10 ounces of mushrooms are used, so 4 ounces remain, 12 teaspoons of butter are used, so 3 teaspoons remain, and 27 ounces of cheese are used, so 3 ounces remain. This combination of omelets and sandwiches can be made from the available inventory; furthermore no additional omelets or sandwiches can be made from the remaining inventory. The value of this allocation of resources is $75. There is no other combination of omelets and sandwiches which can be made from the available inventory and has a value higher than $75. In the foregoing example in the preparation of omelets and sandwiches, constraints were placed on inventory of food materials. The example is now extended to include a bill of resources wherein constraints are present also on availability of equipment used in preparation of the food products. Therefore, in addition to the materials (e.g., food) we now also consider the availability of two resources, skillets and a toaster. The usage requirements for these resources are given by the following chart:
______________________________________
Toaster Skillet
______________________________________
Plain omelet 3 min
Cheese omelet 3 min
Ham omelet 2 min
Ham & Cheese omelet 4 min
Veg. omelet 1 min
Plain sandwich
Cheese sandwich 3 min
Ham sandwich 2 min
Ham & Cheese sandwich
2 min
Ham & Egg sandwich 2 min 5 min
Total Requirements
Toaster 24 min
Skillet 110 min
______________________________________
The total requirements for these resources are computed using logic similar to Bill-of-Material explosion. Note that a cheese omelet requires a total of 6 minutes of skillet time, 3 in the "subassembly" process of making the plain omelet, and 3 in the final assembly process of making the cheese omelet from the cheese and plain omelet. Suppose that we have one toaster, available for 20 minutes, and 6 skillets, each available for 15 minutes. We modify the LP (1)-(5) to include constraints representing the availability of these two resources, as follows. 3x.sub.1 +3x.sub.2 +2x.sub.3 +4x.sub.4 +x.sub.5 +3x.sub.7 +5x.sub.10 .ltoreq.90 2x.sub.8 2x.sub.9 +2x.sub.10 .ltoreq.20 The first inequality in (6) says that the total time for which the skillets are used does not exceed the total time for which the skillets are available (90=6.times.15). The second inequality says that the total time required by the toaster does not exceed the time available on the toaster. Note that the optimal solution to the previous LP with constraints (1)-(5) uses 76 minutes of skillet time and 24 minutes of toaster time, and therefore it is not feasible with respect to the resource availability constraints (6). We can find the optimal solution that satisfies the material availability constraints and the resource availability constraints simultaneously by simply appending the constraints (6) to the A matrix and b vector, and solving the resulting LP. max cx s.t constraints (1) , (2), (3), (4), (5), (6). or, letting A' and b' respectively denote the enlarged A matrix and b vector ##EQU6## The optimal solution to this new, enlarged LP is given by ##EQU7## The value of this solution is $73.25, which is less that the value of the solution to the allocation problem defined by only constraints (1)-(5). EXAMPLE OF A MULTI-PERIOD MODEL Extending the single period model to a multi-period model requires additional decision variables and constraints. These variables and constraints are used to keep track of the inventory (raw materials, subassemblies, and products) and the demand backlog that is carried from one period to the next. For the multi-period model we make the following assumptions. 1. Unmet demand in one period is available to be served in the next period. 2. Unused material in one period is available for use in the next period. 3. Unused capacity (resource) in one period is not available for use in the next period. These assumptions are realistic in many manufacturing companies. As an illustration, we continue the food example, but restrict ourselves to only the sandwiches. We consider 2 time periods, say an early lunch period and late lunch period, and we assume that a delivery of raw materials arrives between the two lunch periods. We let demand be given by:
______________________________________
Early Lunch
Late Lunch
______________________________________
Plain sandwiches 4 2
Cheese sandwiches 5 6
Ham sandwiches 7 8
Ham & cheese sandwiches
6 9
Ham & egg sandwiches
3 4
______________________________________
We let supply be given by:
______________________________________
Initial Inventory
New Supply
______________________________________
Plain sandwiches
2 0
Cheese sandwiches
1 0
Bread 20 slices 30 slices
Ham 25 oz. 15 oz.
Cheese 30 oz. 20 oz.
Eggs 5 2
______________________________________
We let resource availability (in minutes) be given by:
______________________________________
Early Lunch
Late Lunch
______________________________________
Toaster 40 30
Skillet 15 20
______________________________________
Total Requirements for Raw Ingredients
______________________________________
Early Lunch
Late Lunch
______________________________________
Bread 44 58
Cheese 24 36
Ham 36 46
Egg 3 4
______________________________________
Total Requirements for Resources
______________________________________
Early Lunch
Late Lunch
______________________________________
Toaster 32 42
Skillet 27 38
______________________________________
Net Requirements for Ingredients:
______________________________________
Early Lunch
Late Lunch
______________________________________
Bread 24 28
Cheese -- 10
Ham 11 31
Egg -- --
______________________________________
Net Requirements for Resources:
______________________________________
Early Lunch
Late Lunch
______________________________________
Toaster -- 12
Skillet 12 18
______________________________________
Notice that the extra cheese remaining at the end of the early lunch period (6=30-24) is used in the later lunch period (6+20-30=10), so that the late lunch period net requirement for cheese is only 10, rather than 16. In contrast, the extra time available for the toaster in the early period cannot be used in the late lunch period. The linear programming formulation for the two period model requires some additional decision variables. Let v.sub.6 =number of plain sandwiches held in inventory at the end of the early lunch period. Let v.sub.7 =number of cheese sandwiches held in inventory at the end of the early lunch period Let v.sub.8 =number of ham sandwiches held in inventory at the end of the early lunch period Let v.sub.9 =number of ham and cheese sandwiches held in inventory at the end of the early lunch period Let v.sub.10 =number of ham and egg sandwiches held in inventory at the end of the early lunch period v.sub.11 =number of slices of bread held in inventory at the end of early lunch period v.sub.12 =amount of cheese held in inventory at the end of early lunch period v.sub.13 =amount of ham held in inventory at the end of early lunch period v.sub.14 =amount of eggs held in inventory at the end of early lunch period The model must include production variables x, and service variables s for each of the five products in each of the 2 lunch periods. We let x.sub.6,e (resp. x.sub.6,1) denote the number of plain sandwiches produced in the early (resp. late) lunch periods. Similarly x.sub.7,e and x.sub.7,1 denote the production of cheese sandwiches in the early, late lunch periods; x.sub.8,e and x.sub.8,1 denote the production of ham sandwiches in the early, late lunch period. x.sub.9,e and x.sub.9,1 --ham and cheese sandwiches x.sub.10,e and x.sub.10,1 --ham and egg sandwiches We again use s to denote the number of sandwiches served. The first subscript will denote the part number (sandwich type) and the second will denote the lunch period. For example: S.sub.7,e is the number of cheese sandwiches served in the early lunch period The linear programming model requires material availability constraints for each part number in each time period, and service (shipment) accumulation constraints for each demand and each time period. For the first time period the constraints take the form ##STR2## Notice that in the single period model the resource and material availability constraints were inequalities. In the multi-period model, it is necessary to track the carry-over of inventory from one period to the next. Inventory carried from one period to the next is exactly equal to the amount of material that was available at the beginning of the period, minus what is used during the period. For the second period (late lunch) the material availability and resource availability constraints take the form ##STR3## Notice that in the material balance constants for the second period, the supply remaining at the end of the first period is included as additional material availability. Also, in this case, since there are only two periods, we do not require additional variables to track the inventory available at the end of the late period, and the material availability constraints are inequalities. We also include constraints on the inventory variables that specify that inventory must be non-negative. v.sub.7 .gtoreq.0, v.sub.8 .gtoreq.0, v.sub.9 .gtoreq.0, v.sub.10 .gtoreq.0, v.sub.11 .gtoreq.0, v.sub.12 .gtoreq.0, v.sub.13 .gtoreq.0, v.sub.14 .gtoreq.0 In addition to the material and resource availability constraints, we require demand or backlog accumulation constraints and backlog variables. For each product, we define a backlog variable that represents the amount of demand that was not satisfied in the early period. (Recall the assumption that unit demand in one period can be met in a later period). Let b.sub.6 =backlog of demand for plain sandwiches from early lunch Let b.sub.7 =backlog of demand for cheese sandwiches from early lunch Let b.sub.8 =backlog of demand for ham sandwiches from early lunch Let b.sub.9 =backlog of demand for ham and cheese sandwiches from early lunch Let b.sub.10 =backlog of demand for ham and egg sandwiches from early lunch The constraints (4) in the single period model are replaced by the following set of constraints: s.sub.6,e +b.sub.6 =4 s.sub.7,e +b.sub.7 =5 s.sub.8,e +b.sub.8 =7 s.sub.9,e +b.sub.9 =6 s.sub.10,e +b.sub.10 =3 Thus, for example, b.sub.7 =5-S.sub.7,e, is the number of cheese sandwiches demanded in the early lunch period, minus the number of cheese sandwiches served in the early lunch period, that is, the backlog of cheese sandwiches for the late lunch period. For the late-lunch period we have: s.sub.6,1 -b.sub.6 .ltoreq.2 s.sub.7,1 -b.sub.7 .ltoreq.6 s.sub.8,1 -b.sub.8 .ltoreq.8 s.sub.9,1 -b.sub.9 .ltoreq.9 s.sub.10,1 -b.sub.10 .ltoreq.4 These inequalities say that the number of, for example, cheese sandwiches, served in the late lunch period cannot exceed the sum of the backlog from the early lunch period plus the new demand in the late lunch period. As in the single period example, all of the model variables, x, v, s, b, are required to be non-negative. The objective function is again maximization of revenue. ##EQU8## This problem can be written as ##EQU9## This concept of carrying inventory and backlog from one period into the next period can be extended to models with arbitrarily many periods. The objective function of the linear program can include any additional terms that are linear combinations of the model variables. For example, it can include a term representing the manufacturing cost of each of the products as a multiple of the appropriate production variables x, backlog cost, as multiples of the backlog variables b, holding costs, as multiples of the inventory variables v, etc. For the particular problem presented above, the optimal solution is:
______________________________________
s.sub.e,6 = 0 x.sub.e,6 = 10
s.sub.e,7 = 1 x.sub.e,7 = 0
s.sub.e,8 = 1 x.sub.e,8 = 1
s.sub.e,9 = 1 x.sub.e,9 = 8
s.sub.e,10 = 3
x.sub.e,10 = 3
s.sub.l,6 = 4 x.sub.l,6 = 15
s.sub.l,7 = 0 x.sub.l,7 = 0
s.sub.e,8 = 0 x.sub.l,8 = 0
s.sub.l,9 = 9 x.sub.l,9 = 7
s.sub.l,10 = 4
x.sub.l,10 = 4
______________________________________
LP FORMULATION STEPS 1. Define production variables. Require variable x.sub.jt if j is the part number of a product (has a bill of material and/or a bill of resources) and it is a period of time in which part number j can be completed. 2. Define stock variables. Require v.sub.jt for part number j if excess inventory of p/n j can be carried over from period t to period t+1. 3. Define scrap variables. Require v.sub.j,t for part number j if excess inventory of p/n j can be scrapped at end of period t. 4. Define resource surplus variables. u.sub.r,t for each resource r and each period t. 5. Define shipment variables. s.sub.d,t for each demand d and each period t. 6. Define backlog variables. b.sub.d,t for each demand d and each period t such that ##EQU10## 7. Define inventory balance constraints and right hand side. ##EQU11## for all parts j and all periods t-1. Here ##EQU12## is the total shipment of part number j in period t, to all of the demands d for this part number {d.epsilon.D.vertline.p(d)=j}. The sum ##EQU13## is the total usage of part number j in all of the other part numbers. The coefficients a.sub.jk are obtained from the bill of material data. The quantity v.sub.j,t is the stock of part number j that is to be carried over from the end of period t into period t+1. The quantity v.sub.j,t is the amount of part number j that is to be scrapped at the end of period t. The quantity x.sub.jt is the amount of part number j that completes production in period t and is available for shipment or use in other products. This variable exists only if part number j is a product. The quantity e.sub.jt is the amount of part number j that is made available from external sources (purchase, etc.) during period t. e.sub.j,t is obtained from the supply data or material availability data. And finally, the quantity v.sub.j,t-1 is the quantity of part number j that remained available at the end of period t-1 and was carried over into period t, Step 8: Define the resource availability constraints and right hand side. ##EQU14## The sum ##EQU15## is the total amount of resource r that is used by all of the part numbers in period t. The coefficients g.sub.r,j are obtained from the bill of resource data. The quantity u.sub.r,t iS the amount of resource r that remains unused in period t. The quantity c.sub.r,t is the amount of resource r that is available in period t. It is obtained from the resource availability data. Step 9 Define the backlog constraints and right-hand side b.sub.d,t -b.sub.d,t-1 +s.sub.d,t =q.sub.d,t .A-inverted.d,t b.sub.d,t is the backlog at the end of period t for demand d. b.sub.d,t-1 is the backlog at the end of period t-1 for demand d. q.sub.d,t is the demanded quantity for demand d in period t. It is obtained from the demand data. s.sub.d,t is the shipment for demand d in period t. Step 10 Define the non-negativity constraints for all of the variables. ##EQU16## Step 11 Define the objective function coefficients. ##EQU17## H.sub.j,t is the holding cost, or inventory carrying cost for p/n j in period t. S.sub.j,t is the scrapping cost of p/n j in period t. P.sub.d,t is the backlog penalty for demand d in period t. R.sub.d,t is the shipment revenue for demand d in period t. Q.sub.r,t is the surplus cost of resource r in period t. All of these coefficients are obtained from the cost or revenue data. Step 12 (optional) Define substitution constraints and variables and objective function coefficients. Modify material and resource availability constraints, and objective function. Step 13 (optional) Define alternate BOM and/or BOR variables, constraints and objective function coefficients. Modify material and resource availability constraints. Add linking constraints, if required modify objective function. Step 14 (optional) Define separation variables, modify the material availability and resource availability constraints, and modify the objective function. Utilization of the invention, generally, involves production planning and is concerned with determining production and stock levels to meet fluctuating demand requirements. If resources can be acquired as needed and plant capacity is infinitely expandable and contractible at no cost, then the optimal production schedule consists of producing end products according to the demand schedule, and producing subassemblies (i.e., intermediate products) exactly when needed as input to next assembly process. However, in many real assembly systems, the supply of some raw materials is tightly constrained, with long production and/or procurement lead-times. The demand for products fluctuates, both in total volume and in product mix. As a result, just-in-time production is not usually feasible, and when feasible, may result in poor utilization of resources. This tool provides methods for determining the best utilization of the available resources, given the current forecast of demand requirements. Since both the inventory balance equations and the profit maximization objective function are linear (see formulation below), it is not surprising or new to consider linear programming approaches to resource allocation problems. Several "textbook" formulations have been published. However, the inventory management literature cautions against the use of linear programming for resource planning because of the difficulty of accurately formulating the allocation problem for a multi-level assembly process, because of the size and complexity of the formulation for even simple single level assembly processes, and because of the difficulty of interpreting and implementing the solution of the linear program. Recent improvements in LP software packages and computing hardware have rendered the size considerations less forbidding; it is now possible to solve realistic problems in a reasonable amount of time. For example, on an RS/6000, the LP corresponding to a real production planning problem for 400 part numbers, 500 demands, and 26 weeks, can be solved in under 10 minutes cpu time. This invention addresses the remaining considerations: accurately formulating the allocation problem, and enabling effective use of the results by inventory managers. A basic problem which can be handled by the invention is multi-period resource allocation. Determine the optimal allocation of material and capacity by formulating the allocation problem as a linear program, applying a linear programming software package, such as OSL or MPSX, or the Karmarkar algorithm and converting the LP solution into a production and shipment plan. We assume that the planning horizon has been partitioned into T planning periods of equal length (e.g. weeks). Inputs: Supply data Resource availability (Capacity) information Demand data BOM information (product, p/n, usage quantity, usage period, effectivity dates) BOR information (product, resource, usage quantity, usage period, effectivity dates) Cost Model Assumptions Unused MATERIAL remains available for use in the next period. Unused RESOURCES are not available in later periods. Unfilled demand can be filled later. Notation J=set of part-numbers v.sub.j,0 =initial stock of product j (input #2 in FIG. 10) e.sub.j,t =net external supply of j in period t (input #2 in FIG. 10) a.sub.i,j =quantity of p/n i required per unit p/n j (input #3 in FIG. 10) R=set of resources--input #7 in diagram g.sub.r,j =quantity of resource r required per unit of p/n j (input #4 in FIG. 10) c.sub.r,t =quantity of resource r available in period t (input #5 in FIG. 10) D=set of demands (input #1 in FIG. 10) p(d) .epsilon.J, P/N for demand d.epsilon.D q.sub.d,t =quantity of demand d in period t b.sub.d,0 =initial backlog for demand d This formulation permits multiple demands for each part number. These demands may have different penalties and revenue coefficients associated with them. These penalties and revenues appear in the following summation for the objective function. Decision Variables x.sub.j,t =quantity of p/n j produced in period t (output #9 in FIG. 10) s.sub.d,t =quantity of demand d filled in period t (output #8 in FIG. 10) b.sub.d,t =backlog of demand d at end of period t v.sub.j,t =stock of p/n j at the end of period t v.sub.j,t =quantity of p/n j scrapped at the end of period t u.sub.r,t =quantity of resource j unused at the end of period t ##EQU18## Objective function: Notation: (input #6 in FIG. 10) S.sub.r,t =holding cost per unit of p/n j in period t H.sub.j,t =holding cost per unit of p/n j in period t M.sub.j,t =manufacturing cost per unit of p/n j in period t R.sub.d,t =revenue per unit of demand d shipped in period t P.sub.d,t =penalty per unit backlog of demand d in period t Q.sub.r,t =penalty per unit excess of resource r in period t ##EQU19## Alternately, one can formulate an objective function based on some notion of product or demand serviceability, and an associated penalty for failing to meet serviceability targets. In real assembly processes, it may take several periods to produce a product, and the product may require materials (p/n s) and resources in each of these periods. Such considerations can easily be included in the above formulation by keeping track of the release period of each product, the period when each input material or resource is required, and the completion period. The time indices t in the above constraints are appropriately modified. Let m(j) denote the manufacturing lead time (rounded to an integer number of model periods) of p/n j. That is, if one begins the manufacturing process for a single unit of p/n j in period t, that unit of p/n j will be complete in period t+m(j). Each of the p/n's i in p/n j's bill-of-material, and each of the resources r in p/n j's bill of resources have an associated usage offset f(i,j) and f(r,j) respectively. The usage offset is assumed to be a non-negative integer, and is interpreted as follows: p/n j is completed in period t, then material p/n i is required in period t-f(i,j) and resource r is required in period t-f(r,j). Incorporating these manufacturing lead time and offset considerations into the constraint matrix requires the following modification of the material balance and resource availability constraints. ##EQU20## Note that the subscripts indicating the time index of the x variables have been changed. The variable x.sub.k,t+f(j,k) represents the quantity of p/n k that is completed in period t+f (j,k). According to the definition of the offset f(j,k), each of these x.sub.k,t+f(j,k) units of p/n k require a.sub.j,k units of p/n j in period t+f(j,k)-f(j,k)=t. Thus, ##EQU21## is the total amount of p/n j required for use in other p/ns in period t. Similarly ##EQU22## is the total amount of resource r required for use in all p/ns in period t. Similarly, the inventory balance constraints can be modified to consider the time-sensitive part or resource usage resulting from engineering and/or technology changes. Often bill-of-material and bill-of-resources information includes effectivity date information. That is, a p/n, say i, may be used to build another p/n, said j, only during a specific interval, say periods t.sub.1, t.sub.1 +1 . . . . , t.sub.1 +t.sub.2. In all other manufacturing periods, p/n i is not required for the production of p/n j. This effectivity date information can be used to modify the bill-of-material and bill-of-resource coefficients a.sub.i,j and g.sub.r,j, respectively in the constraint matrix as follows. For each pair i,j with i.epsilon.J, j.epsilon.J we define ##EQU23## The material balance constraint for p/n j becomes ##EQU24## The resource availability constraint for resource r becomes. ##EQU25## Additional manufacturing considerations, such as yield and fallout can easily be incorporated into the inventory balance constraints. We let .alpha..sub.j be the manufacturing yield of p/n j. That is, for each unit of p/n j that is useable for shipment or for use in other products, 1/.alpha..sub.j units of p/n j must be produced. If .alpha..sub.j =1, then every unit of p/n j is useable. If .alpha..sub.j =0.75 then three quarters of the units of p/n j produced are useable. For each pair i,j we define d.sub.i,j to be the "fallout" of p/n i in p/n j, expressed in units per 100. Thus, if .alpha..sub.i,j =95, and d.sub.ij =5 then a total of 100 units of p/m i is required to produce each unit of p/m j. 95 of the units will be present in the completed p/n j, 5 will be lost in the manufacturing process. We define, for all pairs i,j ##EQU26## and modify the material balance constraint to include yield and fallout considerations as follows: ##EQU27## The coefficients a.sub.j,t have been replaced by the scaled coefficients a.sub.j,k, and the amount of p/n j available from production in period t has been scaled by the yield .alpha..sub.j. If desirable, the formulation can be augmented to include minimum and maximum production quantities in each period, maximum backlog per demand and period, and minimum and maximum stock quantities for each p/n in each period. Additional input data is needed to describe the production, stock and shipment bounds. We use the following notation. MAXX.sub.j,t =upper bound on production of p/n j in period t. MINX.sub.j,t =lower bound on production of p/n j in period t. MAXS.sub.j,t =upper bound on stock of p/n j at end of period t. MINS.sub.j,t =lower bound or stock of p/n j at end of period t. MAXB.sub.d,t =upper bound on backlog of demand d in period t. The following set of bounding constraints may be added to the basic formulation in any combination. ##EQU28## SUBSTITUTE PARTS AND RESOURCES Often a product can be built using a part or resource other than the one specified on its BOM or BOR. For example, fast memory modules can be substituted for slow memory modules, but slow modules cannot usually be substituted for fast ones. If substitute part and substitute resource information is given, the resource allocation tool can be used to determine the optimal use of primary and substitution resources. Additional inputs: for each BOM entry, substitute information consisting of the substitute part, usage quantity, effectivity dates, and cost or priority information For each BOR entry, substitute information consisting of the substitute resource, usage quantity, effectivity dates, and cost or priority information. Let S(i,j) be the set of all p/ns f that can substitute for p/n i in p/n j. a.sub.j.sup.if =quantity of p/n i that is required as substitute for a.sub.ij units of p/n i in p/n f Formulation modifications: Additional variables for each prod-part-sub triple. z.sub.j,t.sup.i =quantity of p/n j produced in t in which p/n i is not replaced. y.sub.j,t.sup.i,f =quantity of p/n j produced in t in which p/n i is replaced by p/n f Additional constraints ##EQU29## Balance equation for p/n i is modified to use z.sub.j,t.sup.i instead of x.sub.j,t and y.sub.j,t.sup.i,f term is added to balance equations for f The material balance constraint for p/n j becomes ##EQU30## The sum ##EQU31## is the total usage of p/n j as a prime BOM item in other p/n's for which j has substitutes (that is, j is called for in the BOM of k, j has substitutes and no other p/n is used to substitute for j in k). The sum ##EQU32## is the total usage of j as a substitute for other p/n's in p/n k. Thus ##EQU33## is the total usage of p/n j as a substitute in all other p/n's and the sum ##EQU34## is the total usage of j in all other p/n's. The objective function can be modified to reflect the additional cost or benefit incurred by using substitute f for part i in p/n j by including a non-zero coefficient for the variable y.sub.j,t.sup.i,f Let p.sub.jf.sup.jt =cost of substituting p/n f for p/n i in p/n j in period t. The following terms are added to the objective function ##EQU35## Similar modifications can be used to optimize the allocation of substitute resources. Let R (r,j)=set of resources that can substitute for resource r in p/n j. g.sub.j.sup.r,t =usage of resource f when substituting for resource r in p/n j Defined for .A-inverted. f.epsilon.R(r,j). p.sub.j,t.sup.r,t =cost of substituting resource f for resource r in p/n j in period t defined for all f.epsilon. R (j,t) .A-inverted.t. z.sub.j,t.sup.r =quantity of p/n j produced in period t in which resource r is not replaced. Defined for all j,r s,t R(r,j) is not empty, and .A-inverted.t. y.sub.j,t.sup.r,f =quantity of p/n j produced in period t in which resource r is replaced by resource f. Defined for all f .epsilon. R(r,j), .A-inverted.t. The model requires additional constraints of the form ##EQU36## Resource availability constraints are modified as follows: ##EQU37## The following terms are added to the objective function: ##EQU38## The output of this model gives not only the shipment and production schedules, but also the substitution usage data. ALTERNATE BOMS In addition to substitute parts, a simple extension of the resource allocation model allows for consideration of the possibility of building a part according to more than one bill-of-material or bill-of-resources. For example, certain types of memory modules can be built using one "all good" chip and a corresponding substrate, or using two "half-good" chips, and their corresponding substrate. The resource allocation tool can be used to determine how many of each product should be built in each time period using each possible BOM and/or BOR. Additional inputs: For each product, list or BOMs and BORs the model modification is similar to that for substitution. The following additional input data and notation is required for modeling the optimal allocation of resources in the presence of alternate bill-of-materials. K=set of all bills-of-materials. p.sup.(k).epsilon.J =p/n produced by BOM k.epsilon. K. a.sub.i,k =usage of p/n i .epsilon. J in BOM k.epsilon. K. M.sub.k,t =manufacturing cost per unit of p.sup.(k) using BOM k in period t. We introduce the following decision variables: x.sub.k,t =production (of p/n p.sup.(k)) using BOM k .epsilon. K in period t. In particular, we allow for the case where there are two (or more) distinct BOM, say k and k' that produce the same p/n, j=p.sup.(k) =p.sup.(k'). For example, It is common practice in computer manufacturing to produce memory modules using either one full-good memory chip and the appropriate packaging material, or using two half-good memory chips, some connecting components, and the appropriate packaging material. The material balance constraints for p/n j become ##EQU39## The resource availability constraints are replaced by ##EQU40## The sum ##EQU41## is the total production of p/n in period t from all BOMs k.epsilon. K that produce p/n j. The sum ##EQU42## is the total usage of p/n j in time period t in all BOMs. The term ##EQU43## in the original objective function is replaced by the term ##EQU44## Note that the p/n production variables x.sub.j,t for j.epsilon. J have been replaced by the BOM production variables x.sub.k,t for k .epsilon. K. A similar approach can be used to allocate material and resources in the presence of the multiple bills-of-resources. We introduce the following additional data and notation: L=set of all bills-of-materials p(l).epsilon.J=p/n produced by BOR l .epsilon. L g.sub.r,l =usage of resource r .epsilon. R in BOR l .epsilon. L M.sub.l,t =manufacturing cost per unit of p(l) using BOR l in period t. We introduce the following decision variables: x.sub.l,t =production (of p/n p(l)) using BOR l .epsilon. L in period t. Note that we allow for the case where there are two (or more) distinct BORs, say l and l' that produce the same p/n, j=p(l)=p(l'). The material balance constraints for p/n j becomes ##EQU45## The resource availability constraint for resource r .epsilon. R becomes ##EQU46## The sum ##EQU47## is the total production of p/n j in period t from all BORs l .epsilon. L that produce p/n j. The term ##EQU48## in the original objective function is replaced by the term ##EQU49## Note that the p/n production variables x.sub.j,t for j .epsilon. J have been replaced by the BOR production variables x.sub.l,t for l .epsilon. L. A model that includes both alternate BOMs and alternate BORs can also be formulated using the notation introduced above. The material balance constraint for p/n j is given by ##EQU50## The resource availability constraint for resource r is given by ##EQU51## The following additional linking constraint is added: ##EQU52## The term ##EQU53## in the original objective function is replaced by the term ##EQU54## MULTIPLE p/n FABRICATION PROCESSES This extension demonstrates how linear programming can be used to solve a complex material planning that cannot be addressed by standard MRP methodology. In the S/C (semiconductor) fabrication process, basic circuitry is built on a polished silicon wafer to produce a "master slice wafer". Typically, only a small number of different master slices are required by a technology. Each master slice has a single p/n. Then, in the "personalization" process, additional circuitry is built on a master slice, and the completed wafer is cut into individual chips. The completed personalized wafer has a p/n, and a BOM consisting of one master slice wafer; each chip (device) has a p/n. Until recently, each wafer contained only a single type of chip having a common part number, that is, all of the chips on the wafer were identical. In this case, the BOM of a chip consists of the p/n of the personalized wafer that contains the chip, and the usage factor is l/n where n is the number of chips per wafer. To determine the number of wafers to produce, one determined the number of chips required, and divided this quantity by the expected number of good chips per wafer. Now, however, the trend is to increase the number of different chip p/n s on a wafer, and to permit a single chip p/n to be made on a number of different wafers. In this case the notion of "bill-of-material" for a chip is not well defined. Since the chip may be produced from more than one personalized wafer, there is no straightforward way to determine wafer production quantities from chip requirements. In fact, there are typically many different wafer production schedules that could be used to obtain the required chip quantities. Some combinations may produce large excesses of one or more chip types. For example consider the following data: 3 chip types A, B, and C which were described above in reference to FIGS. 2, 3 and 4 Consider two products: P1, consisting of 3 chips of type A and 2 chips of type B; P2, consisting of 1 chip of type A and 3 of type C; and 3 wafer types: AXB consisting of 50 chips of A and 50 chips of B; AXC consisting of 70 chips of A and 30 chips of C; ABC consisting of 20 chips of A, 30 chips of B and 50 chips of C which were also described above in reference to FIGS. 2-5. Further, suppose that the demand is for 25 units of P1 and 25 units of P2. Simple explosion through the BOMs of P1 and P2 converts this to a demand for 100 chips of A, 50 chips of B, and 75 chips of C. However, there is no corresponding "explosion" process for determining the required quantities of wafers. Each of the following combinations of wafer releases meets the chip demand:
______________________________________
COST
______________________________________
5 ABC (excess: 100 B, 175 C)
$7,500
2 AXB, 2 ABC (excess: 40 A, 110 B, 25 C)
$5,200
2 ABC, 1 AXC (excess: 10 B, 55 C)
$4,300
1 AXB, 3 AXC (excess 160 A, 15 C)
$5,000
______________________________________
In general, the number of possible combinations of releases for any specified demand set grows rapidly as the number of chip types, number of wafers, or number of wafers per chip increases. Excess chip inventory costs, and/or wafer product cost data can be used to select among identified wafer release combinations. Alternatively, we can formulate a linear (integer) program which will identify the optimal release combination. The formulation can be expanded to take into account existing inventory of product, chips, and wafers and other resource constraints. This formulation requires the introduction of some additional terminology and notation. We refer to the processes of separating a unit of one p/n (e.g. personalized wafer) into units of one or more different p/n (e.g., chips) as a separation process. Like assembly processes, a separation process can have a bill of resources. Instead of having a bill of material, a separation process has a bill of products (BOP), which lists the p/n s and their respective quantities that result from the separation process. The BOP is associated with the input part. Additional Inputs Bill of Products for each separation process. Bill of Resources for separation processes. (optional) Cost data associated with each separation process Additional Notation N.sub.j,l =quantity of p/n j produced from one unit of p/n l. M.sub.j,t.sup.t =manufacturing cost of separating one unit of part j in period t g'.sub.r,j =amount of resource r required to separate one unit of p/n j. Additional Variable w.sub.j,t =quantity of p/n j separated in period t. Model--Assuming Instantaneous Assembly and Separation ##EQU55## (backlog accounting) ##EQU56## Note: we require that x.sub.j,t =0 unless j has a BOM, and require that w.sub.j,t =0 unless j has a BOP. This invention provides for material planning and resource allocation in a complex manufacturing system. In particular, this invention extends the usual notion of material requirements planning to include separation processes. This invention permits consideration of substitute parts and resources, and alternate Bill-of-Materials and Bill of resources. This invention provides methods for constrained an capacitated material planning and resource allocation. Steps in Constrained Material Requirements Planning with reference to FIGS. 9 and 10. 1. Extract data (Demand, inventory, Bill-of Materials, Bill-of-Resources, Resonance availability cost and revenue data) from site information systems. Source of each data element will be determined by the particular configuration of information systems. In the diagram, the demand data, bill-of-material data, and inventory data are extracted from the Material Requirements Planning System, the bill-of resource data and the resource availability data are extracted from the Capacity Requirements Planning system, and the cost and revenue data is extracted from a third manufacturing information system. 2. Use the Optimal Resource Allocation procedure to determine an optimal shipment schedule and the corresponding production schedule and part usage schedule. 3. Insert shipment schedule, production schedule and past usage schedule into site information systems. Again, the destination of each of these data elements depends on the configuration of the information systems. In the diagram, all three data elements are inserted in the Material Requirements Planning system for further processing. In addition, the production schedule is read into the Capacity Requirements Planning System for further processing, and all the data elements are returned to the third manufacturing information system. Producing the part usage schedule is optional. 1. Demand data: can include backlogged orders, accepted orders, planned orders, and forecasted orders. 2. Inventory data: can include on-hand inventory, supplier orders, planned supplier orders, contractual limits. 3. Bill of materials: Can include alternate bill-of-materials for a part. Can include substitution parts for a product-component pair. Includes effectivity dates, usage rate, fallout, usage offset. 4. Bill of Resources: Can include alternate bill-of-resources for a part, can include substitution resources for a product-resource pair. Includes effectivity dates, usage rate, fallout, and usage offset. 5. Resource availability data: Can include manpower availability, planned downtime, expected downtime. 6. Cost data/Resource data: Includes shipment value, late penalty, holding costs, scrapping costs, manufacturing costs, substitution costs.
______________________________________
Read input data Step 7.1
Process input data and load data
Step 7.2
structures
Build LP model Step 7.3
Define model variables x,s
Step 7.3a
Define model constraints Step 7.3b
Fill constraint matrix A Step 7.3c
Fill right-hand-side vector b
Step 7.3d
Fill objective function c
Step 7.3e
Invoke LP solver Step 7.4
Extract optimal values of the
Step 7.5
variables x,s from the LP solver
Process the optimal values of x,s
Step 7.6
to determine
optimal shipment schedule
Step 7.6a
optimal shipment schedule
Step 7.6b
part usage schedule Step 7.6c
______________________________________
Optimal Resource Allocation Procedure The cost and revenue data is used to compute the coefficients of the objective function. The bill of material data and bill of resource data are used to construct a portion of the constraint matrix. The demand data, inventory data, and resource availability data are used in the construction of the right-hand-side of the constraints. Examples in the practice of the method: 1. A method for material constrained production planning whereby a feasible allocation of material to demand (shipment schedule per demand and period, production schedule per product and period) that maximize profit is determined. Specifically, in Step 1, demand data, bill-of-material data, inventory data, and cost and revenue data are extracted from an MRP system or from an other manufacturing information system. In Step 2, the Optimal Resource Allocation Procedure processes this data, formulates the Linear Program, invokes an LP solver, extracts the optimal values of the LP variables, translates these values in to a shipment schedule and a production schedule. Then, in Step 3, the shipment schedule and the production schedule are inserted into the MRP system or other manufacturing information system. 2. A method for capacity constrained production planning whereby a feasible allocation of capacity to demand (shipment schedule per demand and period, production schedule per product and period) that maximizes profit is determined. Specifically, in Step 1, demand data, bill-of-resource data, resource availability data, and cost and revenue data are extracted from a CRP system, or from an other manufacturing information system. In Step 2, the Optimal Resource Allocation Procedure processes this data, formulates the Linear Program, invokes an LP solver, extracts the optimal value of the LP variables, translates these values in to a shipment schedule and a production schedule. Then in Step 3, the shipment schedule and the production schedule are inserted into the CRP system or the other manufacturing information system. 3. A method for material and capacity constrained production planning whereby a feasible allocation of material and capacity to demand (shipment schedule per demand and period, production schedule per product and period) which maximizes profit is determined. Specifically, in Step 1, demand data, bill-of-material data, and inventory data are extracted from an MRP system or other manufacturing information system, fill-of-resource data and resource availability data are extracted from a CRP system or other manufacturing information system, and cost and revenue data is extracted from the MRP system, the CRP system, or some other manufacturing information system. In Step 2, the Optimal Resource Allocation Procedure processes this data, formulates the Linear Program, invokes an LP solver, extracts the optimal values of the LP variables, translates these values in to a shipment schedule and a production schedule. Then, in Step 3, the shipment schedule and the production schedule are inserted into the MRP system, the CRP system or the other manufacturing information system. 4. A method for capacity constrained Material Requirements Planning where by capacity is allocated to demands to maximize profit, and the resulting production plan (shipment schedule per demand and period, production schedule per product and period), is then analyzed to determine the material requirements. Specifically, in Step 1, demand data, bill-of-resource data, resource availability data, and cost and revenue data are extracted from an MRP system, a CRP system, or from an other manufacturing information system. In Step 2, the Optimal Resource Allocation Procedure processes this data, formulates the Linear Program, invokes an LP solver, extracts the optimal values of the LP variables, translates these values in to a shipment schedule and a production schedule. Then, in Step 3, the shipment schedule and the production schedule. Then, in Step 3, the shipment schedule and the production schedule are inserted into the MRP system, and standard MRP logic is used to determine the material requirements of the shipment and production schedule. 5. A method for critical components constrained Material Requirements Planning where by a specified set of critical raw materials(for example, components with long lead times, or limited availability) are allocated to demands so as to maximize profit, and the resulting production plan (shipment schedule per demand and period, production schedule per production and period) is then analyzed to determine the requirements of all materials not in the specified set. Specifically, in Step 1, demand data, bill-of-material data, inventory data, and cost and revenue data are extracted from an MRP system. In a subsequent step (Step 1a) the bill-of-material data is processed to eliminate from each bill-of materials all raw material part numbers which are not in the pre-specified set of critical parts, and all product part numbers which do not use, either directly or on subassemblies, raw materials in the pre-specified set of critical parts. A resulting "stripped" bill-of materials may have no component parts. Inventory data for raw material part numbers which are not on the pre-specified critical parts list and have demand are replaced by the total demand for that part number in each time period. In Step 2, the Optimal Resource Allocation Procedure processes the reduced set of data produced by Step 1a and formulates the Linear Program corresponding to the reduced set of data. A product which has no component parts on its bill-of-materials results in production variables which are unconstrained, that s, they can take arbitrarily large values. The shipment variables corresponding to these products will exactly equal demand. Step 2 then invokes an LP solver, extracts the optimal values of the LP variables, translates these values in to a shipment schedule and a production schedule. Then, in Step 3, the shipment schedule and the production schedule are inserted into the MRP system. The MRP then uses the original set of bill-of-materials data, the shipment schedule, and the production schedule to determine the requirements of all of the part numbers. In an alternate implementation of this method, the bill-of-material pre-processing (Step 1a) is omitted. Subsequent to Step 1 in Step 1b the inventory data for every raw-material not on the per-specified critical component list, the inventory data is replaced by the vector (M,M,M, . . . ,M) where M is some very large quantity (e.g., expected total annual part usage). This results in that part usage constraints for these parts having extremely large right-hand-sides. In effect, the constraint has been omitted from the formulation. Decision variables that appear only in these constraints become unconstrained. 6. A method for material and capacity constrained Material Requirements Planning where by raw materials (on hand, on order, and projected availability) and capacity are allocated to demands to maximize profit, and the resulting production plan (shipment schedule per demand and period, production schedule per product and period), is then analyzed to determine the requirements of all materials. Specifically, in Step 1, demand data, bill-of-material data, and inventory data are extracted from an MRP system or other manufacturing information system, bill-of-resource data and resource availability data are extracted from a CRP system or other manufacturing information system, and cost and revenue data is extracted from the MRP system, the CRP system, or some other manufacturing information system. The inventory data is extracted as follows: the inventory of part number i in period to is given by (1) the on hand stock of i for period t=1, (2) the amount of i already ordered and scheduled to arrive in period t for 1<t<leadtime(i) (3) an upper bound on the possible availability or usage of i for t>leadtime (i) In Step 2, the Optimal Resource Allocation procedure processes this data, formulates the Linear Program, invokes an LP solver, extracts the optimal values of the LP variables, translates these values in to a shipment schedule a production schedule, and a material usage schedule. Then, in Step 3, the shipment schedule the schedule, and a material usage schedule are inserted into the MRP system, the CRP system or the other manufacturing information system. If available the MRP system is used to further analyze and report on the usage of materials, particularly on the usage of material beyond its leadtime. Then, either the material usage schedule together with the on-hand and on-order inventory data, or the results of the further MRP analysis, are used to generate new orders for each part number (outside of its leadtime). 7. A method for Earliest Ship Date Quoting in which a set of previously accepted order, a specified new order, material information, and capacity availability information are analyzed to determine the earliest possible shipment date for the specified new order this method first allocates materials and capacity to the previously accepted orders so as to meet the quoted shipment dates, then allocates the remaining material and capacity to the specified new order so as to ship it as early as possible. Specifically, in Step 1, demand data, bill-of-material data, and inventory data are extracted from an MRP system or other manufacturing information, bill-of-resource data and resource availability data are extracted from a CRP system or other manufacturing information system, and cost and revenue data is extracted from the MRP system, the CRP system, or some other manufacturing information system. The demand data includes previously accepted orders, the specified new order, and a forecast of future orders. Each order is classified according to its type. The due date for the new order is set to the current date, and it is given a high revenue value-higher than the total value of the forecasted orders. In Step 2, the Optimal Resource Allocation Procedure processes this data and formulates the Linear Program. This LP includes shipment bounds, reflecting the fact that the previously committed orders must be shipped on their respective due dates. Then the LP solver is invoked, and the optimal values of the LP variables are extracted and translated in to a shipment schedule and a production schedule. The date at which the new order ships is the earliest possible date at which this order can be shipped. This date is reported to the user, or returned to the MRP system or other manufacturing information system. 8. A method for New Order Assessment in which a set of previously accepted orders, information on shipment revenue and late delivery penalties associated with these orders, a specified new order, shipment revenue associated with shipping this order in each time period, material availability information, and capacity availability information are analyzed to determine whether it is profitable for the manufacturing company to accept the specified order, the most profitable ship date for the order, and the impact on the ship dates of previously accepted orders. This method allocates material and capacity to the set of previously accepted orders and the specified new order in a manner that optimizes the total profit. The resulting shipment schedule is reviewed to determine (1) whether the specified new order is ship, (2) the shipment date of the specified new order, and (3) the shipment dates of the previously accepted orders. Specifically, in Step 1, demand data, bill-of-material data, and inventory data are extracted from an MRP system or other manufacturing information system, bill-of-resource data and resource availability data are extracted from a CRP system or other manufacturing information system, and cost and revenue data is extracted from the MRP system, the CRP system, or some other manufacturing information system. The demand data includes previously accepted orders, the specified new order, and a forecast of future orders. Each order is classified according to its type. Revenue data for forecasted orders is scaled by the probability of the order materializing. The due date for the new order is set to the current date. In Step 2, the Optimal Resource Allocation procedure processes this data and formulates the Linear Program. This LP includes shipment bounds, reflecting the fact that the previously committed orders must be shipped on their respective due dates. Then the LP solver is invoked, and the optimal values of the LP variables are extracted and translated in to a shipment schedule and a production schedule. If the new order does not appear on the shipment schedule, then it is not profitable to make the order and it should be rejected, or the customer's price should be increased so that the order becomes profitable. If the new order does appear on the shipment schedule, then the date at which the new order ships is the most profitable date at which this order can be shipped. If earlier shipment is desired, the customer price can be increased. The shipment status of the new order, and, if appropriate, the shipment date date are reported to the user, or returned to the MRP system or other manufacturing information system. 9. A method for short term production scheduling in which daily capacity and daily material availability are allocated to products and demands to determine a daily release schedule and daily usage of capacity. Specifically, the method described in Ex. 3 is used, with time periods set to a day or a shift, rather than than the usual planning period duration of a week or a month. 10. A Method for Optimal Capacity and/or Manpower Allocation, in which material and capacity and/or manpower are allocated to products and demands so as to minimize the cost of unused capacity and manpower. Specifically, the method described in Ex. 2 is used, with the scrapping cost of capacity and manpower set equal to the actual value of the respective resource, and all other cost and revenue data eliminated. 11. A method for capacity and material constrained production planning using substitute parts in which capacity and material (including substitute parts) are allocated to products and demands so as to maximize profit. The resulting production plan specifies the usage of substitute parts. Specifically, the method described in Ex. 3 is used, with the bill-of-material data including information about the use of substitute parts and substitute resources. Step 3 also produces a material usage schedule and a capacity usage schedule which explicitly shows the usage of substitute parts and substitute capacity. 12. A method for determining | ||||||