Internship: Tree Search Optimisation

Research internship at G-SCOP — iterative beam search for the Permutational Flowshop Problem, leading to a publication in the European Journal of Operational Research.

This internship focused on the Permutational Flowshop Problem (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.

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 from the literature and improve the best known solutions to date in a number of instances. This led to the publication of a scientific paper and a spot in the European Journal of Operational Research (EJOR).

Completed tasks

• 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 results and finding statistical tendencies to find better heuristics

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⁻ᵇ
• The solutions of uniform random instances of the same size follow a Gaussian distribution