Risk-averse single machine scheduling: complexity and approximation

DOI10.1007/S10951-019-00599-6MaRDI QIDQ2286434zbMATH OpenOpenAlexFDO

Authors Adam Kasperski, Paweł Zieliński

Publication date 22 January 2020

Published in Journal of Scheduling (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1712.03371

zbMATH Keywords

approximation algorithmscomputational complexityconditional value-at-riskrobust schedulingsingle machinevalue-at-risk

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: In this paper a class of single machine scheduling problems is considered. It is assumed that job processing times and due dates can be uncertain and they are specified in the form of discrete scenario set. A probability distribution in the scenario set is known. In order to choose a schedule some risk criteria such as the value at risk (VaR) an conditional value at risk (CVaR) are used. Various positive and negative complexity results are provided for basic single machine scheduling problems. In this paper new complexity results are shown and some known complexity results are strengthen.

Recommendations

• Risk averse scheduling with scenarios
• Complexity of single machine scheduling problems under scenario-based uncertainty
• Minimizing value-at-risk in single-machine scheduling
• Algorithms and complexity analysis for robust single-machine scheduling problems
• Robust single machine scheduling problem with weighted number of late jobs criterion

Cites work

• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• A Probabilistic Model for Minmax Regret in Combinatorial Optimization
• An algorithm for the single machine sequencing problem with precedence constraints
• Approximating the min-max (regret) selecting items problem
• Approximation in stochastic scheduling
• Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion
• Complexity of minimizing the total flow time with interval data and minmax regret criterion
• Complexity of single machine scheduling problems under scenario-based uncertainty
• Complexity results for a class of min-max problems with robust optimization applications
• Distributionally robust single machine scheduling with risk aversion
• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1979522 (Why is no real title available?)
• Lawler's minmax cost algorithm: optimality conditions and uncertainty
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Minimizing conditional-value-at-risk for stochastic scheduling problems
• Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion
• Minimizing the number of late jobs on a single machine under due date uncertainty
• Minimizing Total Tardiness on One Machine is NP-Hard
• Minimizing value-at-risk in single-machine scheduling
• Minmax regret solutions for minimax optimization problems with uncertainty
• On ordered weighted averaging aggregation operators in multicriteria decisionmaking
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Reducibility among combinatorial problems
• Robust decisions under risk for imprecise probabilities
• Robust discrete optimization and its applications
• Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production
• Scheduling
• Scheduling algorithms
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds
• Single machine scheduling problems with uncertain parameters and the OWA criterion
• Single machine scheduling with scenarios
• Some remarks on the value-at-risk and the conditional value-at-risk
• Stochastic Machine Scheduling with Precedence Constraints
• The Minimum Satisfiability Problem
• Unrelated machine scheduling with stochastic processing times

Cited in

(13)

• An adversarial model for scheduling with testing
• Two-stage combinatorial optimization problems under risk
• Complexity results for common due date scheduling problems with interval data and minmax regret criterion
• Aversion scheduling in the presence of risky jobs
• The distributionally robust machine scheduling problem with job selection and sequence-dependent setup times
• Risk averse scheduling with scenarios
• Minimizing value-at-risk in single-machine scheduling
• Min–max version of single-machine scheduling with generalized due dates under scenario-based uncertainty
• A stochastic bi-objective project scheduling model under failure of activities
• Robust scheduling in a two-machine re-entrant flow shop to minimise the value-at-risk of the makespan: branch-and-bound and heuristic algorithms based on Markovian activity networks and phase-type distributions
• Recoverable robust single machine scheduling with polyhedral uncertainty
• Investigating the recoverable robust single machine scheduling problem under interval uncertainty
• Complexity of single machine scheduling problems under scenario-based uncertainty

This page was built for publication: Risk-averse single machine scheduling: complexity and approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2286434)