Single machine scheduling problems with uncertain parameters and the OWA criterion

DOI10.1007/S10951-015-0444-YzbMATH Open1341.90048arXiv1405.5371OpenAlexW1930081464WikidataQ59472686 ScholiaQ59472686MaRDI QIDQ282249FDOQ282249

Authors: Adam Kasperski, Paweł Zieliński 

Publication date: 12 May 2016

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

Abstract: In this paper a class of single machine scheduling problems is discussed. It is assumed that job parameters, such as processing times, due dates, or weights are uncertain and their values are specified in the form of a discrete scenario set. The Ordered Weighted Averaging (OWA) aggregation operator is used to choose an optimal schedule. The OWA operator generalizes traditional criteria in decision making under uncertainty, such as the maximum, average, median or Hurwicz criterion. It also allows us to extend the robust approach to scheduling by taking into account various attitudes of decision makers towards the risk. In this paper a general framework for solving single machine scheduling problems with the OWA criterion is proposed and some positive and negative computational results for two basic single machine scheduling problems are provided.

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

Recommendations

• Complexity of single machine scheduling problems under scenario-based uncertainty
• A single-machine scheduling problem with uncertainty in processing times and outsourcing costs
• An uncertain programming model for single machine scheduling problem with batch delivery
• scientific article; zbMATH DE number 1539056
• Single machine scheduling to minimize the number of late jobs under uncertainty.
• Single machine robust scheduling with budgeted uncertainty
• Uncertain single-machine scheduling with deterioration and learning effect
• Single machine scheduling under market uncertainty
• Optimality region for job permutation in single-machine scheduling with uncertain processing times
• Complexity of single machine, multi-criteria scheduling problems

zbMATH Keywords

robust optimizationschedulingsingle machineOWA criterion

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Title not available (Why is that?)
• On ordered weighted averaging aggregation operators in multicriteria decisionmaking
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Robust discrete optimization and its applications
• Improved polynomial algorithms for robust bottleneck problems with interval data
• Computing improved optimal solutions to max-min flexible constraint satisfaction problems
• On approximation algorithms for the minimum satisfiability problem
• Exact algorithms for OWA-optimization in multiobjective spanning tree problems
• On solving linear programs with the ordered weighted averaging objective.
• Approximating the min-max (regret) selecting items problem
• Single machine scheduling with scenarios
• A family of inequalities valid for the robust single machine scheduling polyhedron
• Complexity of minimizing the total flow time with interval data and minmax regret criterion
• Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion
• Scheduling algorithms
• Title not available (Why is that?)
• An algorithm for the single machine sequencing problem with precedence constraints
• Complexity of Scheduling under Precedence Constraints
• The Minimum Satisfiability Problem
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Title not available (Why is that?)
• Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
• Title not available (Why is that?)
• On the complexity of a class of combinatorial optimization problems with uncertainty
• Minimizing the number of late jobs on a single machine under due date uncertainty
• On the robust single machine scheduling problem
• Complexity of single machine scheduling problems under scenario-based uncertainty

Cited In (12)

• Investigating the recoverable robust single machine scheduling problem under interval uncertainty
• Total completion time scheduling under scenarios
• Application of the interpolation approach for approximating single-machine scheduling problem with an unknown objective function
• Risk-averse single machine scheduling: complexity and approximation
• A robust two-machine flow-shop scheduling model with scenario-dependent processing times
• Risk Averse Scheduling with Scenarios
• A state-of-the-art survey on multi-scenario scheduling
• A single-machine scheduling problem with uncertainty in processing times and outsourcing costs
• An approximation scheme for the bi-scenario sum of completion times trade-off problem
• Parameterized multi-scenario single-machine scheduling problems
• Bin packing problem with scenarios
• Minimizing worst-case and average-case makespan over scenarios

This page was built for publication: Single machine scheduling problems with uncertain parameters and the OWA criterion

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