Exact algorithm and machine learning-based heuristic for the stochastic lot streaming and scheduling problem

Abstract

<p>This paper presents a probabilistic variant of the classic lot streaming and scheduling problem (LSSP), in which the arrival times of products are stochastic. The LSSP involves a multi-product lot streaming problem and a sublot scheduling problem with a flow shop model and sequence-dependent setup times. While the deterministic LSSP has been studied in the literature, the problem with stochastic arrival times of products has not been explored. In this paper, we first derive some properties of the LSSP solution and propose closed-form expressions to compute the objective function of a given solution under three commonly used stochastic distributions. Based on these expressions, we develop a new exact dynamic programming (DP) algorithm and propose an efficient DP-based heuristic algorithm. Additionally, we build a machine learning model to predict whether a DP transition needs to be considered in the heuristic to improve its efficiency. Our computational study of test instances with various arrival time distributions shows that our algorithms can achieve promising results. Furthermore, we find that the machine learning model can simultaneously reduce the computational complexity and improve the algorithm’s accuracy.</p>