There has been intensive research on tiebreakers for insertion-based constructive heuristics in the permutation flow shop scheduling problem when the objective is to minimize the makespan. In this paper we analyze the space of all possible tie-breaking rules for the most common insertion orders, and evaluate the efficacy of existing tiebreakers based on this analysis. We find that an optimal tie breaker would produce results that are about 1% better than current best tie breakers. We propose a constructive heuristic based on a truncated cyclic best-first search in the space of all tie breakers and show that it closely approximates the solutions that such an optimal tie breaker can achieve.