A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> sp-graph (this is called series composition). <s> We show that unit execution time jobs subject to a precedence constraint whose complement is chordal can be scheduled in linear time on m processors. Generalizations to arbitrary execution times are NP-complete. <s> BIB001 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> sp-graph (this is called series composition). <s> This paper addresses the problem of scheduling n unit length tasks on m identical machines under certain precedence constraints. The aim is to compute minimal length nonpreemptive schedules. We introduce a new order class which contains properly two rich families of precedence graphs: interval orders and a subclass of the class of series parallel orders. We present a linear time algorithm to find an optimal schedule for this new order class on any number of machines. <s> BIB002 </s> A survey on how the structure of precedence constraints may change the complexity class of scheduling problems <s> sp-graph (this is called series composition). <s> Scheduling of unit execution time (UET) task systems on parallel machines with minimal schedule length is known to be NP-complete. The problem is polynomially solvable for some special cases. For a fixed number of parallel machines m > 2, the complexity of the problem is still open, but the problem becomes NP-hard if m is arbitrary. In this paper we characterize a new order class that properly contains quasi-interval orders and we prove that the Coffman--Graham algorithm yields optimal schedules for this new class on any number of machines. Finally, some extensions are discussed for a larger order class and for scheduling in the presence of unit communication delays. <s> BIB003
An example is given in Figure 3 . Note that sp-graph can also be defined by the forbidden subgraph of A divide-and-conquer-graph (DC-graph) is a special sp-graph built using symmetries. It can be used to model divide-and-conquer algorithms (for example binary search, merge sort, number multiplication...) and is formally defined as follows: Definition 3 (DC-graph) A single vertex is a DC-graph; given two vertices s and t and k DC-graphs This definition is illustrated with Figure 5 . An example is given in Figure 6 . BIB001 show that interval order graphs can also be defined by the forbidden induced subgraph presented in Figure 7 . Larger classes of graphs were defined by forbidden subgraphs, such as quasi-interval order graphs and over-interval order graphs (respectively in BIB002 and BIB003 ), the quasi-interval order graphs being strictly included in over-interval order graphs. The corresponding forbidden subgraphs are drawn in Figures 8 and 9. To ease the reading, the following definitions will be given within the order theory paradigm. We will hence talk about a partial order set P = (X, P ) rather than a directed acyclic graph G = (X, A) to describe the precedence graph, and a partial order P corresponds to the precedence constraints.