Target-based distributionally robust optimization for single machine scheduling

Zhi Pei, Haimin Lu, Qingwei Jin and Lianmin Zhang

European Journal of Operational Research, 2022, vol. 299, issue 2, 420-431

Abstract: 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 β-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 β-robust scheduling approach in terms of excess value.

Keywords: Scheduling; Target-based; Distributionally robust optimization; Risk measure; CVaR (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721007244
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:299:y:2022:i:2:p:420-431

DOI: 10.1016/j.ejor.2021.08.034

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().