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

Annika Tonnius , Robert J. Martin

Original Paper

First online: 28.04.2023

DOI: 10.23773/2023_6

Cite this article as: Tonnius, A., Martin, R.J., Logistics Research (2023) 16:6. doi:10.23773/2023_6

Abstract

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 selfsupervised learning is well suited for high-performance applications involving the approximate optimization of discrete NP-hard problems.

Keywords

scheduling hybrid flow shop flowtime makespan relaxation neural networks self-supervised learning