Neural combinatorial optimization (NCO) has gained significant attention due to the potential of deep learning to efficiently solve combinatorial optimization problems. NCO has been widely applied to job shop scheduling problems (JSPs) with the current focus predominantly on deterministic problems. In this paper, we propose a novel attention-based scenario processing module (SPM) to extend NCO methods for solving stochastic JSPs. Our approach explicitly incorporates stochastic information by an attention mechanism that captures the embedding of sampled scenarios (i.e., an approximation of stochasticity). Fed with the embedding, the base neural network is intervened by the attended scenarios, which accordingly learns an effective policy under stochasticity. We also propose a training paradigm that works harmoniously with either the expected makespan or Value-at-Risk objective. Results demonstrate that our approach outperforms existing learning and non-learning methods for the flexible JSP problem with stochastic processing times on a variety of instances. In addition, our approach holds significant generalizability to varied numbers of scenarios and disparate distributions.

In order to compute lower bounds for shop scheduling problems, a lot of attention has been paid to adjustment techniques based on one-machine relaxations. We present such a new technique but, following the observation that machines are connected to each other through precedence constraints, we also study techniques that are based on the combination of precedence constraints and disjunctive constraints between operations that are processed on different machines. A computational study of the effectiveness of these new techniques is performed on job-shop and flow-shop instances.