Ordered sets have recently gained much importance in
many applied and theoretical problems in computer
science and operations research ranging from project
planning via processor scheduling to sorting and
retrieval problems. These problems involve partial
orders as their basic structure, e.g. as precedence
constraints in scheduling problems, or as comparability
relation among the objects to be sorted or retrieved.
Since many of the involved problems are NP-hard in
general, much attention has recently been given to
special classes of partial orders with "nice"
strutural properties that lend themselves the design of
efficient methods, and for obtaining bounds by
structural relaxation in more general situations.
Typical such classes are: series parallel partial
orders, N-free partial orders, interval orders,
two-dimensional partial orders, and partial orders with
special decomposition properties. This area of
"computationally tractable" classes of partial
orders shows many similarities and interactions with
algorithmic complexity of their recognition. In
addtion, we present the tractibility of these different
classes on several applications dealing with scheduling
and sorting.
