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

DOI10.1007/978-3-031-16081-3_4MaRDI QIDQ6167004zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

dynamic programmingrejectionreschedulingfully polynomial-time approximation scheme

Mathematics Subject Classification ID

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

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

Cites work

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

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)