Extending the SI Decomposition to Continuous-Time Two-Stage Scheduling Problems

Abstract

[EN] Scheduling often involves making decisions in presence of uncertainty, which governs the pricing of raw materials, energy, resource availability, demands, etc. A common approach to incorporate uncertainty in the decision-making process is using two-stage stochastic formulations. Unfortunately, the mathematical complexity of the resulting problems grows exponentially with the number of uncertainty scenarios, which is further complicated by the presence of binary variables The authors have recently proposed a method using the so-called Similarity Index for discrete-time two-stage scheduling problems that enable scenario-based decomposition. This paper extends this method for scheduling problems formulated on a continuous-time basis. The fundamental idea is to use the Similarity Index to meet non-anticipation in the binary variables and Progressive Hedging on the continuous ones. The proposal is tested on a literature case study that consists of a multiproduct plant with a single processing unit. The combined SI-PH decomposition managed to solve the problem much faster than its monolithic counterpart.