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

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 eective 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 eect 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 GierThompson (GT) scheduling algorithm, a constructive method that incrementally builds feasible schedules by resolving
resource conicts 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 conict 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 eectively.
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.

Date of Award	2025
Original language	English
Supervisor	Stefan Wagner (Supervisor)