Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Health care management
Reexamination Certificate
2000-05-25
2001-05-22
Millin, Vincent (Department: 2765)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Health care management
C705S002000, C709S241000, C709S241000, C706S041000
Reexamination Certificate
active
06236976
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to systems and processes for scheduling complex jobs, and specifically to a scheduling system and process using limited discrepancy search techniques.
2. Description of Related Art
A class of problems known as “Constraint-Satisfaction Problems” (CSPs) arises often in diverse areas such as human resource allocation, artificial vision, event planning, map coloring, and the like. These problems are characterized in having a set of elements and a set of possible attributes, and in calling for a particular assignment of attributes to elements. An example of a CSP might be the problem of how to staff the night shift of a factory with at least one person who is intelligent and at least one person who is strong. Another, slightly more general, example is scheduling the jobs required, using finite available resources, to construct a prototype of a new product by a target date.
Processes using artificial intelligence (AI) techniques have been applied to CSPs not only to permit managers to allocate human and other resources in a feasible manner, but in a wide range of other diverse situations, for instance to help planners determine feasible schedules for meetings, to assist scientists in interpreting images from artificial vision devices, and even to allow cartographers to select colors for countries or other municipal areas when designing maps.
Two primary approaches have been taken in attempting to deal with such situations using artificial intelligence. The first is known as “systematic” because under this approach, every possible set of element-attribute pairings is eventually considered, unless a set of pairings that meets all of the constraints is found at some point in the process. These processes often rely on maintaining a database of possible reasons why certain assignments, or groups of assignments, will not satisfy the constraints of the CSP. The sets of reasons indicating assignments that do not work are commonly referred to as sets of “nogoods”. When a process of this class fails to provide a set of workable assignments, one can be sure that no workable set of assignments exists. Numerous such systematic processes are known, for instance as described in M. L. Ginsberg,
Dynamic Backtracking
, JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH 1:25-46, 1993.
The second class is known as “nonsystematic” and is typically faster to find a solution. However, because processes of this class do not keep track of whether they have considered all possible sets of element-attribute pairings, where such processes do not yield a solution, one cannot know whether a workable set of assignments exists but has not been found, or whether no workable set of assignments exists. A well-known example of such a nonsystematic technique is the GSAT technique, now known under an improved version as WSAT and described in B. Selman, et al.,
Local Search Strategies for Satisfiability Testing
, PROCEEDINGS 1993 DIMACS WORKSHOP ON MAXIMUM CLIQUE, GRAPH COLORING, AND SATISFIABILITY, 1993.
Several other known strategies within these two broad classes of processes have been employed to solve CSPs.
One known process is to simply apply a heuristic, or “rule of thumb,” and to see whether the heuristic results in an acceptable solution. One such heuristic might be: If machine A is available, use it; otherwise if machine B is available use it; otherwise if machine C is available use it; otherwise wait for machine A to finish and then use it. In some instances, such a technique works very well and provides a simple solution. When the heuristic fails, however, alternate techniques must be used.
One possible alternate scheme, known as iterative sampling, or isamp, involves following random paths, or probes, from a starting point until eventually a path leading to an acceptable solution is discovered. At each node on a path, one of the successor nodes is selected at random and followed; next, one of the successors to that node is selected, and so on, until either a “goal node”, i.e., acceptable solution, or a dead end is reached. If a path terminates at a dead end, a new probe is begun from the original starting point.
This process samples with replacement, resulting in a uniform chance of finding a goal node on any particular probe. Accordingly, the probability of achieving a goal node progresses uniformly to 1 as the number of probes grows without limit.
Iterative sampling works well in applications exhibiting high solution densities, but not otherwise.
Another scheme, known as “backtracking,” uses the heuristic approach as far as possible. When the heuristic is found to fail, the last decision before the failure is changed, unless all possible changes at that point have already been tried. If they have, the decision prior to that is changed, and so on. This process works well where heuristics early in the process are more reliable than those later in the process, because it does not revisit the earliest decisions until all of the subsequent paths have been found to fail. Unfortunately, in most real-world problems, heuristics generally become more reliable as a solution is approached and the problem is reduced in size.
Known processes for handling CSPs are all lacking in one way or another, particularly when applied to job scheduling problems. Known systematic approaches are computationally quite slow. Known nonsystematic approaches are unable to report with certainty the absence of a workable set of assignments. Furthermore, techniques such as GSAT perform very poorly in situations where there is no way to tell when one is “close” to a workable set of assignments. An example of a situation to which GSAT is not well suited is the CSP of generating a crossword puzzle by filling words from a fixed dictionary into a given frame, i.e., assigning letter attributes to square elements. GSAT falters here because a conflict at a single square may require reassignment of a large portion of the other words in the puzzle.
None of the known teachings provides an adequately robust process that does not suffer from these failings.
It would be helpful if a process and corresponding system could effectively combine systematic and non-systematic approaches to efficiently reach solutions to CSPs such as resource allocation and scheduling problems.
SUMMARY OF THE INVENTION
In accordance with the present invention, assignment of attributes to elements subject to constraints is achieved using a system (
100
) that has a systematic engine (
120
) and a nonsystematic engine (
130
). The systematic engine (
120
) includes a schedule developer (
121
) for producing partial proposed assignments, a pruning processor (
122
) for determining violations of discrepancy limits by a partial proposed assignment, and a bound selector (
123
) for relaxing discrepancy limits as needed. The non-systematic engine (
130
) includes a schedule packer (
131
) for modifying assignments proposed by the systematic engine and an evaluator (
132
) for comparing the modified assignments with the constraints.
Also in accordance with the present invention, a process of assigning attributes to elements includes iteratively generating a partial proposed assignment, determining whether it violates a predetermined discrepancy limit, and modifying the proposed assignment. If no partial proposed assignment can be constructed within the discrepancy limit, the limit is altered. A complete, but intermediate, assignment is then formed based on the proposed assignment, is improved by the non-systematic engine, and is evaluated with respect to the constraints. If the constraints are satisfied, the assignment is considered to be acceptable; otherwise, the process begins again with a new partial proposed assignment.
Still further in accordance with the invention, the schedule packer right-justifies and left-justifies a proposed assignment to improve the assignment.
The features and advantages described in the specification are not all-inclusive, and particularly, many additional features a
Crawford James M.
Ginsberg Matthew L.
Harvey William D.
Jonsson Ari K.
Pemberton Joseph C.
Fenwick & West LLP
Millin Vincent
Patel Jagdish N
State of Oregon Acting by and Through the State Board of Higher
LandOfFree
System and process for job scheduling using limited... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and process for job scheduling using limited..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and process for job scheduling using limited... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2570317