Evaluation of the quantiles and superquantiles of the makespan in interval valued activity networks. (March 2023)

• Record Type: Journal Article
• Authors: Meloni, Carlo; Pranzo, Marco
• Is Part Of: Computers & operations research. Volume 151(2023)
• Publication Date: 2023-03
• Subjects: Quantiles -- Superquantiles -- VaR -- Expected shortfall -- CVaR -- Scheduling -- Makespan -- Uncertainty -- Activity networks; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.106098
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: This paper deals with the evaluation of quantile-based risk measures for the makespan in scheduling problems represented as temporal networks with uncertainties on the activity durations. More specifically, for each activity only the interval for its possible duration values is known in advance to both the scheduler and the risk analyst. Given a feasible schedule, we calculate the quantiles and the superquantiles of the makespan which are of interest as risk indicators in various applications. To this aim we propose and test a set of novel algorithms to determine rapid and accurate numerical estimations based on the calculation of theoretically proven lower and upper bounds. An extensive experimental campaign computationally shows the validity of the proposed methods, and allows to highlight their performances through the comparison with respect to the state-of-the-art algorithms. Highlights: Interval-valued activity networks to represent solutions in complex scheduling. New methods to evaluate the risk due to uncertainties associated to a schedule. An algorithmic method to evaluate quantiles and superquantiles of the makespan. Accurate and rapid methods for theoretically proven bounds of the risk measures. Experimental test of the applicability and the effectiveness of the method.