Fast risk estimation for job shop scheduling solutions under interval uncertainty via machine learning

Abstract This paper addresses the evaluation of quantile-based risk measures of the makespan in complex job shop scheduling problems represented as activity networks. We consider the case where activity durations are uncertain and only the range of possible duration values is known in advance for each activity. Risk assessment is a crucial step in activity scheduling as it enables decision-makers proactively address delays or worsening of the makespan, avoiding incurring extra costs due to missed deadlines or worsening of the service quality. In particular, we focus on the value-at-risk and the conditional-value-at-risk of the makespan associated with given a feasible schedule affected by uncertainty. Calculating these risk measures with an exact approach is computationally expensive and becomes progressively less efficient as problem complexity grows. We therefore propose a machine learning-assisted approach that provides a rapid and accurate estimate of these risk indicators based on specific features of the given activity network. Machine learning models can provide fast risk assessment by leveraging collected data of risk evaluations, and are suitable for integration into real-time risk management and optimization-based decision support systems. Computational experiments conducted on a wide set of benchmark instances demonstrate the effectiveness of the proposed approach, achieving very high accuracy in risk estimation while maintaining consistently fast computational times, regardless of the problem’s scale or complexity.