<p>This paper studies a variant of the flexible Flow Shop Scheduling Problem as encountered at a large-scale Belgian seafood processing plant. The operations are conducted in two sequential stages as the seafood products are first filleted or prepared on specialised machines and then packaged through parallel machines. Since the packaging is product-specific, sequence-dependent setup times should be considered in the second stage. Improved scheduling of the operations would require fewer setups and thus efficiently planning the operations on the machines at the packaging station will be an important objective of this research. Furthermore, since the end product quality is crucial in the food industry and this is mainly determined by the speed of processing, the makespan will be minimised in this study. However, we further contribute to the existing literature by investigating several objectives that were relevant to the company’s management. The scheduling problem is solved using a single- and multi-pass algorithms that can easily be implemented in the seafood processing plant. Furthermore, a genetic algorithm with a focus on various diversity measures and problem-specific crossover and mutation operators is developed. Although the genetic algorithm is more difficult to implement, it allowed us to solve real world cases with over 100 orders daily within a reasonable computational time, resulting in an improved solution quality.</p>