Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Software program
Reexamination Certificate
1998-12-18
2003-04-08
Frejd, Russell (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Software program
C700S100000, C705S002000, C703S002000
Reexamination Certificate
active
06546364
ABSTRACT:
FIELD OF THE INVENTION
The present invention involves the selection of jobs for execution in manufacturing processes from declarative descriptions of the environment in which the processes are performed.
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. To assist in making such decisions, computational tools may be used to determine which products to produce and/or when to produce them. These tools are sometimes divided into two aspects: planning tools and scheduling tools. 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 use of such tools may assist in answering the questions posed, alone they cannot be relied upon to produce useful results. For example, if such tools are used in a static fashion, i.e., so that they are not used in a manner that accurately reflects the changes in the environment being experienced, they cannot be expected to produce reliable results. Further, such tools will not necessarily yield workflows that reflect detailed sets of instructions for how to assemble the products of interest. That is, where workflow specify the order in which various resources are to be employed to produce the products and, hence, act as assembly instructions for the product, scheduling tools may only generate worklists for individual items of equipment. What is needed therefore is an improved scheme for addressing the above-described needs of manufacturing environments.
SUMMARY OF THE INVENTION
An adaptive workflow system that includes a scheduling engine and a workflow engine is provided. The scheduling engine may be configured to build workflows that describe sequences of tasks to be performed in a dynamically changing environment. The workflow engine may be configured to monitor the execution of the tasks within the environment and to provide the scheduling engine with information regarding deviations of task executions from the workflows. When such deviations (e.g., changes in the environment) are detected and/or when new tasks are added, the workflow engine may trigger the scheduling engine to rebuild the workflows for as yet uncompleted tasks. The workflows may define start and end times, etc. for the tasks.
In general, the tasks may be a set of job requests to be processed in a manufacturing environment (e.g., a print shop). In such a scheme, the scheduling engine may be made up of an aggregate planner and a detailed scheduler. Aggregate plans that describe which jobs to do and how to do them may be first made and then passed to the detailed scheduler for timelining, and specific resource allocation, etc.
In some cases, the manufacturing environment may be represented by a declarative model that describes the bills of materials and bills of resources for the manufacturing environment. Alternatively, the manufacturing environment may be represented by a model that includes the resources consumed by the job requests.
Ultimately, workflows may be generated from the detailed schedule. The workflows represent procedural steps to accomplish the process to be performed within the manufacturing environment. In such cases, generating a workflow may be accomplished by choosing one or more of a number of paths through the model (e.g., using the hierarchical aggregate planning and detailed scheduling approach), 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.
In general though, any of a number of model representations may be used. Thus, generating a workflow may be accomplished by choosing any one of a plurality of feasible routes for completion of the process defined by the model; by choosing an optimal one of a plurality of routes for completion of the process defined by the model; or by choosing one of a plurality of routes defined by the model according to one or more user-defined criteria for route selection. The routes so chosen may define bills of resources for the real world environment defined by the model. New workflows may be generated in response to an update to the model.
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: 4475156 (1984-10-01), Federico et al.
patent: 4484522 (1984-11-01), Simeth
patent: 4495582 (1985-01-01), Dessert et al.
patent: 4578768 (1986-03-01), Racine
patent: 4584648 (1986-04-01), Dlugos
patent: 4601003 (1986-07-01), Yoneyama et al.
patent: 4648023 (1987-03-01), Powell
patent: 4796194 (1989-01-01), Atherton
patent: 4839829 (1989-06-01), Freedman
patent: 5016170 (1991-05-01), Pollalis et al
patent: 5053970 (1991-10-01), Kurihara et al.
patent: 5212791 (1993-05-01), Damian et al.
patent: 5229948 (1993-07-01), Wei et al.
patent: 5233533 (1993-08-01), Edstrom et al.
patent: 5278750 (1994-01-01), Kaneko et al.
patent: 5287194 (1994-02-01), Lobiondo
patent: 5291394 (1994-03-01), Chapman
patent: 5291397 (1994-03-01), Powell
patent: 5369570 (1994-11-01), Parad
patent: 5406476 (1995-04-01), Deziel, Jr. et al.
patent: 5432887 (1995-07-01), Khaw
patent: 5463555 (1995-10-01), Ward et al.
patent: 5504568 (1996-04-01), Saraswat et al.
patent: 5557367 (1996-09-01), Yang et al.
patent: 5574640 (1996-11-01), Sycara et al.
patent: 5592602 (1997-01-01), Edmunds et al.
patent: 5630070 (1997-05-01), Dietrich et al.
patent: 5729790 (1998-03-01), Conley et al.
patent: 5734837 (1998-03-01), Flores et al.
patent: 5748899 (1998-05-01), Aldrich
patent: 5754857 (1998-05-01), Gadol
patent: 5757669 (1998-05-01), Christie et al.
patent: 5765139 (1998-06-01), Bondy
patent: 5768506 (1998-06-01), Randell
patent: 5778364 (1998-07-01), Nelson
patent: 5794207 (1998-08-01), Walker et al.
patent: 0 517 953 (1992-12-01), None
patent: 09034953 (1997-02-01), None
patent: 11110451 (1999-04-01), None
patent: WO 96/10793 (1996-04-01), None
patent: WO 96/16365 (1996-05-01), None
patent: WO 97/07472 (1997-02-01), None
patent: WO 97/28506 (1997-08-01), None
patent: WO 97/29441 (1997-08-01), None
patent: WO 97/31322 (1997-08-01), None
Kerr, paper published in Proceedings of the 4th IFIP TC5/WG5.7 International Conference on Advances in Production Management Systems, 1991.*
‘A Knowledge Based, Integrated Process Planning and Scheduling System for document Preparation’; Roger M. Kerr; XP-000892975; pp. 479-509 (Copy in IDS of paper #7).*
“Introduction to Algorithms”; Cormen, Leiserson and Rivest, 1989, Published by MgGraw-Hill Book Company; pp 86-90 & 541-543.*
PCT International Search Report; International Application No. PCT/US99/24177; Apr. 6, 2000.
PCT International Search Report; International Application No. PCT/US99/24178; Apr. 6, 2000.
P
Flight John L.
Goodrow Cristos J.
Nelson Phillip C.
Smirnov Yuri V.
Soung Yuh-Wen
Blakely , Sokoloff, Taylor & Zafman LLP
Frejd Russell
Impresse Corporation
LandOfFree
Method and apparatus for creating adaptive workflows 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 creating adaptive workflows, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for creating adaptive workflows will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3048961