Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
1998-12-18
2001-08-21
Gordon, Paul P. (Department: 2121)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C700S100000
Reexamination Certificate
active
06278901
ABSTRACT:
FIELD OF THE INVENTION
The present invention involves the automated selection of jobs for execution in a manufacturing environment using a declarative description of the environment and/or updates regarding the current status of jobs being executed within the environment.
BACKGROUND
Within manufacturing plants, deciding what products to produce (assuming the plant 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 are questions that continually confront the owners and operators thereof. Many times, these questions are complicated by the fact that different products have different associated costs and values. Further, such plants are often faced with requests to produce many more products than can reasonably be manufactured in a given time frame. Thus, the challenge is to decide how best to employ the available resources for the tasks presented. Stated differently, the question is how to select a “best” subset of the available jobs for completion (and, perhaps, in what order to execute them).
In some cases, aggregate planning techniques have been used to help answer such questions. Aggregate planning may be characterized as the development of a plan for plant operations for given time periods. The goal may be to develop a plan that minimizes cost while meeting the demands of the jobs to be processed. Although useful, many current aggregate planning solutions are computationally intensive. For example, although “brute force” techniques could be used to select from among a list of possible jobs, where the number of jobs is anything more than trivial, these techniques simply require too much processing time to be of much benefit. Further, “trial and error” solutions, although perhaps easier to implement, often require too long to develop and/or update. Thus, what is required is an aggregate planning solution that avoids such drawbacks.
SUMMARY OF THE INVENTION
Discussed herein is scheme wherein an aggregate plan for a set of job requests to be processed in a manufacturing environment (e.g., a print shop) may be produced given capacities for resources of the manufacturing environment, the capacities being represented by bins in multiple dimensions, some of which may be used by the jobs on an alternative basis. In such a scheme, producing the aggregate plan may be accomplished by selecting a subset of the job requests according to a bin packing procedure. For example, bin packing may be accomplished by selecting from among ordered lists of the job requests grouped according to costs for one or more of the resources. The ordered lists of job requests may be ordered in terms of value. In some cases, at least some of the job requests may have different values versus cost for different ones of the resources. Each alternative may be represented as a separate bin.
The scheme may also include developing a detailed schedule from the aggregate plan, the detailed schedule differing from the aggregate plan by including start and end times for the selected jobs. In some cases, the manufacturing environment may be represented by a declarative model including a first number of state nodes and a second number of task nodes interconnected with the state nodes, the bins being associated with the task nodes. 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 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: T918004 (1974-01-01), Chappell et al.
patent: 3581072 (1971-05-01), Nymeyer
patent: 3703006 (1972-11-01), Sharma
patent: 3703725 (1972-11-01), Gomersall 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.
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: 4796194 (1989-01-01), Atherton
patent: 4827423 (1989-05-01), Beasley et al.
patent: 4839829 (1989-06-01), Freedman
patent: 5229948 (1993-07-01), Wei et al.
patent: 5291397 (1994-03-01), Powell
patent: 5432887 (1995-07-01), Khaw
patent: 5463555 (1995-10-01), Ward et al.
patent: 5524077 (1996-06-01), Faaland et al.
patent: 5794207 (1998-08-01), Walker et al.
patent: 5826040 (2000-10-01), Fargher et al.
patent: 5946661 (1999-08-01), Rothschild et al.
patent: 6137588 (2000-10-01), Fargher et al.
patent: 0 517 953 A2 (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/31322 (1997-08-01), None
patent: WO 97/28506 (1997-08-01), None
patent: WO 97/29441 (1997-08-01), None
Guandong Liu, A Practical Approach for Integrated Order and Production Scheduling Problems, IEEE, pp. 101-105, Jun. 1994.*
Christopher Lozinski and C. Roger Glassey, Bottleneck Starvation Indicators for Shop Floor Control, IEEE, pp. 147-153, Nov. 1988.*
“A Fine Mes”, State of the Art; JIm Esch; Petersborough, NH, US; No. 12; pp. 67, 68, 70, 74, 75, Date unknown.
“Simulation System for Real-Time Planning, Scheduling, and Control”; Glenn R. Drake and Jeffrey S. Smith; pp. 1083-1090, Date unknown.
“Electronic Contracting with COSMOS-How To Establish, Negotiate and Execute Electronic Contracts on the Internet”; F. Griffel, M. Boger, H. Weinrcich, W. Lamersdorf and M. Merz; XP-002129707; pp. 46-55 Date unknown.
PCT International Search Report; International Application No. PCT/US 99/24177; Apr. 6, 2000.
PCT International Search Report; International Application No. PCT/US 99/24178; Apr. 6, 2000.
PCT International Search Report; International Application No. PCT/US 99/24193; Feb. 5, 2000.
PCT International Search Report; International Application No. PCT/US 99/24131 Dec. 4, 1998.
PCT International Search Report; International Application No. PCT/US 24132; Feb. 22, 2000.
“A Knowledge Based, Integrated Process Planning and Scheduling System for Document Preparation”; Roger M. Kerr; XP-00089297
Goodrow Cristos J.
Nelson Phillip C.
Winner Jeffrey B.
Blakely , Sokoloff, Taylor & Zafman LLP
Gordon Paul P.
Impresse Corporation
LandOfFree
Methods for creating aggregate plans useful in manufacturing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods for creating aggregate plans useful in manufacturing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for creating aggregate plans useful in manufacturing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2451848