Abstract In multiprocessors with static allocation of processes to processors, scheduling can be done locally for each processor. The scheduling strategy may have dramatic effect on the execution time of a parallel program. It is NP-hard to find an optimal schedule, and very little is known on how close the heuristic solutions get. In order to obtain nontrivial performance bounds, this study focuses on a restricted class of parallel programs, viz., chain structured programs. The major result is a theorem stating that if certain program parameters are known the execution time of the optimal schedule can be calculated within a factor of 2, even though the optimal schedule is unknown. Using a previously developed tool, one can extract the necessary parameters from a parallel program. This technique makes it possible to compare the execution time for different scheduling strategies with the optimal case. The technique used for calculating the performance bounds gives important hints on how to design efficient scheduling algorithms for chain structured programs.