Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
1998-11-02
2002-02-12
Grant, William (Department: 2121)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C700S097000
Reexamination Certificate
active
06347256
ABSTRACT:
FIELD OF THE INVENTION
The present invention involves the creation of virtual representations of manufacturing processes and, in particular, homogeneous manufacturing environments that may be associated with on-demand manufacturing processes.
BACKGROUND
Within manufacturing environments, the questions of deciding what products to produce (assuming the environment is capable of producing more than a single product), when to produce them, how much of each to produce and whether to accept new orders for different products must all be weighed against the realities of the various constraints imposed upon and within the environment. For example, a given manufacturing environment that is currently operating at or near its maximum capacity should probably not be weighed down with additional order commitments that require immediate response. On the other hand, a manufacturing environment that is operating with excess capacity is capable of accepting new orders, but it may not be apparent how many orders are capable of being fulfilled within a specified time frame.
The process of job order scheduling, which is at the heart of the above dilemma, typically proceeds along a product structure in order to determine which components must be produced and/or purchased and when. This process is time consuming whenever the number of unique orders grows, which is a typical situation in on-demand manufacturing environments. This problem is exacerbated by the historical fashion in which product structures have been separated into bills of material and routings. Those of ordinary skill in the art have been unwilling to deviate from product structures that segregate these descriptions of a manufacturing process. See, Eliyahu M. Goldratt, The Haystack Syndrome, Ch. 27, p. 169 (1990) for a discussion of classical manufacturing modeling techniques and the reasons behind the inertial unwillingness to accept new modeling approaches in this field. As a result, scheduling in on-demand manufacturing environments remains a complex and time-consuming process.
Goldratt recognized that a product structure that could represent both bills of material and routings may allow for a reduction in the amount of computer processing time for successful scheduling operations. Id. at pp. 173-174. However, Goldratt failed to describe any manner for accomplishing this goal. At best then, Goldratt seems to have appreciated the problem but has left the development of a feasible solution to others.
SUMMARY OF THE INVENTION
The present invention provides a solution to the scheduling problem described above. Briefly, a model that integrates one or more bills of materials with one or more routings for a manufacturing environment is described. The model is constructed as an alternating structure of state nodes and task nodes. This structure implicitly defines the logical relationships between the nodes without requiring additional semantics. Each route through the model defines a bill of materials and its associated bill of resources, allowing for scheduling operations within the manufacturing environment.
In one embodiment, a directed graph includes a first number of state nodes and a second number of task nodes. The task nodes are interconnected with the state nodes to define one or more paths through the directed graph, each of the paths including an alternating series of one or more of the state nodes and one or more of the task nodes. Thus, any predecessor state node in one of the paths represents a precondition for a subsequent task node along that path. Further, any following state node of that task node represents a result of applying one or more manufacturing processes that correspond to the task node.
The state nodes may be virtual representations of inventory items of a manufacturing environment. Thus, collectively the state nodes may define one or more bills of material for the manufacturing environment. Similarly, the task nodes may each define a virtual representation of a manufacturing process within the manufacturing environment. In other words, the task nodes may collectively define one or more bills of resources for the manufacturing environment. In some cases, the bill of resources may be restricted to reusable resources, while in other cases both reusable and consumable resources may be represented.
In a further embodiment, a method of modeling a manufacturing environment is provided. The method provides for representing a final product of the manufacturing environment with a first state node of a directed graph. In addition, each manufacturing process required in the production of the final product and the corresponding preconditions thereto and results produced thereby may be represented as a number of corresponding task nodes and state nodes. In general, the task nodes may represent the manufacturing processes of the manufacturing environment. The state nodes may represent the preconditions to the task nodes and the results produced thereby. As described in greater detail below, the task nodes and the state nodes may be arranged within the directed graph such that inputs to each of the task nodes represent required states and outputs of each of the task nodes represent alternative states produced thereby. Within this arrangement, any state node, except possibly a start node, may represent the output of one or more of the manufacturing processes represented by one or more of the task nodes.
As will be discussed below, in some cases the task nodes may represent manufacturing processes which require reusable resources from the manufacturing environment, in other cases the they may not.
Within the directed graph, the state nodes may be arranged in a hierarchy so as to comprise one or more bills of material for the manufacturing environment. Further, the task nodes alternate with the state nodes along each of a number of paths through the directed graph, each path defines a route along which the final product may be generated.
In yet another embodiment, a computer assisted scheduling system is provided. The system includes a model of a real-world manufacturing environment. The model may be arranged as a directed graph and may include a first number of state nodes and a second number of task nodes interconnected therein to define one or more paths through the directed graph. Each of the paths may include an alternating series of one or more of the state nodes and one or more of the task nodes. In this arrangement, any predecessor state node in one of the paths represents a precondition for a subsequent task node along that path. Likewise, any state node following a task node represents a result of applying one or more manufacturing processes which correspond to the task node. The system further includes a scheduler configured to determine which of the routes through the direct graph to use to manufacture the product.
The production automation system that incorporates the described model may be configured to receive updates from the real-world manufacturing environment, where these updates represent changes in the manufacturing environment. For example, the changes may represent completed tasks and/or changes in the availability of one or more resources used by one or more of the task nodes.
Further details of these and other embodiments will be discussed below, however, it should be remembered that these are merely examples of implementations of the present invention.
REFERENCES:
patent: 3581072 (1971-05-01), Nymeyer
patent: 3703006 (1972-11-01), Sharma
patent: 3703725 (1972-11-01), Gomersall et al.
patent: T918004 (1974-01-01), Chappell et al.
patent: 3905045 (1975-09-01), Nickel
patent: 3930251 (1975-12-01), Salava et al.
patent: 3988570 (1976-10-01), Murphy et al.
patent: 4007362 (1977-02-01), Sindermann
patent: 4017831 (1977-04-01), Tieden et al.
patent: 4231096 (1980-10-01), Hansen et al.
patent: 4400783 (1983-08-01), Locke, Jr. et al.
patent: 4433426 (1984-02-01), Forster
patent: 4449186 (1984-05-01), Kelly et al.
patent: 4468750 (1984-08-01), Chamoff et al.
patent: 4475756 (1984-10-01), Federico et al.
pate
Flight John L.
Nelson Phillip C.
Smirnov Yuri V.
Soung Yuh-Wen
Winner Jeffrey B.
Bahta Kidest
Blakely & Sokoloff, Taylor & Zafman
printCafe System, Inc.
LandOfFree
Manufacturing process modeling techniques does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Manufacturing process modeling techniques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Manufacturing process modeling techniques will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960385