Method of allocating work in capacity planning
First Claim
1. A computer implemented method providing accurate capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate a workload, said method comprising the steps of:
- inputting data detailing by time period, processing times, tool availabilities and load factors, and a number of passes per product for every operation on every tool group in a manufacturing line;
scanning a list of operations, locating identical operation names within cascade sets of tool groups and organizing the operations and tool groups into the appropriate cascade groups, OperbyGrp and ToolsbyGrp, respectively, as Linear Programming (LP) input data files, the step of organizing tool groups and the operations into the appropriate cascade groups as Linear Programming (LP) input data files including the step of combining processing times and number of times a product visits a particular operation into a derived quantity Up,g,s, called Usage, which represents a required time to process a unit start of product p through all passes of an operation s, on a primary or otherwise preferred tool group contained in tool cascade group g;
calculating from the LP input data files an allocation of workload to parallel, unrelated tool groups in a cascade set, with a preference for an order in which the tool groups are to be used and in which ratios of process times of operations performed on different tool groups varies by operation;
generating output files which report the derived optimum product starts by product and required number of tools by tool group;
multiplying the Usage, Up,g,s, for each operation s by a number of product starts, Wp, for product p;
summing over all Products, P, to obtain a total required time for that operation according to the expression
thus obtaining a total required time referenced to the primary or otherwise preferred tool group in tool cascade group t for all products being processed through operation s;
then allocating the total required time over the tool groups contained in tool cascade group g capable of performing that operation, according to the expression
each tool group having its own fractional allocation decision variable, fg,s,t;
taking into account variable process time ratios, Rg,s,t, on such tool groups to a process time of the primary tool group by introducing an effective available time per day
obtained by dividing actual available time per day, At, by a respective variable process time ratio, Rg,s,t, and further multiplying by a number of tools in the tool group, Nt, to obtain an effective available time per day for an entire tool group;
summing the fractional allocation decision variable fg,s,t for each tool group over all operations contained within the set OperbyGrp[g], that contains all operations associated with the cascade group g, and then summing over all those tool cascade groups, ToolsbyGrp[g], to which that tool group belongs according to the expression in order to obtain a total fractional use decision variable, Ft, for that tool group for use in a linear program (LP) objective function that constrains utilization of that tool group; and
employing penalty functions having very steep slopes above a fractional use (FracUse) of one, said penalty functions being so employed in order to achieve a feasible solution to the Linear Programming (LP) equations when tool groups are forced to be used beyond their capacity for product starts at the minimum of their ranges, said feasible solution providing information on the amount by which tool group capacity is exceeded.
1 Assignment
0 Petitions
Accused Products
Abstract
A computer implemented method provides accurate capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate the workload. The method reliably determines precisely what are the gating tools among sets of parallel, unrelated tools in a complex manufacturing environment in which different tools can perform the same or similar sets of operations, generally at different rates. The primary, secondary, etc. tool groups in each cascade set are explicitly kept track of in order to enable the correct penalty function to be associated, in one implementation with the appropriate tool group, and in another implementation with the tool allocation variables. The end user may also interact with the input data through a Menu Program or through a Graphical User Interface (GUI) and modify the data for “what-if” analyses.
54 Citations
23 Claims
-
1. A computer implemented method providing accurate capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate a workload, said method comprising the steps of:
-
inputting data detailing by time period, processing times, tool availabilities and load factors, and a number of passes per product for every operation on every tool group in a manufacturing line;
scanning a list of operations, locating identical operation names within cascade sets of tool groups and organizing the operations and tool groups into the appropriate cascade groups, OperbyGrp and ToolsbyGrp, respectively, as Linear Programming (LP) input data files, the step of organizing tool groups and the operations into the appropriate cascade groups as Linear Programming (LP) input data files including the step of combining processing times and number of times a product visits a particular operation into a derived quantity Up,g,s, called Usage, which represents a required time to process a unit start of product p through all passes of an operation s, on a primary or otherwise preferred tool group contained in tool cascade group g;
calculating from the LP input data files an allocation of workload to parallel, unrelated tool groups in a cascade set, with a preference for an order in which the tool groups are to be used and in which ratios of process times of operations performed on different tool groups varies by operation;
generating output files which report the derived optimum product starts by product and required number of tools by tool group;
multiplying the Usage, Up,g,s, for each operation s by a number of product starts, Wp, for product p;
summing over all Products, P, to obtain a total required time for that operation according to the expression
thus obtaining a total required time referenced to the primary or otherwise preferred tool group in tool cascade group t for all products being processed through operation s;
then allocating the total required time over the tool groups contained in tool cascade group g capable of performing that operation, according to the expression
each tool group having its own fractional allocation decision variable, fg,s,t;
taking into account variable process time ratios, Rg,s,t, on such tool groups to a process time of the primary tool group by introducing an effective available time per day
obtained by dividing actual available time per day, At, by a respective variable process time ratio, Rg,s,t, and further multiplying by a number of tools in the tool group, Nt, to obtain an effective available time per day for an entire tool group;
summing the fractional allocation decision variable fg,s,t for each tool group over all operations contained within the set OperbyGrp[g], that contains all operations associated with the cascade group g, and then summing over all those tool cascade groups, ToolsbyGrp[g], to which that tool group belongs according to the expression in order to obtain a total fractional use decision variable, Ft, for that tool group for use in a linear program (LP) objective function that constrains utilization of that tool group; and employing penalty functions having very steep slopes above a fractional use (FracUse) of one, said penalty functions being so employed in order to achieve a feasible solution to the Linear Programming (LP) equations when tool groups are forced to be used beyond their capacity for product starts at the minimum of their ranges, said feasible solution providing information on the amount by which tool group capacity is exceeded. - View Dependent Claims (2)
-
-
3. A computer implemented method providing accurate capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate a workload, said method comprising the steps of:
-
inputting data detailing by time period, processing times, tool availabilities and load factors, and a number of passes per product for every operation on every tool group in a manufacturing line;
scanning a list of operations, locating identical operation names within cascade sets of tool groups and organizing the operations and tool groups into the appropriate cascade groups, OperbyGrp and ToolsbyGrp, respectively, as Linear Programming (LP) input data files, the step of organizing tool groups and the operations into the appropriate cascade groups as Linear Programming (LP) input data files including the step of combining processing times and number of times a product visits a particular operation into a derived quantity Up,g,s, called Usage, which represents a required time to process a unit start of product p through all passes of an operation s, on a primary or otherwise preferred tool group contained in tool cascade group g;
calculating from the LP input data files an allocation of workload to parallel, unrelated tool groups in a cascade set, with a preference for an order in which the tool groups are to be used and in which ratios of process times of operations performed on different tool groups varies by operation;
generating output files which report the derived optimum product starts by product and required number of tools by tool group;
multiplying the Usage, Up,g,s, for each operation s by a number of product starts, Wp, for product p;
summing over all products, P, to obtain a total required time for that operation according to the expression
thus obtaining a total required time referenced to the primary or otherwise preferred tool group in tool cascade group t for all products being processed through operation s;
then allocating the total required time over the tool groups contained in tool cascade group g capable of performing that operation, according to the expression
each tool group having its own fractional allocation decision variable, fg,s,t;
taking into account variable process time ratios, Rg,s,t, on such tool groups to a process time of the primary tool group by introducing an effective available time per day
obtained by dividing actual available time per day, At, by a respective variable process time ratio, Rg,s,t, and further multiplying by a number of tools in the tool group, Nt, to obtain an effective available time per day for an entire tool group;
summing the fractional allocation decision variable fg,s,t, for each tool group over all operations contained within the set OperbyGrp[g], that contains all operations associated with the cascade group g, and then summing over all those tool cascade groups, ToolsbyGrp[g], to which that tool group belongs according to the expression in order to obtain a total fractional use decision variable, Ft, for that tool group for use in a linear program (LP) objective function that constrains utilization of that tool group; and employing penalty functions to track tool groups in each cascade set in order to allocate work in a proper rank order of tool groups, said penalty functions being adjusted to maximize use of the primary tool group while minimizing use of the non-primary tool groups, said adjustment placing the primary tool group penalty function above a horizontal axis with negative slope and placing the non-primary tool group penalty functions below said horizontal axis with positive slope, said adjustment further providing for the ratio of the penalty slopes of any two non-primary tool groups to exceed the ratio of the respective processing rates of said any two non-primary tool groups, wherein work is directed to a slower higher ranked tool group in preference to a faster lower ranked tool group. - View Dependent Claims (4, 5)
-
-
6. A computer implemented method of allocating work in capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate a workload, said method comprising the steps of:
-
aggregating data of all the sequential operations of the parallel, unrelated tools and the processes needed to produce a product by time period into a set of distinct operations by identifying sequential operations that are actually the same operation performed on different products and also identifying the same sequential operations performed multiple times on a single product, sequential operations being all the separate operations performed in sequence on each separate product processed on a manufacturing line and the number of multiple times the same sequential operations are performed on a single product being referred to as the number of passes for that distinct operation on that product;
scanning the aggregated data for the distinct operations, locating identical distinct operations within individual cascade sets of tool groups, and organizing operations and tool groups into related sets; and
formulating a non-integer, linear program having said related sets as input with piecewise-linear penalty terms incorporated into an objective function which distributes work in a preferred sequence among such parallel, unrelated tool groups and which linear program, by the use of a summation in the objective function of product starts multiplied by profit or revenue per product start, also can optimize product mix for a fixed tool set when product starts are allowed to vary by product type over finite ranges, wherein said related sets are the sets OperbyGrp and ToolsbyGrp determined, respectively, by the collection into disjoint sets of all those operations that can be performed on specific sets of tool groups, and by the specific sets of tool groups that can perform the operations in each of the sets OperbyGrp.
-
-
7. A computer implemented method of allocating work in capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate a workload, said method comprising the steps of:
-
aggregating data of all the sequential operations of the parallel, unrelated tools and the processes needed to produce a product by time period into a set of distinct operations by identifying sequential operations that are actually the same operation performed on different products and also identifying the same sequential operations performed multiple times on a single product, sequential operations being all the separate operations performed in sequence on each separate product processed on a manufacturing line and the number of multiple times the same sequential operations are performed on a single product being referred to as the number of passes for that distinct operation on that product;
scanning the aggregated data for the distinct operations, locating identical distinct operations within individual cascade sets of tool groups, and organizing operations and tool groups into related sets; and
formulating a non-integer, linear program having said related sets as input with piecewise-linear penalty terms incorporated into an objective function which distributes work in a preferred sequence among such parallel, unrelated tool groups and which linear program, by the use of a summation in the objective function of product starts multiplied by profit or revenue per product start, also can optimize product mix for a fixed tool set when product starts are allowed to vary by product type over finite ranges, wherein said related sets are the sets ToolsbyOper and OperbyTool determined, respectively, by what are the specific combinations of tool groups that can perform each operation and the specific sets of operations that can be performed on each tool group.
-
-
8. A computer implemented method of allocating work in capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate a workload, said method comprising the steps of:
-
aggregating data of all the sequential operations of the parallel, unrelated tools and the processes needed to produce a product by time period into a set of distinct operations by identifying sequential operations that are actually the same operation performed on different products and also identifying the same sequential operations performed multiple times on a single product, sequential operations being all the separate operations performed in sequence on each separate product processed on a manufacturing line and the number of multiple times the same sequential operations are performed on a single product being referred to as the number of passes for that distinct operation on that product;
scanning the aggregated data for the distinct operations, locating identical distinct operations within individual cascade sets of tool groups, and organizing operations and tool groups into related sets; and
formulating a non-integer, linear program having said related sets as input with piecewise-linear penalty terms incorporated into an objective function which distributes work in a preferred sequence among such parallel, unrelated tool groups and which linear program, by the use of a summation in the objective function of product starts multiplied by profit or revenue per product start, also can optimize product mix for a fixed tool set when product starts are allowed to vary by product type over finite ranges, wherein each said distinct operation is a sequential operation.
-
-
9. A computer implemented method providing accurate capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate a workload, said method comprising the steps of:
-
inputting data detailing by time period processing times, tool availabilities and load factors, and a number of passes per product for every operation on every tool group in a manufacturing line;
scanning a list of operations, locating identical operation names within cascade sets of tool groups and organizing the operations and tool groups as Linear Programming (LP) input data files;
calculating from the LP input data files an allocation of workload to parallel, unrelated tool groups in a cascade set, with a preference for an order in which the tool groups are to be used and in which ratios of process times of operations performed on different tool groups varies by operation; and
generating output files which report the derived optimum product starts by product and required number of tools by tool group, wherein the step of calculating an allocation of workload to parallel, unrelated tool groups in a cascade set further comprises the step of employing penalty functions having very steep slopes above a fractional use (FracUse) of one, said penalty functions being so employed in order to achieve a feasible solution to the Linear Programming (LP) equations when tool groups are forced to be used beyond their capacity for product starts at the minimum of their ranges, said feasible solution providing information on the amount by which tool group capacity is exceeded.
-
-
10. A computer implemented method providing accurate capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate a workload, said method comprising the steps of:
-
inputting data detailing by time period processing times, tool availabilities and load factors, and a number of passes per product for every operation on every tool group in a manufacturing line;
scanning a list of operations, locating identical operation names within cascade sets of tool groups and organizing the operations and tool groups as Linear Programming (LP) input data files;
calculating from the LP input data files an allocation of workload to parallel, unrelated tool groups in a cascade set, with a preference for an order in which the tool groups are to be used and in which ratios of process times of operations performed on different tool groups varies by operation; and
generating output files which report the derived optimum product starts by product and required number of tools by tool group, wherein the step of calculating an allocation of workload to parallel, unrelated tool groups in a cascade set further comprises the step of employing penalty functions to track tool groups in each cascade set in order to allocate work in a proper rank order of tool groups, said penalty functions being adjusted to maximize use of the primary tool group while minimizing use of the non-primary tool groups, said adjustment placing the primary tool group penalty function above a horizontal axis with negative slope and placing the non-primary tool group penalty functions below said horizontal axis with positive slope, said adjustment further providing for the ratio of the penalty slopes of any two non-primary tool groups to exceed the ratio of the respective processing rates of said any two non-primary tool groups, wherein work is directed to a slower higher ranked tool group in preference to a faster lower ranked tool group. - View Dependent Claims (11)
-
-
12. A computer implemented method providing accurate capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate a workload, said method comprising the steps of:
-
inputting data detailing by time period processing times, tool availabilities and load factors, and a number of passes per product for every operation on every tool group in a manufacturing line;
scanning a list of operations, locating identical operation names within cascade sets of tool groups and organizing the operations and tool groups as Linear Programming (LP) input data files;
calculating from the LP input data files an allocation of workload to parallel, unrelated tool groups in a cascade set, with a preference for an order in which the tool groups are to be used and in which ratios of process times of operations performed on different tool groups varies by operation; and
generating output files which report the derived optimum product starts by product and required number of tools by tool group, further comprising as part of the step of organizing tool groups and the operations as Linear Programming (LP) input data files the steps of organizing tool groups and the operations into the sets ToolsbyOper and OperbyTool, respectively, and combining processing times and number of times a product visits a particular operation into a derived quantity Up,s, called Usage, which represents a required time to process a unit start of product p through all passes of an operation s, on a primary or otherwise preferred tool capable of processing operation s. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21)
multiplying the Usage, Up,s, for each operation s by a number of product starts, Wp, for product p;
summing over all products, P, to obtain a total required time for that operation according to the expression
thus obtaining a total required time referenced to the primary or otherwise preferred tool group of those tool groups capable of performing operation s;
then allocating the total required time over the tool groups contained in tool groups capable of performing operation s, according to the expression
each tool group having its own fractional allocation variable, fs,t, that represents the fraction of the total capacity of the tool group t that is devoted to performing operation s; and
taking into account variable process time ratios, Rs,t, on such tool groups to a process time of the preferred tool group by introducing an effective available time per day,
obtained by dividing actual available time per day, At, by a respective variable process time ratio, Rs,t, and further multiplying by a number of tools in the tool group, Nt, to obtain an effective available time per day for an entire tool group.
-
-
14. The computer implemented method of claim 13 further comprising the step of summing the fractional allocations fs,t for each tool group over all operations capable of being performed on that tool group, OperbyTool[t], according to the expression
-
s ∈ OperbyTool [ t ] f s , t in order to obtain a total fractional use Ft of that tool group that is a decision variable used in a linear program (LP) objective function that constrains utilization of that tool group.
-
-
15. The computer implemented method of claim 14 further comprising the step of employing penalty functions to track tool groups in each cascade set in order to allocate work in a proper rank order of tool groups, said penalty functions being adjusted to maximize use of the primary tool group while minimizing use of the non-primary tool groups, said adjustment placing the primary tool group penalty function above a horizontal axis with negative slope and placing the non-primary tool group penalty functions below said horizontal axis with positive slope, said adjustment further providing for the ratio of the penalty slopes of any two non-primary tool groups to exceed the ratio of the respective processing rates of said any two non-primary tool groups, wherein work is directed to a slower higher ranked tool group in preference to a faster lower ranked tool group.
-
16. The computer implemented method of claim 15 further comprising the step of employing penalty functions to identify gating tool groups among those tool groups in a cascade set operating at full capacity, said penalty functions being applied in a narrow intermediate region beginning at a tool group fractional use (FracUse) of one (1.0), said region having an upper limit in a small interval above one (1.0), said small interval being arbitrarily small, wherein said penalty functions have slopes which are adjusted, relative to slopes of penalty functions having a fractional use (FracUse) of less than one, in such a way as to drive the operating point for said gating tool groups to said upper limit of said narrow intermediate region.
-
17. The computer implemented method of claim 16 further comprising the step of receiving inputs from a user changing a number of tools by tool group and allowed ranges of product starts by product in order to generate trial outputs to “
- what-if”
scenarios.
- what-if”
-
18. The computer implemented method of claim 14 further comprising the step of employing penalty functions having very steep slopes above a fractional use (FracUse) of one, said penalty functions being so employed in order to achieve a feasible solution to the Linear Programming (LP) equations when tool groups are forced to be used beyond their capacity for product starts at the minimum of their ranges, said feasible solution providing information on the amount by which tool group capacity is exceeded.
-
19. The computer implemented method of claim 18, wherein said inputting step includes desired tool group rank order for every operation, and wherein said sets ToolsbyOper[s] thereby become ordered sets, further comprising the step of employing penalty functions associated with each tool allocation decision variable to track operations and tool groups in each cascade set in order to allocate work in a proper rank order of tool groups by operation, said penalty functions being adjusted to maximize use of the primary tool group while minimizing use of the non-primary tool groups, said adjustment placing the primary tool group penalty function above a horizontal axis with negative slope and placing the non-primary tool group penalty functions below said horizontal axis with positive slope, said adjustment further providing for the ratio of the penalty slopes of any two non-primary tool groups to exceed the ratio of the respective processing rates of said any two non-primary tool groups, wherein work is directed to a slower higher ranked tool group in preference to a faster lower ranked tool group.
-
20. The computer implemented method of claim 12 further comprising the steps of:
-
dividing the Usage, Up,s, for each operation s by the time required to process one part through operation s on the preferred tool group tp of cascade group g, Hs,tp, to obtain the number of yield adjusted passes of product p undergoing operation s in cascade group g, Jp,s;
multiplying the number of yield adjusted passes, Jp,s, for each operation s by a number of product starts, Wp, for product p;
summing over all products, P, to obtain a total number of unit starts per day adjusted for yield across all products being processed through operation s according to the expression
andthen allocating the total number of parts per day over the tool groups contained in tool groups capable of performing that operation s, according to the expression
each tool group having its own fractional allocation decision variable, fs,t, that represents the fraction of the total capacity of the tool group t that is devoted to performing operation s, and the quantity
representing the number of parts per day tool group t is capable of manufacturing.
-
-
21. The computer implemented method of claim 20, wherein the step of calculating an allocation of workload to parallel, unrelated tool groups in a cascade set further comprises the step of employing penalty functions having very steep slopes above a fractional use (FracUse) of one, said penalty functions being so employed in order to achieve a feasible solution to the Linear Programming (LP) equations when tool groups are forced to be used beyond their capacity for product starts at the minimum of their ranges, said feasible solution providing information on the amount by which tool group capacity is exceeded.
-
22. A computer implemented method providing accurate capacity planning for manufacturing environments comprising parallel, unrelated tools that can process the same operations at different rates and with preferences for the sequence in which those tools are selected to accommodate a workload, said method comprising the steps of:
-
inputting data detailing by time period processing times, tool availabilities and load factors, and a number of passes per product for every operation on every tool group in a manufacturing line;
scanning a list of operations, locating identical operation names within cascade sets of tool groups and organizing the operations and tool groups into the appropriate cascade groups, OperbyGrp and ToolsbyGrp, respectively, as Linear Programming (LP) input data files, and combining processing times and number of times a product visits a particular operation into a derived quantity Up,g,s, called Usage, which represents a required time to process a unit start of product p through all passes of an operation s, on a primary or otherwise preferred tool group contained in tool cascade group g;
calculating from the LP input data files an allocation of workload to parallel, unrelated tool groups in a cascade set, with a preference for an order in which the tool groups are to be used and in which ratios of process times of operations performed on different tool groups varies by operation;
generating output files which report the derived optimum product starts by product and required number of tools by tool group;
dividing the Usage, Up,g,s, for each operation s by the time required to process one part through operation s on the preferred tool group tp of cascade group g, Hg,s,tp, to obtain the number of yield adjusted passes of product p undergoing operation s in cascade group g, Jp,g,s;
multiplying the number of yield adjusted passes, Jp,g,s, for each operation s by a number of product starts, Wp, for product p;
summing over all products, P, to obtain a total number of unit starts per day adjusted for yield across all products being processed through operation s according to the expression
andthen allocating the total number of parts per day over the tool groups contained in tool cascade group g capable of performing that operation, according to the expression
each tool group having its own fractional allocation decision variable, fg,s,t, and the quantity
representing the number of parts per day tool group t is capable of manufacturing.- View Dependent Claims (23)
-
Specification