Matching and scheduling in a generalized optimal selection theory

Studies a model for matching and scheduling a task structure onto a heterogeneous suite of computers. The paper first generalizes optimal selection theory (OST) and its later augmentations to include general dependency graphs, which represent dependencies between subtasks, and presents the generalized OST (GOST) model. The GOST model allows nonoptimal choices of machines, as in augmented OST (AOST), and heterogeneous code blocks, as in heterogeneous OST (HOST), and incorporates communication time, system reconfiguration time, and data reformatting time (needed when data is exchanged between heterogeneous processors). Under the GOST model, we address the problem of matching/scheduling dependency graphs on a heterogeneous suite of computers. For arbitrary dependency graphs, matching/scheduling is NP-complete. But for the special instances of trees, and, more importantly, in the case of series-parallel dependency graphs we present polynomial time algorithms for optimal matching/scheduling