Wasserstein distance-based distributionally robust parallel-machine scheduling *

Recent research on distributionally robust (DR) machine scheduling has used a variety of approaches to describe the region of ambiguity of uncertain processing times by imposing constraints on the moments of the probability distributions. One approach that has been employed outside machine scheduling research is the use of statistical metrics to define a distance function between two probability distributions. Adopting such an approach, we study Wasserstein distance-based DR parallel-machine scheduling, where the ambiguity set is defined as a Wasserstein ball around an empirical distribution of uncertain processing times corresponding to finitely many samples. The objective is to minimize a DR objective that concerns the worst-case expected total completion time-related cost over all the distributions arising from the Wasserstein ambiguity set, subject to DR chance constraints on the machine service capacity. We show that the problem can be equivalently re-formulated as a mixed-integer linear program (MILP), which has a more simplified formulation when the bounded support set reduces to a left bounded one. To solve the resulting model, we develop a tailored branch-and-Benders-cut algorithm incorporating some enhancement strategies, including in-out Benders cut generation, aggregated sample group cut generation, and two-stage Benders cut generation, which significantly outperforms the CPLEX solver. Experiment results on comparing our model with the deterministic and stochastic counterparts and the model with first-order moment ambiguity set illustrate the benefits of considering distributional ambiguity and Wasserstein ambiguity set.

Automated summary

Recent research on distributionally robust (DR) machine scheduling has explored different approaches to deal with uncertain processing times. One approach is to use statistical metrics to measure the distance between probability distributions. In this study, we focus on Wasserstein distance-based DR parallel-machine scheduling, where we minimize the worst-case expected total completion time-related cost over all distributions within a Wasserstein ambiguity set.