Zur Hauptnavigation wechseln Zur Suche wechseln Zum Hauptinhalt wechseln

Solution Archives and their Influence on Diversification and Intensification in Job Shop Scheduling Problems

  • Stefan Habringer

    Studienabschlussarbeit: Masterarbeit

    Abstract

    Job shop scheduling problems (JSSPs) constitute a class of NP-hard problems that model the structure of real-world production environments. The main challenge involves scheduling a set of jobs, each comprising several operations, on a limited set of resources, with the objective of minimising the makespan of the production process. Genetic algorithms (GA) represent a class of evolutionary algorithms that are able to nd approximate solutions to these problems. The primary disadvantage of GAs is their reliance on genetic diversity within their population of solution candidates. This is particularly true for complex problem instances, where GAs may exhibit limited exploration of the search space or premature convergence. An e ective GA must balance exploratory and exploitative behaviour. Several approaches exist to improve GAs in this regard, with solution archives representing one which is able to steer the algorithm during runtime. This thesis investigates the e ect of hybridisation and the introduction of a TRIE-based solution archive on the GA's ability to solve a set of JSSP benchmark instances. All solutions are generated using the well-established Gi¬er Thompson (GT) scheduling algorithm, a constructive method that incrementally builds feasible schedules by resolving resource con icts between operations. For the hybrid approaches, local- and tabu search operators are used, whilst the employed solution archive enables both exploratory or exploitation-focused behaviour. Within the archive, each solution is stored in its phenotype representation, a sequence of scheduled operations, with each node enriched by local scheduling context, namely the feasible operation and con ict sets derived during GT-based schedule construction. This structure allows for the generation of new candidates by recombining features of previously encountered high-quality solutions, thereby guiding the GA's search process more e ectively. The experimental results demonstrate that the solution-archive-enhanced genetic algorithm (SAGA) achieves quality values comparable to those of the canonical GA baseline, whilst simultaneously increasing both geno- and phenotype diversity within the population. This improvement, however, incurs increased algorithmic complexity and longer runtime.
    Datum der Bewilligung2025
    OriginalspracheEnglisch
    Betreuer/-inStefan Wagner (Betreuer*in)

    Studiengang

    • Software Engineering

    Zitieren

    '