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

Abstract

This article 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. Although the deterministic LSSP has been studied in the literature, the problem with stochastic arrival times of products has not been explored. In this article, 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.

Keywords:

• Stochastic arrival times
• lot streaming
• scheduling
• dynamic programming
• machine learning

Disclosure statement

The authors report that there are no competing interests to declare.

Notes

1 The data are available at https://github.com/Wangchengkai/Lot-Streaming-and-Scheduling-Problem

Additional information

Funding

This research is supported by the Science and Technology Commission of Shanghai Municipality "Science and Technology Innovation Action Plan" (No. 22511103603).

Notes on contributors

Ran Liu

Ran Liu is an associate professor in the Department of Industrial Engineering and Management, Shanghai Jiao Tong University, Shanghai, China. His research interests include combinational optimization, stochastic optimization, and the applications to healthcare and manufacturing operations management. He earned his PhD in industrial engineering from Shanghai Jiao Tong University, Shanghai, China, and his BS degree in industrial engineering from Northwestern Polytechnical University, Xi’an, China.

Chengkai Wang

Chengkai Wang is currently a PhD student in the Department of Industrial Engineering and Management at Shanghai Jiao Tong University, Shanghai, China. His research interests lie in queueing theory and the optimization of time-varying service systems. He received his BS degree in industrial engineering from Shanghai Jiao Tong University, Shanghai, China, in 2020, and he is continuing his studies at the same institution to pursue a PhD degree.

Huiyin Ouyang

Dr. Huiyin Ouyang is an assistant professor of operations management at HKU Business School. She obtained her bachelor’s and master’s degrees from Tsinghua University, and her PhD in statistics and operations research from the University of North Carolina at Chapel Hill. Prior to joining HKU Business School, she held a postdoctoral fellow position at the Department of Industrial Engineering and Management Science at Northwestern University. Her research focuses on stochastic modeling and analysis of service systems, healthcare operations, simulation analytics, and data-driven decision-making.

Zerui Wu

Zerui Wu is currently pursuing a PhD degree in the Department of Industrial Engineering and Management, Shanghai Jiao Tong University. His research interests include stochastic programming, exact and heuristic algorithm design, and the optimization of production and service systems. He received a BS degree in industrial engineering from Shanghai Jiao Tong University, Shanghai, China, in 2021.