Approximation scheme for single-machine rescheduling with job delay and rejection

DOI10.1007/978-3-031-16081-3_4zbMATH Open1526.90018OpenAlexW4296168269MaRDI QIDQ6167004FDOQ6167004

Authors: Ruiqing Sun, Xiaofei Liu 

Publication date: 7 July 2023

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-16081-3_4

Recommendations

• Approximation scheme for rescheduling on a single machine with job delay and rejection
• Single machine scheduling with rejection to minimize the weighted makespan
• A tardiness-augmented approximation scheme for rejection-allowed multiprocessor rescheduling
• Single machine scheduling with release dates and rejection
• Single-machine scheduling under the job rejection constraint

zbMATH Keywords

dynamic programmingrejectionreschedulingfully polynomial-time approximation scheme

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Cites Work

• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Rescheduling for job unavailability
• Rescheduling on identical parallel machines with machine disruptions to minimize total completion time
• Matchup Scheduling with Multiple Resources, Release Dates and Disruptions
• Rescheduling for machine disruption to minimize makespan and maximum lateness
• Rescheduling due to machine disruption to minimize the total weighted completion time
• Approximation schemes for scheduling on parallel machines
• Penalty cost constrained identical parallel machine scheduling problem
• Cost allocation in rescheduling with machine unavailable period
• A unified framework for designing EPTAS for load balancing on parallel machines
• Semi-online algorithms for hierarchical scheduling on three parallel machines with a buffer size of 1
• Vector scheduling with rejection on a single machine
• Two approximation schemes for scheduling on parallel machines under a grade of service provision
• Approximation scheme for rescheduling on a single machine with job delay and rejection

Cited In (1)

• On the parameterized tractability of single machine scheduling with rejection to minimize the weighted makespan

This page was built for publication: Approximation scheme for single-machine rescheduling with job delay and rejection

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