Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-06-04
2002-09-24
Trammell, James P. (Department: 3621)
Data processing: database and file management or data structures
Database design
Data structure types
C705S002000
Reexamination Certificate
active
06456996
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates in general to the fields of supply chain management, and single-enterprise and multi-enterprise planning and scheduling. More particularly, the present invention relates to a computer implemented scheduling system and process that uses an abstract local search technique.
BACKGROUND OF THE INVENTION
Computer implemented planning and scheduling systems are widely used for factory, enterprise and supply chain planning functions. In general, such systems can model the manufacturing or other environment and provide plans or schedules for producing items to fulfill consumer demand within the constraints of the environment.
The problem of planning or scheduling an environment can be represented as a constrained optimization problem. For example, consider a simple problem of sequencing a set of tasks on a resource in a manufacturing environment. In addition, assume that each task has a deadline, and the objective is to schedule each task so that it ends by the associated deadline. One way to view this problem, for example, is as a search in the space of start times. Under this view, the problem becomes a simple constrained optimization problem in which the variables are the start times, the constraint is that no tasks can overlap, and the objective is to minimize lateness. This type of approach to planning and scheduling problems can provide an efficient framework for producing plans.
An abstract local search (ALS) is an efficient approach for analyzing and resolving planning and scheduling a manufacturing or other environment. An ALS solves combinatorial optimization problems by making local moves in the space of abstract solutions. An abstract solution (for example, a task ordering) is mapped to a concrete solution (for example, a schedule) by a greedy solution builder that, generally, enforces all hard constraints. The concrete solution is then evaluated to determine flaws, usually by measuring soft constraint violations. The flaws in the concrete solution are used to generate modifications (moves) in the abstract solution, that might reduce the flaws in the concrete solution.
In non-analogous contexts, detecting flaws in concrete solutions and using them to drive modifications in abstract solutions has been shown to be effective in several local search applications (for example, GSAT for propositional satisfiability problems. Selman, Kautz, and Cohen, “Local Search Strategies for Satisfiability Testing”, 1993, Vol. 26,
DIMACS Series in Discrete Mathematics and Theoretical Computer Science
(American Mathematical Society). One article attributes the effectiveness of iterative repair to making use of important information about the current solution to guide the search. Minton, Johnston, Philips, and Laird, “Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method”,
Artificial Intelligence
58:161-205 (1990).
SUMMARY OF THE INVENTION
In accordance with the present invention, a computer implemented scheduling system and process are disclosed that use an abstract local search technique.
A technical advantage of the present invention is that the abstract local search technique is useful for solving constrained optimization problems. It is particularly suited to a problem domain where some fast deterministic algorithm can map a set of priorities into a solution that satisfies the hard constraints in the problem.
Although some forms of priorities have previously been used for representing schedules, no general framework to integrate priorities into local search has been proposed. It is presented herein that the basic loop of priorities feeding into a greedy solution builder and an analysis technique that updates the priorities will be applicable to a large class of constrained optimization problems, and will scale to problems of realistic size and complexity.
REFERENCES:
patent: 5408663 (1995-04-01), Miller
patent: 5440681 (1995-08-01), Kudo
patent: 5467268 (1995-11-01), Sisley et al.
patent: 5559710 (1996-09-01), Shanraray et al.
patent: 5574640 (1996-11-01), Sycara et al.
patent: 5737728 (1998-04-01), Sisley et al.
patent: 5768594 (1998-06-01), Blelloch et al.
patent: 5787000 (1998-07-01), Lilly et al.
patent: 5887174 (1999-03-01), Simons et al.
patent: 5943652 (1999-08-01), Sisley et al.
patent: 6044222 (2000-03-01), Simons et al.
patent: 6272483 (2001-08-01), Joslin et al.
Lipske, Kenneth R., “A Greedy-based Decision Support System for Scheduling a Manufacturing Operation”, Production & Inventory Management Journal v37nl pp. 36-39 First Quarter 1996, ISSN: 0897-8336.*
Joslin, David E., “Squeaky Wheel” Optimization′, Journal of Artificial Intelligence Research 10 (1999), pp. 353-373. Submitted Aug. 1998, published May 1999.*
Lipske, “Greedy-based decision support system for scheduling a manufacturing operation,” Production and Inventory Management Journal, First Quarter 1996, APICS, vol. 37, No. 1 (Abstract).
Fred Glover, Manuel Laguna, “Tabu Search”, Modern Heuristic Techniques (Colin Reeves, Ed.) pp. 70-151.
E. Pinson, C. Prins, F. Rullier, “Using Tabu Search for Solving the Resource-Constrained Project Scheduling Program”.
Dr. Lawrence Davis, Bolt Beranek and Newman, Inc., “Job Shop Scheduling with Genetic Algorithms”, First Initial Conference Genetic Algorithms, CMV, Pittsburg 1985 Ed. Grefeuslette, John. pp. 136-140.
James M. Crawford, “An Approach to Resource Constrained Project Scheduling”.
Egon Balas, “Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm”.
Tonius Baar, Peter Brucker, Sigrid Knust, “Tabu-Search Algorithms for the Resource-Constrained Project Scheduling Problem”, Gsuabrueck Preprints, Reike P. Heft, 192.
David P. Clements, James M. Crawford, David E. Joslin, George L. Nemhauser, Markus E. Puttlitz, Martin W. P. Savelsbergh, “Heuristic Optimization: A hybrid AI/OR approach”, Sep. 29, 1997.
Gilbert Syswerda, “Schedule Optimization Using Genetic Algorithms”.
Crawford, Jr. James M.
Dalal Mukesh
Walser Joachim Paul
Baker & Botts L.L.P.
i2 Technologies US, Inc.
Trammell James P.
Wang Mary
LandOfFree
Computer implemented scheduling system and process using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer implemented scheduling system and process using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer implemented scheduling system and process using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823610