The term flexible flow line (FFL) denotes a generalization of the standard flow shop where at least one stage comprises more than one machine. We present a scheduling algorithm for the FFL which minimizes a combination of job tardiness and machine utilization. To our knowledge, this is the first exact method that minimizes a tardiness based objective function for the given production facility. The algorithm makes use of a simple enumeration scheme and applies priority rule based simulation methods in order to compute lower bound values for the considered criteria in an efficient way. The exploration strategy of our algorithm is a combination of best first search and depth first search and connects the advantages of both methods in an adaptive dynamic manner. Based upon an efficient parallelization of the algorithm, it is now possible to solve problem instances of moderate scale in a reasonable amount of time.