Apparatus and method for production planning

Apparatus and method for production planning in a manufacturing facility is provided. The apparatus and method generates a plurality of theoretical plans and a constraint-based model for receiving one of the theoretical production plans, and applying at least one constraint thereto. Further, a cost function is computed for the theoretical production plans. Then, the apparatus and method searches for a feasible production plan among the plurality of theoretical plans, where the feasible plan is the plan which does not violate the applied constraint and has the least computed cost function.

TECHNICAL FIELD OF THE INVENTION 
This invention relates in general to the field of scheduling systems. More 
particularly, the present invention relates to apparatus and a method for 
production planning. 
BACKGROUND OF THE INVENTION 
Production planning is the process of choosing work to be started in a 
manufacturing facility during some future time period so that performance 
is maximized. Work is usually selected from a variety of product types 
which may require different resources and serve different customers. 
Therefore, the selection must optimize customer-independent performance 
measures such as cycle time and customer-dependent performance measures 
such as on-time delivery. 
The reasons for requiring advanced production planning may be unique to 
each manufacturing facility. For example, one facility may require 
advanced planning so that materials may be ordered and delivered in time 
for manufacture. Another facility may require advanced planning in order 
to make delivery commitments or predict delays in product delivery. 
In order to configure a production plan which yields the best performance, 
the capacity, or the amount of work the facility can handle, must be 
modeled in some fashion, since starting work above the capacity of the 
facility compromises performance and brings forth no benefits. 
Conventional factory capacity models employ simple steady-state linear 
relations that include: (1) the average amount of available work time for 
each machine in the factory and (2) the amount of work each product 
requires of each machine. From the above linear relations, a given start 
plan is within capacity if, for each machine, the total required amount of 
work is: (1) less than the machine's available time, and (2) multiplied by 
a predetermined fraction goal utilization of the start rate. 
There are several problems associated with a linear production planning 
program. Because of the large problem size, variables in linear programs 
must be expressed in non-integer quantities in order to yield good 
solutions. As a result, fractional start quantities may be generated which 
must be converted into discrete start quantities. Such forced conversion 
sacrifices the goodness of the solution. 
Additionally, non-linear relationships cannot be modeled in a linear 
program. Examples of such relationships are the expected yield for a 
product's start quantity, and the cost of surplus and delinquency. Such 
non-linear relationships have been traditionally coerced into linear 
expressions with loss of precision. 
The large problem size presents another obstacle for linear production 
planning programs. Even if a planning problem can be expressed in a linear 
program, the problem size may prohibit efficient solution via conventional 
linear programming techniques. This problem has not been overcome in the 
industry without substantial loss of optimality in the solution. 
Therefore, a need has arisen for apparatus and method to formulate a 
production plan for a manufacturing facility that accommodates integer 
variables, allows non-linear expressions and provides a near optimal 
production plan despite the large problem size. 
SUMMARY OF THE INVENTION 
In accordance with the present invention, apparatus and method for 
production planning are provided which substantially eliminate or reduce 
disadvantages and problems associated with prior production planners. 
In one aspect of the present invention, apparatus for production planning 
in a manufacturing facility is provided. The apparatus comprises means for 
generating a plurality of theoretical plans and a constraint-based model 
for evaluating one of the theoretical production plans, and applying at 
least one constraint thereto. Further, a cost function is computed for 
each of the theoretical production plans. Means is then provided for 
searching for a feasible production plan among the plurality of 
theoretical plans that does not violate any of the applied constraints and 
has the least computed cost function value. 
In another aspect of the present invention, apparatus for production 
planning in a manufacturing facility is provided. The apparatus comprises 
means for computing (e.g. computer) the capacity of the factory in order 
to produce the determined quantities and types of product, means for 
computing the maximum factory capacity, and means for comparing the 
computed production capacity with the maximum factory capacity. Further 
included are means for computing the cost of producing the determined 
quantities and types of product in response to the computed production 
capacity being less than or equal to the maximum factory capacity and 
means for selecting a production plan that has the least computed cost 
function value. 
In yet another aspect of the present invention, a method for generating a 
production plan for a manufacturing facility is provided, which comprises 
the steps of initializing the production plan, and generating a plurality 
of proposals to modify the production plan. At least one constraint is 
formulated and applied to the production plan as modified by each of the 
plurality of proposals. Any proposal which causes the production plan to 
contradict the constraints is then discarded, after which the cost of 
implementing the production plan as modified by each of the remaining 
proposals is computed. A proposal which causes the production plan to have 
the least computed cost is selected and the above steps are repeated until 
no proposals remain after the discarding step. The current production plan 
is then offered as the solution production plan. 
An important technical advantage of the present invention provides a 
formulation of production planning as a cost minimization problem using 
constraint-based models. 
Another important technical advantage of the present invention provides a 
production planner which employs a heuristic search algorithm which 
iteratively manipulates a starting plan to reduce the plan cost until no 
further manipulation improves the plan. 
Yet another important technical advantage of the present invention provides 
a more accurate production planner which accommodates real variables and 
linear equalities as well as integer variables and non-linear equalities.

