Die vorliegende Arbeit beschäftigt sich mit Verallgemeinerungen des klassischen Job-Shop Scheduling-Problems J||Cmax. Im ersten Kapitel werden Probleme mit verallgemeinerten Reihenfolgerestriktionen, Maschinen mit deterministischen Nichtverfügbarkeitsintervallen und erneuerbaren diskreten Ressourcen eingeführt und modelliert. Als zu minimierende Zielfunktionen werden der Makespan, die Lateness, die Tardiness und die Summe der Fertigstellungszeiten verwendet. Im zweiten Kapitel wird zur Minimierung einer beliebigen der vier Zielfunktionen eine genetische lokale Suche entwickelt. Für das Verständnis der Heuristik wird zusätzlich die Struktur des Lösungsraumes untersucht. Im dritten Kapitel wird die genetische lokale Suche für die multikriterielle Optimierung und zur Approximation der Menge der Pareto-optimalen Lösungen erweitert. Schließlich wird zur Entscheidungsunterstützung ein Short-Listing-Verfahren, das die Menge der Pareto-optimalen Lösungen reduziert, entwickelt und untersucht. Die ausgewählten Lösungen sollten dabei eine möglichst gute Diversität aufweisen.