Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Health care management
Reexamination Certificate
1999-05-05
2002-12-03
Choi, Kyle J. (Department: 2163)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Health care management
C705S002000, C706S013000, C706S062000, C700S100000, C700S104000
Reexamination Certificate
active
06490566
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates to computer implemented management for business enterprises, and more particularly to a system and method for scheduling resources.
BACKGROUND OF THE INVENTION
Computer-implemented scheduling systems are increasingly being used in factories and other enterprises. Such systems model the enterprise environment and provide schedules for producing items to fulfill consumer demand within the constraints of the environment.
Typically, a scheduling problem can be represented as a constrained optimization problem. For example, consider the problem of sequencing a set of tasks on a single resource in a manufacturing environment. Assume each task has a deadline and that the objective is to schedule each task so that it is completed by its deadline. One way to view this problem is as a search in a space of start times. Under this view, the problem is a constrained optimization problem in which the variables are the start times, the constraint is that no tasks can overlap, and the objective is not missing deadlines.
Constraints may be categorized into “hard” and “soft” constraints. Hard constraints are those that are not to be violated. Soft constraints may be violated, but at the expense of some penalty or cost. One approach to scheduling is to first determine a candidate schedule that does not violate hard constraints, and then to evaluate that schedule in terms of soft constraint violations. This process continues until a “best” schedule is obtained.
Some scheduling problems can be described as being “tightly constrained”. These problems typically have many possible solutions, but have only a few solutions that do not violate hard constraints. The process of searching for candidate schedules can be tedious and consume much processing time.
SUMMARY OF THE INVENTION
One aspect of the invention is a computer-implemented method of scheduling tasks, the tasks having associated hard constraints. A genetic algorithm is used to generate an initial task permutation. This task permutation is represented as a directed graph, whose nodes are the tasks and whose edges are determined by the constraints. Given two arbitrary tasks, an edge exists in the corresponding nodes of the graph if the first task can be placed directly before the second task in the schedule, without violating any hard constraints. An acyclic subgraph is constructed and a long path through the subgraph is calculated, which is used to produce a candidate schedule. The quality of this schedule is evaluated, and its fitness is used as feedback to the genetic algorithm. The output schedule is the best result found during repeated iterations.
If the scheduling problem includes soft as well as hard constraints, the graph is constructed to represent only the hard constraints. Each candidate schedule produced from calculating a long path through the graph is subjected to soft constraints and evaluated in terms of soft constraint violations. The evaluation is fed back to the genetic algorithm to produce a new task permutation.
An advantage of the invention is that is an efficient method for solving tightly constrained scheduling problems. The use of graph-based processing permits hard constraints to be represented as feasible transitions between tasks and to be satisfied by heuristically finding a long path through the graph. The system would otherwise spend a great deal of effort evaluating schedules that violate hard constraints. The construction of a subgraph converts the problem of determining the longest path from a problem of NP complexity into a problem of O(E) complexity, where E is the number of edges in the graph.
REFERENCES:
patent: 5319781 (1994-06-01), Syswerda
patent: 5511158 (1996-04-01), Sims
patent: 5971596 (1999-10-01), Nishikawa
patent: WO-9814891 (1998-04-01), None
Lawler et al. The Traveling Salesman Problem. Wiley, 1985, pp. 28,29, 108-115.*
Mehlhorn. Graph Algorithms and NP-Completeness. New York: Springer-Verlag, 1984, p. 1-27.*
Sandnes et al. Improved static multiprocessor scheduling using cyclic task graphs: a genetic approach. Advances in Parallel Computing, Sep. 19-22, 1997, v12, p. 703-710.*
Fang et al. A genetic algorithm to hot strip mill rolling scheduling problems.. In Proceedings IEEE Conference on Tools with Artificial Intelligence, Nov. 10-12, 1998, pp. 264-271.*
Woo et al. Task scheduling in distributed computing systems with a genetic algorithm. High Performance Computing on the Information Superhighway, 1997. HPC Asia '97 , 1997, pp.:301-305.*
Coli et al. Global execution time minimization by allocating tasks in parallel systems. Proceedings Euromicro Workshop on Parallel and Dustributed Processing, 1995, pp. 91-97.*
Matsuda et al. Optimization of order allocation to in-stock slabs by genetic algorithm. Transactions of the Society of Instrument and Control Engineers, Japan, 1997, pp. 118-126 (abstracts only).
Baker & Botts L.L.P
Choi Kyle J.
i2 Technologies US, Inc.
Robertson D.
LandOfFree
Graph-based schedule builder for tightly constrained... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Graph-based schedule builder for tightly constrained..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph-based schedule builder for tightly constrained... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2978704