Lehrstuhl Mathematik & InformatikOn the Singularity of the 2-Processor Case in the Multiprocessor Scheduling Problem
Abstract. We investigate the scheduling problem for unit execution time jobs with precedence constraints on a variable number of processors. We show in the 2-processor case that the gap of performance between Critical-Path and Coffman-Graham schedules can be expressed in a graph theoretical fashion. We define a function Z associating to each dag G a number Z(G) between 0 and the length of the longest path in G. This function is related to a certain substructure called zigzag. Especially if G does not contain this substructure at all, then Z(G)=0. It is shown that in the 2-processor case Critical-Path schedules differ from optimum by additive term Z(G) in the worst case. Especially for dags without zigzags Critical-Path schedules are optimal as well as Coffman-Graham schedules.