The Hybrid Flow Shop model with multiprocessor tasks, unrelated parallel machines and sequence dependent setup times

In this thesis we present a study focused on a scheduling problem that is inspired by the production process of mattresses. We can translate our scheduling problem into a multi-objective Hybrid Flow Shop model with non-identical multiprocessor tasks, unrelated parallel machines and sequence dependent setup times. To the best of our knowledge, we are the first to introduce research concerning the Hybrid Flow Shop model with these assumptions. We define our problem mathematically by means of a mathematical formulation, which also allows us to obtain a benchmark for small sized problem instances. Furthermore, we define a constraint programming formulation to solve small problem instances to optimality. Based on our mathematical formulation, we derive a lower and upper bound. Next to exact solution approaches, we adopt heuristic solution approaches from literature, a genetic and memetic algorithm, and adapt these methods to be able to solve our model. The outcomes of the resulting algorithms are compared to the optimal solution. It turns out that on certain small problem instances our heuristic solution approaches are able to produce optimal results. Finally, we study the performance of the heuristic approaches on a large industry based case study. On the large scale problem instances the genetic algorithm in combination with a linear programming optimization problem at the end yields the most successful results.