Scheduling of pipelined operator graphs

We investigate a class of scheduling problems that arise in the optimization of SQL queries for parallel machines (Chekuri et al., 1995). In these problems, an undirected graph is used to represent communication and inter‐operator parallelism. The goal is to minimize the global response time of the system. We provide a polynomial time approximation scheme for the special cases where the operator graph is a tree, thereby improving on a polynomial time 2.87‐approximation algorithm by Chekuri et al. The approximation scheme is generalized to the case where the operator graph has treewidth bounded by a constant. We analyze instances with small response times for general operator graphs: Deciding whether a response time of four time units can be reached is easy, but deciding whether a response time of six time units can be reached is NP‐hard. Finally, we prove that for general operator graphs the existence of a polynomial time approximation algorithm with worst case performance guarantee better than 4/3 would imply P=NP.