The Multiresource Flexible Job-Shop Scheduling Problem with Early Resource Release

In this work, we study the multiresource flexible job-shop scheduling problem (MRFJSSP), which relaxes the standard “simultaneous occupation” policy described in the literature. This policy implies that a job operation starts only when all its assigned necessary resources are available and releases them simultaneously. In contrast, our approach assumes that a job operation begins simultaneously across all assigned resources, although these resources may not be occupied for the same duration. This variant (which we will call “early resource release”) was first formally proposed in the scheduling literature more than twenty years ago, but to the best of our knowledge, it has not been empirically tested. Thus, to tackle this problem, we formulate a constraint programming (CP) model adopting a multi-mode resource-constrained project scheduling problem (MMRCPSP) representation. We tested our approach on 65 instances of the MRFJSSP where the precedence relationships between operations of a given job follow a linear order. We prove optimality in 44 instances with an average optimality gap of 9.37%. Additionally, we contributed eight new lower bounds for the same set of instances in the literature when considering the simultaneous occupation policy.