DETAILED DESCRIPTION OF THE INVENTION 
With reference to the drawings, FIG. 1 illustrates some of the input and 
output parameters of a preferred embodiment of the apparatus and method 
for production planning for a manufacturing facility, indicated generally 
at 10 and constructed according to the teaching of the present invention. 
In order to formulate a production plan 12, production planner 10 takes 
into consideration inputs such as customer demand 14. Customer demand 14 
may specify the quantity and type of products ordered by the customer, and 
the delivery date of the order. Customer demands 14 may also be 
prioritized in the order of importance. The output or end product of the 
manufacturing facility, when produced in accordance with production plan 
12, should preferably meet customer demand 14 and yet not result in an 
over abundance in inventory. Similarly, there is also penalty when 
customer demand 14 is not met by the production plan 12. Therefore, 
associated with each production plan 12 is a plan cost 16, which 
represents the cost of implementing the plan. 
Another set of inputs 18 describes the constraints placed on production 
planner 10 from facility related parameters, such as machine capacity, 
down time, etc. Therefore, the production volume is checked by facility 
constraints 18. Additional constraints 20 arising from the operation of 
the facility, such as yield, surplus and work-in-process, also regulate 
the production quantity and type of product that should be started. 
Referring to FIG. 2, a flowchart 30 of a heuristic search algorithm of the 
preferred embodiment of the present invention 10 (e.g. for a general 
purpose computer) is shown. The present invention employs the heuristic 
search algorithm to search for a suitable plan which specifies the product 
type and quantity to be started at the beginning of the next planning 
period without incurring high cost or violating any facility or 
operational constraints 18 and 20. The search algorithm starts by setting 
the quantities for all product types to zero. For a semiconductor wafer 
fabrication facility, this equates to setting the number of lots to be 
started to zero for all device types. This results in the worst and 
highest cost plan, since by producing nothing, none of the customer 
demands will be met. 
From the initial zero plan, a set of operators which proposes changes to 
the plan is generated, as shown in block 34. The operators may propose to 
modify the plan in two ways. They may increase the number of lots to be 
started by one for a particular device type, or they may set the number of 
lots to a determinable number, so that critical customer orders for each 
device are covered. All operators reachable from the current plan in the 
above-identified ways are generated and examined to determine their 
feasibility. Those operators which generate plans that contradict facility 
or operational constraints are eliminated from the search, as shown in 
block 36. 
If there are remaining operators, as determined in decision block 38, then 
a plan cost is computed for each remaining proposed plan. Of the remaining 
operators, the one which yields the most decrease in computed plan cost 
per addition to work is selected, as shown in block 44. The change in work 
may be defined as the change in the amount of utilization of the current 
top bottleneck machine in the current plan and may be computed by machine 
usage information 63. The selected operator is then applied to the current 
plan, as shown in block 46, to yield a new current plan. Execution then 
returns to block 34 where another set of operators are generated from the 
new current plan. The loop, including blocks 34 to 46, is repeated until, 
at block 38, no operator remains which does not contradict any 
constraints. The plan from which the last set of operators is generated is 
the solution production plan that will yield low plan cost, adds the least 
amount of work, and yet does not contradict any constraints. 
One may recognize the above-described search algorithm as a beam search of 
width one, where each feasible plan constitutes a parent node in the 
search tree, and the operators are the children nodes of each parent node. 
The beam search algorithm of width one is used in the preferred embodiment 
of the present invention because it keeps the number of nodes searched to 
a manageable quantity in a potentially sizeable search tree. 
With reference to FIG. 3, the details of those factors which contribute to 
the computation of plan cost, and facility and operational constraints are 
shown. For ease of illustration, a fictional semiconductor wafer 
fabrication facility which makes only three types of devices and has only 
four machines will be used as an example. Referring back to block 34 in 
FIG. 2, a set of operators is generated which proposes to modify a current 
plan in some fashion. The modifications proposed typically present a new 
mix of product types and/or quantities. Therefore, a production plan 50 
may constitute variables 51-53, which represent the number of lots to be 
started for each type of device. 
In block 36 of the search algorithm shown in FIG. 2, the generated 
operators must be examined to determine whether they violate constraints 
imposed on variables 51-53. One is the constraint which stems from 
facility capacity. 
Each of variables 51-53, which represent the number of lots to be started 
for each device, is operated upon by machine usage constraints 55, which 
are derived from a capacity model 56 of each machine in the facility. Such 
machine capacity modeling is known in the art. The result is the amount of 
usage by each device type on each piece of machinery 57. Note that since 
there are four machines, there are four such variables 58-61. The amount 
of usage per machine, per device, contributes partially to capacity 
feasibility constraints 62. Therefore, 
EQU PLAN.sub.-- USAGE(MACHINE)=.SIGMA.LOT.sub.-- USAGE(MACHINE,PRODUCT) * 
STARTS(PRODUCT) 
computes for the amount of usage required on each machine for the plan, 
where LOT.sub.-- USAGE(MACHINE,PRODUCT) represents the amount of usage 
required by each lot of each device on each machine, and STARTS(PRODUCT) 
represents the number of lots to be started for each product. 
The maximum usage possible for each machine 63, which is computed from a 
combination of factors such as machine availability due to down time and 
setup time 64, work-in-process 65, and the number of hours of operation 66 
is used to compute the following: 
EQU PLAN.sub.-- USAGE(MACHINE).ltoreq.MAX.sub.-- FACTORY.sub.-- UTILIZATION * 
MAX.sub.-- USAGE(MACHINE), 
where MAX.sub.-- FACTORY.sub.-- UTILIZATION specifies the goal factory 
utilization, and MAX.sub.-- USAGE(MACHINE) is the maximum usage per 
machine 63. Therefore, a plan is feasible with respect to (MAX.sub.-- 
FACTORY.sub.-- UTILIZATION * MAX.sub.-- USAGE(MACHINE)) if STARTS(PRODUCT) 
values are such that, for every machine, PLAN.sub.-- USAGE(MACHINE) 
utilizes the machines no greater than the goal. The capacity constraints 
62 further assure that if a machine becomes a bottleneck in the production 
process, it is used no more than the factory utilization goal. Typically, 
the factory utilization goal is set by facility personnel. 
The number of lots per device type is further regulated by expected surplus 
constraints 68, which compute the expected surplus per device 69 for the 
three device types 70-72. This relationship may be expressed in the 
following fashion: 
##EQU1## 
EXPECTED.sub.-- SURPLUS(PRODUCT) is the expected surplus for each product; 
AVG.sub.-- OUTPUT(STARTS(PRODUCT)) equals to STARTS(PRODUCT) * AVG.sub.-- 
YIELD(PRODUCT); TOTAL.sub.-- DEMAND(PRODUCT) is the amount of all known 
demands for each product, including non-startable demands; and MAX.sub.-- 
SURPLUS.sub.-- DEMAND.sub.-- RATIO is an input parameter predetermined by 
facility personnel. 
From the foregoing, it may be seen that surplus feasibility constraint 73 
states that if the lot-start number is positive for a product, surplus is 
acceptable if the ratio of expected surplus to total demand (computed from 
customer demand 74) does not exceed MAX.sub.-- SURPLUS.sub.-- 
DEMAND.sub.-- RATIO. 
A facility may choose to accommodate partial lots which contain a fewer 
number of wafers than a full lot. Partial lots are useful to meet small 
customer demands, but tend to utilize certain machines poorly, such as 
batch machines like ovens. Therefore, in order to ensure good facility 
utilization, a partial lot feasibility constraint 75 is applied to the 
number of starting lots 50. From the number of starting lots for each 
product 51-53, the number of partial lots 76 and full lots 77 are computed 
by partial lot count and full lot count constraints 78 and 79, 
respectively. Partial lot feasibility constraint 75 may be expressed by 
the following: 
##EQU2## 
where MAX.sub.-- T.sub.-- LOT.sub.-- RATIO is an input parameter 
determined by facility personnel. 
Returning to block 36 in FIG. 2, it may be seen that the above-described 
capacity, surplus feasibility, and partial lot feasibility constraints are 
applied to the plan modification proposed by each operator, and those 
operators which contradict the constraints are removed from the search. It 
is important to note that although specific constraints are shown herein, 
they merely serve as examples of how constraints may be used in the 
present invention to compute a production plan. Therefore, other 
constraints known in the art may be applicable to the present invention 
and are within the scope thereof. 
In block 42, those remaining operators are applied to the current plan to 
compute the cost of the modified plan. This computation is shown in FIG. 
3. The number of lots to be started for each product type 51-53 are 
subject to a yield constraint to compute an expected yield 81 for each 
device type 82-84. In the preferred embodiment of the present invention, 
yield constraint 80 may be expressed by the following statistical formula: 
##EQU3## 
The average yield and variance of each product, AVG.sub.-- YIELD(PRODUCT) 
and VARIANCE(PRODUCT), are computed from previous yield values. If 
desired, trend analysis and other methods to achieve better yield 
prediction may also be used. K is an input parameter specifying a measure 
of confidence in the chance that at least YIELD will be produced from 
START for each product type. From the foregoing, it may be recognized that 
higher K or confidence results in production of sufficient quantity to 
more frequently meet customer demand. However, more inventory may be 
produced, since more lots are started per demand. 
Expected yield for each device type 82-84 is subject to demand constraints 
85 and pull-ahead constraints 86 to compute push cost and pull cost per 
device 87 and 88, respectively. Push cost 87 is defined as the cost of not 
covering customer demand and pull cost 88 is defined as the cost of 
producing orders ahead of time. Therefore, demand constraints 85 and 
pull-ahead constraints receive input from customer demand 74. There are 
known formulas for computing the push and pull costs, and will not be 
discussed further herein. 
The push cost per device 89-91 and pull cost per device 92-94 are summed 
independently by summation constraints 95 and 96 to calculate for the 
total push cost 97 and total pull cost 98 of the plan. The total push and 
pull costs 97 and 98 are summed again by a third summation constraint 99 
to yield the total cost 100 of the plan. 
As mentioned above, the total plan cost 100 provides a measure of the 
goodness of the plan. If an operator proposes a plan that costs the least 
and adds the least amount of work among all remaining operators and yields 
no feasible children operators in the search tree, then the plan proposed 
by the operator is the solution plan. 
Although the present invention has been described in the environment of a 
semiconductor wafer fabrication facility, the constraint-based model 
combined with the heuristic search algorithm as taught by the present 
invention is applicable to other production environments. No particular 
form of hardware is required for system operation. The preferred 
embodiment was designed with a general computer in mind, but would work 
equally well with any other computerized apparatus. 
Furthermore, it should be understood that various changes, substitutions 
and alterations can be made hereto without departing from the spirit and 
scope of the present invention as defined by the appended claims.