|
Organizers |
An improved algorithm for the jump number problem.
by
Catherine McCartin
Victoria University, Wellington
The scheduling of computer and manufacturing systems has been the subject of extensive research since the early 1950's. This talk will focus on a particular scheduling problem known as the `jump number problem'.
The `jump number scheduling problem' has been shown to be NP-complete. However, for a fixed parameter k, El-Zahar and Schmerl have shown that the decision problem ``is the jump number <= k?'', is solvable in polynomial time. Their algorithm has a running time in excess of O(nk!/k!), where n is the size of the schedule. This is impractical, even for small k. Furthermore, the exponent in n increases as k increases. We obtain a significant improvement on this by giving a linear-time constructive algorithm that outputs a schedule with <= k jumps, if one exists, or reports `no' otherwise.
Date received: June 8, 1999
Copyright © 1999 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cacc-38.