Interval orders are partial orders defined by having interval representations. It is well known that a transitively oriented digraphGis an interval order iff its (undirected) complement G¯ is chordal. We investigate parallel algorithms Tot the following scheduling problem: Given a system consisting of a setTofntasks (each requiring unit execution time) and an interval order ≺ overT, and given m identical parallel processors, construct an optimal (i.e., minimal length) schedule for (T, ≺).