期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 299, 期 2, 页码 420-431出版社
ELSEVIER
DOI: 10.1016/j.ejor.2021.08.034
关键词
Scheduling; Target -based; Distributionally robust optimization; Risk measure; CVaR
This study addresses the traditional single-machine scheduling problem with uncertain processing time. It proposes a distributionally robust optimization model and introduces target-based risk measures to handle excess value beyond the target level. The numerical analysis shows that these methods outperform the traditional distributionally beta-robust scheduling approach in terms of excess value.
In the traditional single-machine scheduling problem with uncertain processing time, distributionally robust optimization models are established in situations where the distribution information is not known exactly. One well-studied robust optimization method used in scheduling is the distributionally beta-robust optimization technique. The goal of this technique is to maximize the probability that the total flow time of the job sequence does not exceed the predetermined target level T . However, it is possible that the excess value of the total flow time beyond the target T may be incredibly large, and therefore it is necessary to consider the optimized excess value. To address this concern, two new target-based risk measures are introduced. First, target-oriented CVaR, the worst-case conditional value-at-risk (CVaR) is used to minimize the excess value beyond T , which accounts for both the excess probability and the excess value. Second, the essential riskiness index (ERI) is extended to a multi-piecewise linear function for excess value control in single-machine scheduling problems. To obtain a tractable closed-form solutions of the risk measures, the CVaR-based measure is decomposed into an assignment problem and a second-order cone programming problem, and the ERI is converted to its equivalent semi-definite programming and second-order cone counterparts. To efficiently solve the risk measures for single-machine scheduling, a bisection search algorithm and a Benders decomposition algorithm are designed. In the numerical analysis, the excess value and the probability are investigated with respect to two distributions, namely the two-point distribution and the truncated normal distribution. The experiment design also considers different ranges of expectation and variance, tolerance levels, and problem scales. It is discovered that the CVaR and ERI-based methods are always better than the distributionally beta-robust scheduling approach in terms of excess value.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据