Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
1998-12-04
2001-11-20
Grant, William (Department: 2121)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C705S002000
Reexamination Certificate
active
06321133
ABSTRACT:
FIELD OF THE INVENTION
The present invention is directed to a system for forecasting the first-available time for completion of a job request in a real-world environment, such as a manufacturing environment.
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.
To simplify the scheduling problem somewhat, the process is sometimes divided into two aspects: planning and scheduling. The term planning is used to identify those activities, and the relations therebetween, required to accomplish a set of goals. Scheduling then becomes the assignment of specific resources and time windows to the actions identified in the plan. Although the division of the scheduling problem into these two domains is useful, it does present certain problems because of the interdependent nature of planning and scheduling systems.
Complicating this division still further is the idea of introducing order promising. That is, given a work environment (e.g., a manufacturing environment) already burdened with a number of existing job orders, can the environment accept new orders for completion within customer-specified time constraints? Viewed differently, how can the new orders be accepted without disrupting the existing work already scheduled and yet still satisfy a guaranteed delivery time/date? This is a non-trivial complication to the scheduling dilemma because, as others have recognized, although historically price has been a principle factor in choosing a vendor, more and more customers are emphasizing timely (meaning certainly not late and perhaps not even early) delivery in making such decisions.
SUMMARY OF THE INVENTION
In one embodiment, the present invention provides an order promising system, which includes a scheduler configured to produce schedules for jobs to be performed in a dynamically changing environment and to accept queries regarding the possibility of scheduling as yet unscheduled jobs; and means for monitoring execution of one or more current schedules produced by the scheduler so as to maintain information regarding a current state of the environment for use by the scheduler when producing schedules. In one example, the scheduler is made up of an aggregate planning level and a detailed scheduling level. Then, the means for monitoring may include a workflow engine configured to receive updates from the environment during execution of the schedule. The system may further include an order promising module configured to provide the queries to the scheduler.
In some cases, the means for monitoring may further include a virtual representation of the physical environment, the virtual representation being updateable by the workflow engine in response to the updates. This virtual representation of the physical environment may be a model of a manufacturing environment, for example a print shop environment.
The model may be arranged as a directed graph, having a first number of state nodes and a second number of task nodes interconnected with the state nodes to define one or more paths through the directed graph, each of the paths comprising an alternating series of one or more of the state nodes and one or more of the task nodes with any predecessor state node in one of the paths representing a precondition for a subsequent task node along the one of the paths and any following state node of the subsequent task node along the one of the paths representing a result of applying one or more actions that correspond to that task node. The state nodes may be virtual representations of inventory items of the manufacturing environment. Alternatively, at least a subset of the state nodes as arranged in the hierarchy defined by the directed graph may collectively define a bill of materials for the manufacturing environment. Or, the first number of state nodes may define a route through the directed graph.
In addition to the above, each of the task nodes may define a virtual representation of a manufacturing process. Together, the task nodes may collectively define routings for the manufacturing environment. The individual routings may define bills of resources for the manufacturing environment.
In a further embodiment, a system that includes a hierarchical scheduling module configured to generate workflows for a series of jobs to be processed in a manufacturing environment; and an order promising module configured to query the hierarchical scheduling module to determine whether one or more additional jobs may be processed in the manufacturing environment within a specified time window is provided. The order promising module may be configured to first query an aggregate planning level of the hierarchical scheduling module to determine whether the one or more additional jobs may be processed. Further, the order promising module may be configured to query a detailed scheduling level of the hierarchical scheduling module to determine whether the one or more additional jobs may be processed in the event that the aggregate planning level returns a negative reply to the first query by the order promising module. The hierarchical scheduling module is preferably kept apprised of a current state of the manufacturing environment through updates to a virtual representation of the manufacturing environment, e.g., a model (as discussed above) thereof.
In yet another embodiment a method includes querying a hierarchical scheduling module configured to generate workflows for a series of jobs to be processed in a manufacturing environment to determine whether one or more additional jobs may be processed in the manufacturing environment within a specified time window. The querying may involve first querying an aggregate planning level of the hierarchical scheduling module to determine whether the one or more additional jobs may be processed. Further, the querying may require querying a detailed scheduling level of the hierarchical scheduling module to determine whether the one or more additional jobs may be processed in the event that the aggregate planning level returns a negative reply to the first query by the order promising module. The querying of the hierarchical scheduling module may be performed in response to user inquiries submitted via a user interface.
In the method, the hierarchical scheduling module is kept apprised of a current state of the manufacturing environment through updates to a virtual representation of the manufacturing environment. This may involve updating a model of a print shop environment.
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: T918004 (1974-01-01), Chappell et al.
patent: 3581072 (1971-05-01), Nymeyer
patent: 3703006 (1972-11-01), Sharma
patent: 3703725 (1972-11-01), Gomersa
Goodrow Cristos J.
Nelson Phillip C.
Smirnov Yuri V.
Winner Jeffrey B.
Blakely , Sokoloff, Taylor & Zafman LLP
Cabrera Zoila
Grant William
Impresse Corporation
LandOfFree
Method and apparatus for order promising does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for order promising, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for order promising will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2599125