Single-machine scheduling with release times, deadlines, setup times, and rejection

DOI10.1016/j.ejor.2020.09.042zbMath1487.90288OpenAlexW3089826203MaRDI QIDQ2030718

Lei He, Mathijs de Weerdt, Robert Baart

Publication date: 7 June 2021

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2020.09.042

zbMATH Keywords

schedulingdynamic programmingfixed-parameter tractabilityorder acceptancedecision diagrams

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

Due-window assignment scheduling with past-sequence-dependent setup times ⋮ A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ Decision Diagrams for Discrete Optimization: A Survey of Recent Advances ⋮ Equitable scheduling on a single machine ⋮ Single machine scheduling with release dates: a distributionally robust approach ⋮ Single machine scheduling to minimize maximum earliness/tardiness cost with job rejection ⋮ A matheuristic for the generalized order acceptance and scheduling problem ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems

Uses Software

• OR-Library

Cites Work

• Orienteering problem: a survey of recent variants, solution approaches and applications
• Fundamentals of parameterized complexity
• Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment
• A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites
• Scheduling and fixed-parameter tractability
• Single machine scheduling with release dates and rejection
• New classes of efficiently solvable generalized traveling salesman problems
• Scheduling equal-length jobs on identical parallel machines
• Multi-phase algorithms for throughput maximization for real-time scheduling
• Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times
• An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time
• Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times
• Hybrid optimization methods for time-dependent sequencing problems
• Large multiple neighborhood search for the clustered vehicle-routing problem
• On the approximability of an interval scheduling problem
• On the parametric complexity of schedules to minimize tardy tasks.
• The team orienteering problem with time windows: an LP-based granular variable neighborhood search
• Multi-machine scheduling lower bounds using decision diagrams
• Lower bounds for uniform machine scheduling using decision diagrams
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• Discrete Optimization with Decision Diagrams
• Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
• Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
• Strip Graphs: Recognition and Scheduling
• Interval scheduling: A survey
• Multivalued Decision Diagrams for Sequencing Problems
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Scheduling
• Unnamed Item
• Unnamed Item