“Exact Algorithms for Distributionally β-Robust Machine Scheduling with Uncertain Processing Times”, a collaboration of Zhang Yuli, a faculty at the School of Management and Economics, and Prof. Shen Zuojun from the University of California at Berkeley and Professor Song Shiji from Tsinghua University, was recently published in the INFORMS Journal on Computing. Zhang Yuli is the first author of this article.
Aiming at the scheduling problem in uncertain environment, this paper proposes a stochastic robust optimization model based on β-robust criterion, and proposes an efficient and accurate algorithm for solving such nonlinear discrete optimization models - Parametric Search. This method only needs to search the one-dimensional parameter space and solve a small number of linear optimization problems to obtain the optimal solution of the original problem, which avoids the difficulty of branching and delimiting in the multi-dimensional discrete space. In the sense of expectation, the method has the computational complexity of polynomial time. Computational experiments show that this method can improve the efficiency of existing algorithms by several orders of magnitude.
