Complex scheduling method and device

Details Complex scheduling method and device Complex scheduling method and device

2000-06-09

2003-08-12

Follansbee, John (Department: 2121)

Data processing: generic control systems or specific application

Specific application, apparatus or process

Product assembly or manufacturing

C705S002000

Reexamination Certificate

active

06606529

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
A method and device for scheduling a plurality of events.
2. Prior Art
Scheduling in general, including scheduling of a manufacturer's supply chain for time-sensitive and complex manufacturing operations while satisfying resource, geographic, temporal and operating constraints, is a highly complex, non-linear problem that falls into a notoriously difficult mathematical class of hard to solve problems (technically, “NP-hard”). Manual scheduling, even when computer-assisted, is expensive in terms of time, manpower, and funds and produces far less than optimal scheduling of critical resources for critical manufacturing requirements.
The prior art methods for automating supply chain scheduling for manufacturing systems produce solutions that are “adequate” (however defined), but often far from optimal, sometimes leading to bottlenecks, excess supply inventories, supply shortages, or temporal disconnects, all of which may disrupt the manufacturing process and drive up unit production costs. This is especially so for manufacturing of leading edge products and/or where large numbers of companies are involved in the manufacturing process. Automated real-time and optimal supply chain scheduling for manufacturing systems would increase scheduling (and hence manufacturing) effectiveness and reduce unit production costs by avoiding the negative consequences of non-optimal scheduling.
Past attempts at mathematically optimal scheduling have usually employed a single promising artificial intelligence (AI) or operations research (OR) methodology in a “brute force” computational assault on the problem. Each such methodology has weaknesses relative to solving large-scale, computationally complex supply chain scheduling problems. Generally speaking, manufacturing supply chain scheduling problems exhibit the following characteristics: (a) a large number of constrained resources that must be scheduled in order to accomplish the manufacturing process; (b) complexity in terms of geographic and temporal geometry; (c) time sensitive actions to be scheduled; and (d) present a large problem/solution space typically proportional to m!, where m is the number of supply chain events to be scheduled within the problem time horizon with worst-case single algorithm solution times that are exponential in m.
Computational complexity theory (CCT) deals with the time (T) it takes an algorithm implemented in a computer program to solve a problem. Typically, the computational complexity of a problem is classified according to the time needed to solve it on a Turing Machine (TM), defined as a finite state machine with an infinite read-write tape. T is expressed as a function of n, where n is a measure of the size of the input or the number of inputs to the TM for solving the problem. In CCT, T as a function of n, T(n), is generally expressed in “order-of-magnitude” form O (f(n)). T(n)=O (f(n)) means there exists constants k and n such that
T
(
n
)≦
k|f
(
n
)| for
n≧n
0
  (1)
For example, suppose that solution time for a problem is given by T(n)=5n+2. In this case, T(n)=O(n) since 5n+2≦6n for n≧2 (i.e.,f (n)=n, k=6, and n
0
==2). If T (n) is a polynomial of the form
T
(
n
)=
a
i
n
i
+a
i−1
n
i−1
+. . . +a
1
n+a
0
  (2)
then T(n)=O(n
i
); i.e., all constants and low-order terms are ignored. Thus for T(n)=O (n
2
), a doubling of the size of the problem quadruples the solution time required. It is common and useful to classify problems according to their order of magnitude time complexities.
A problem is polynomial or polynomial time if its solution time on a TM is given by T (n)=O (n
b
) for some constant b: solution time is constant if b=0, linear if b=1, quadratic if b=2, etc. Solution time is exponential if T(n)=O(b
h(n)
) for constant b and polynomial h(n). For large n, the order of magnitude complexity of a problem can make a dramatic difference in solution times.
The class of problems P that are solvable in polynomial time are considered tractable because they can usually be solved in a reasonable amount of time for reasonable size inputs. Problems that cannot be solved in polynomial time are generally considered intractable or “hard” problems because as the size of the input representing the problem increases, solutions become computationally infeasible on even the fastest computers.
On the other hand, the class NP (which stands for nondeterministic polynomial) consists of all problems that are solvable in polynomial time on a nondeterministic TM, where “solvable” in this case does not have the usual meaning. A nondeterministic TM does not systematically solve a problem as does a deterministic TM, but instead guesses a solution (hence the term nondeterministic) and then checks its correctness. A given problem is said to be solvable in polynomial time on a nondeterministic TM if a nondeterministic TM can check the correctness of its guessed solution in polynomial time. Unfortunately, worst case times for systematically (deterministically) solving NP problems in the usual sense of the term are often exponential. The so-called “satisfiability” problem is an example of an NP problem which may be stated as follows: determine whether there exists an assignment of values to a set of n boolean variables such that a given set of constraints over the variables is met.
The class NP includes the class P because any problem solvable in polynomial time on a deterministic TM is also polynomial solvable on a nondeterministic TM. If all NP problems are polynomial solvable on a deterministic TM, then P=NP. Although many problems in NP seem much harder than the problems in P (e.g., satisfiability problems) no one has yet proven that P≠NP. Several decades ago, the satisfiability problem was proved to have the property that every other problem in NP can be reduced to it in polynomial time. This means that if the satisfiability problem is polynomial solvable, then every problem in NP is polynomial solvable, and if some problem in NP is intractable, then the satisfiability problem must also be intractable. Since 1971, other problems have been shown to be equivalent to the satisfiability problem. This set of equivalent problems is called the set of “NP-complete” problems, and has the property that if any one of the problems in that set is in P, then all NP problems are in P and P=NP. Thus, NP-complete problems are the hardest problems in NP (and are therefore sometimes also called NP-hard), or said another way, they set the upper bound on “hardness” for NP problems.
The fastest known algorithms for systematically solving these problems have worst case solution times that are exponential in the size n of the problem. Finding a worst-case polynomial-time solution to one of them would be a major breakthrough in computer science. However, despite the fact that the worst-case or upper-bound solve times for NP problems are exponential in n, in actual practice, solve times are often shorter than worst-case.
In summary, the general scheduling problem has been shown to be an NP-hard combinatorial optimization problem. A combinatorial optimization problem consists of finding, from among a finite set of alternatives, one that optimizes the value of a given objective function. Scheduling problems are satisfiability problems, and thus NP-hard problems too, because they seek to assign boolean values to requested events (i.e., decide whether they are scheduled or not) such that a given set of constraints are met. There remains a need for a method and device for finding an optimal solution to the multi-task scheduling problem in real time.
SUMMARY OF THE INVENTION
It is a first object of the invention to provide means for obtaining an optimal solution to a multi-task scheduling problem.
It is a further object of the invention to provide a method which may be used in a computer envi

Affiliated with

Also associated with

Rating

Complex scheduling method and device does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Complex scheduling method and device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complex scheduling method and device will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3095020