A new cumulative scheduling model using effective continuous-time formulation and dominance rules for optimality

The cumulative scheduling problem has been traditionally represented using a discrete time formulation, incorporating the variable resource consumption of each job as decision variables. In our research, we aim to provide a more accessible approach to formulating a specific configuration of this problem. We establish an optimality condition for resource allocation, which enables us to eliminate these decision variables and develop a simpler, more concise, and efficient continuous-time formulation. Furthermore, we introduce two optimality-based dominance rules for the continuous-time model, which are strengthened by valid inequalities. Computational experiments reveal that the continuous-time formulation significantly outperforms existing state-of-the-art approaches. Additionally, the optimality-driven dominance rules and inequalities contribute to enhancing the performance of the continuous-time model, especially in large-scale instances.