Table of Contents
Tree Search Optimisation
Languages and technologies:
- C++
- Rust
- Python
- Git
- Visual Studio Code
Context :
This internship was focused on the permutational flowshop problem (see PFS), in this problem one tries to schedule jobs that need to be processed by machines in order to finish all of them in the least amount of time.
Here is an example of what a solution looks like, with each color representing the tasks of a job.
Finding the optimal solution for this problem is usually impossible as the number of possible solutions grows exponentially with the number of jobs, for this, heuristic algorithms are used to find good enough solutions. In our case a tree search exploration algorithm is used: the iterative beam search algorithm, this algorithm with a good heuristic proved to be exceptionally good for some instances of this problem, it managed to compete with state of the art algorithms of the literature and improve the best known solutions to date in a number of instances. This lead to the publication of a scientific paper and a spot in the European Journal of Operational Research (EJOR)
Completed Tasks :
For more detailed explanations here is a pdf explaining everything in more detail
Iterative beam search for the Permutational flowshop scheduling problem
- Optimisation of code to make the algorithm run as smoothly as possible
- Generating a dataset to test the code while also trying well known benchmarks
- Analysing the result and finding statistical tendencies to find better heuristics
Here are some interesting facts not mentioned in the paper:
The algorithm improves the solution each iteration, the current best solution over time follows the equation $y = C + a.x^{-b}$
Here is a histogram that shows that the solutions of uniform random instances of the same size follow a Gaussian distribution.
