Relaxation and self-supervised machine learning for the hybrid flow shop assignment problem

We present an approximation method for the hybrid flow shop scheduling problem based on relaxation and machine learning techniques. Our model combines a suitable relaxation of the objective function to a continuous solution space with a self-supervised learning method for neural networks, which does not require any labeled training data. Thereby, we avoid the pre-computation of exact solutions, which is generally not feasible for NP-hard problems such as hybrid flow shop scheduling. In terms of computational effort during the decision process, our approach outperforms other methods with similar approximation accuracy, which suggests that the considered technique of self- supervised learning is well suited for high-performance applications involving the approximate optimization of discrete NP-hard problems.