In this paper a heuristic algorithm is described that can constructively produce solutions to a variant of the Flexible Job Shop Problem (FJSP) that introduces changeover times between each pair of two operations consecutively performed on a machine. The performance of the heuristic algorithm is compared to the performance of an exact solver. Seven heuristics are compared for the FJSP variant with changeovers. The main objective function used is the makespan of the created schedules. The difference that occurs in the quality of the seven heuristics is examined also when instead the total lateness across all jobs is chosen as objective function. It concludes that a heuristic algorithm allows for the creation of good feasible solutions to complex problem instances for the FJSP variation with changeover times in under 30 seconds and that it outperforms an exact algorithm for the FJSP with changeover for use cases where efficiency is important and runtime is limited.