Scheduling problems are of high relevance in various application areas, especially in production and logistic environments. A well-known problem setting is the job shop scheduling problem that occurs in traditional manufacturing systems. Modern manufacturing systems, however, are usually more complex and feature multi-purpose machines that allow to process different types of manufacturing operations. This is taken account of in the flexible job shop scheduling problem, which generalizes the job shop scheduling problem, by assuming that each operation must be processed by exactly one machine out of a given set of eligible machines. Moreover, in real-world manufacturing systems, the incorporation of setup times plays an important role and the workforce planning must be integrated, especially when having to consider a set of employees with differing skills. In the face of the growing automatization of manufacturing processes, the need for applicable solution approaches that promise a good trade-off between computational time and solution quality is becoming more important. Against this background, this cumulative thesis investigates various flexible job shop scheduling problems incorporating workforce constraints that are of practical relevance as well as presents novel exact and heuristic solution approaches for scheduling the respective problem variants.