Almanach-HF/flowshop_transformer

Abstract

The goal of this project is to explore the applicability of the Transformer architecture to solve an NP-Hard combinatorial optimization problem (COP). For this study, we choose to focus on a single COP known as the permuation flowshop problem (PFSP), where we seek to schedule the launch of several jobs to go through a chain of machines with the goal of reducing total completion time also known as the MakeSpan. To apply the Transformer architecture to the PFSP, we consider the jobs as tokens to which learned embeddings can be associated, and we investigate an approach involving two learning phases: (1) in the first phase, we train our Transformer network to act as a surogate to the MakeSpan objective function (2) in the second phase, we recover the schedule using learnable schedule embeddings combined with the trained Transformer surrogate to minimize the MakeSpan over a continuous space while also leveraging a regularization strategy matching the schedule embeddings to trained job embeddings.

Challenges:

1. Designing/Balancing the training dataset + tuning the network hyper-parameters to train a high quality Transformer surrogate with minimal computational ressources.
2. Identifying the appropriate strategy/regularization for matching the schedule embeddings with the job embeddings.

Permuation Flowshop Problem (PFSP)

The Permutation Flow-Shop Problem (PFSP) considers a ( Jobs x Machines ) matrix, where each job requires some processing time in each machine, the notable constraints being:

1. Each job must go sequentially along the same chain of machines, in the same order.
2. A machine can process only one job at a time.

Different launch sequences result in different completion times of all the jobs. The goal is to find the sequence that minimizes the completion time (MakeSpan).This NP-Hard problem is of great importance in modern industry and to reduce production time, energy consumption, and generated pollution.

Proposed approach

Given an PFSP instance, i.e. a Jobs x Machines matrix, the idea we would like to investigate is to recover an optimal/pseudo-optimal schedule using a two learning phases process:

Phase 1: In this phase, the goal is to train a neural model (which we will call the objective surrogate or simply surrogate) to learn latent job embeddings and to predict/estimate the MakeSpan associated with job schedules that are represented as sequences of those job embeddings, specifically:

1. We generate a training dataset containing (x=job schedule, y=MakeSpan) pairs.
2. We train the neural model (we will focus on the Transformer architecture) on this dataset in a supervised way: the model learns to predict/calculate the MakeSpan for a given input job schedule.

Phase 2: In the second phase, we recover the optimal/pseudo-optimal job schedule in the following way:

1. We freeze the neural network weights, and save aside the learned job embeddings $J$
2. We initialize a set of learnable schedule embeddings $S$ which have the same dimension as the job embeddings.
3. We seek for: $$S^{\ast }=argminNeuralModel(S)s\mathrm{.}t\mathrm{.}\text{ S is a permutation of J}S^*\; =\; argmin\backslash \; NeuralModel(S)\backslash \backslash \; s.t.\backslash \; \backslash text\{S\; is\; a\; permutation\; of\; J\}$$ where $NeuralModel(S)$ represents surrogate objective i.e. the MakeSpan predicted by the model for the schedule S. Enforcing the condition that $S$ is a permutation of $J$ will require additional regularization on the surrogate objective. A straigtforward way would be to consider the cosine similarity matrix between $S$ and $J$ in the following way: Other approaches could be to use the Sinkhorn-Gumbel regularization porposed by *'Gonzalo Mena, David Belanger, Scott Linderman, & Jasper Snoek. (2018). Learning Latent Permutations with Gumbel-Sinkhorn Networks'*.

Link with the course

This project will envolve several aspects related to the course, at least:

1. Finding an appropriate neural net architecture that can model the right inductive biases for solving our task $\rightarrow$ course 3: Architectures.

2. The exploratory nature of this project will involve some visualizations to investigate the behavior of the proposed model, such as the similarity matrix obtained at the end of the optimization in phase 2 $\rightarrow$ course 2: Interpretability: visualization and analysis.

3. Controlling the bias in the generated dataset, such as the ratio of good and bad PFSP schedules $\rightarrow$ course 4: Issues with datasets.

Dataset used

• We will generate our own synthetic PFSP instances and associated datasets.
• We may also consider using known PFSP benchmarks such as E. Taillard (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.

Experiment plan

1. We begin with small PFSP instances (with a few jobs like 5 to 9 jobs, 2 to 5 machines) to see how capable the neural model is to recover optimal solutions. We will probably consider these two experiment variants:

   • variants where we encode the PFSP times matrix in the neural model and others where we do not
   • variants where we provide the optimal schedule in the training dataset and others where we do not.

2. We increase afterwards the size of our PFSP instances and/or move to literature benchmarks like Taillard's.

3. We compare ourselves essentially with classical approaches for solving PFSP, as to the best of our knowledge, this is the first time a fully neural based approach is proposed to solve this problem, though a close paper exists that also targets PFSP with a neural model but employs a much different strategy and focuses on a different objective function other than MakeSpan, known as Total Flow Time (see I. Garmendia, A., Ceberio, J., & Mendiburu, A. (2024). Applicability of Neural Combinatorial Optimization: A Critical View. ACM Trans. Evol. Learn. Optim., 4(3).)

References

I. Garmendia, A., Ceberio, J., & Mendiburu, A. (2024). Applicability of Neural Combinatorial Optimization: A Critical View. ACM Trans. Evol. Learn. Optim., 4(3).

Gonzalo Mena, David Belanger, Scott Linderman, & Jasper Snoek. (2018). Learning Latent Permutations with Gumbel-Sinkhorn Networks'

E. Taillard (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.