4.7 Article

Wasserstein distance-based distributionally robust parallel-machine scheduling *

出版社

PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.omega.2023.102896

关键词

Parallel-machine scheduling; Distributionally robust optimization; Wasserstein metric; Benders decomposition algorithm

向作者/读者索取更多资源

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.
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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.7
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据