An Expectation-Maximization Algorithm-based Autoregressive Model for the Fuzzy Job Shop Scheduling Problem

Abstract

The fuzzy job shop scheduling problem (FJSSP) emerges as an innovative extension to the job shop scheduling problem (JSSP), incorporating a layer of uncertainty that aligns the problem more closely with the complexities of real-world manufacturing environments. This improvement increases the computational complexity of deriving the solution while improving its applicability. In the domain of deterministic scheduling, neural combinatorial optimization (NCO) has recently demonstrated remarkable efficacy. However, its application to the realm of fuzzy scheduling has been relatively unexplored. This paper aims to bridge this gap by investigating the feasibility of employing neural networks to assimilate and process fuzzy information for the resolution of FJSSP, thereby leveraging the advancements in NCO to enhance fuzzy scheduling methodologies. To achieve this, we approach the FJSSP as a generative task and introduce an expectation-maximization algorithm-based autoregressive model (EMARM) to address it. During training, our model alternates between generating scheduling schemes from given instances (E-step) and adjusting the autoregressive model weights based on these generated schemes (M-step). This novel methodology effectively navigates around the substantial hurdle of obtaining ground-truth labels, which is a prevalent issue in NCO frameworks. In testing, the experimental results demonstrate the superior capability of EMARM in addressing the FJSSP, showcasing its effectiveness and potential for practical applications in fuzzy scheduling.