Title
M-Machine Unit Time Scheduling: A Report on
Ongoing Research
Authors
-
Publication
Springer, Lecture Notes in Economics and Mathematical Systems 304, Optimization, Parallel Processing and Applications, ed. A. Kurzhanski, K. Neumann und D. Pallaschke, 1988, pp. 165-213
Source
-
Classification
-
not available
Keywords
-
not available
-
-
Scheduling of partially unit time jobs on m machines,
aiming at minimal schedule length, is known to be one
of the notorious combinatorial optimization problems,
for which the complexity status is still unresolved.
Available results give polynomial time algorithms for
special classes of partial orders and for the two
machine case. The present paper includes a general
representation theorem on the existence of schedules of
a given schedule length and a corresponding algorithmic
method that allows a unifying approach to some of the
unresolved special cases. It includes also a general
algorithmic scheme that may work in the 3-machine case
and may eventually lead to a polynomial time algorithm
(or at least to membership in CO-NP) for the general
m-machine case. Finally, it gives some insight into
so-called m-critical posets, which should play an
essential role in a proof on the correctness for the
intended polynomial time algorithm.
