On-line single machine scheduling with release dates and submodular rejection penalties

DOI10.1007/978-3-031-16081-3_6MaRDI QIDQ6167007zbMATH OpenOpenAlexFDO

Authors Xiaofei Liu, Yaoyu Zhu, Weidong Li, Lei Ma

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_6

zbMATH Keywords

competitive ratioon-line algorithmon-line schedulingsubmodular penalties

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Algorithms for single machine scheduling problem with release dates and submodular penalties
• Single machine scheduling with release dates and rejection
• Scheduling on single machine and identical machines with rejection
• Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
• On-line scheduling of unit time jobs with rejection: Minimizing the total completion time

Cites work

• A push-relabel framework for submodular function minimization and applications to parametric optimization
• An improved heuristic for parallel machine scheduling with rejection
• Approximation algorithms for precedence-constrained identical machine scheduling with rejection
• Approximation algorithms for the multiprocessor scheduling with submodular penalties
• Multiprocessor Scheduling with Rejection
• On-line scheduling of unit time jobs with rejection: Minimizing the total completion time
• Penalty cost constrained identical parallel machine scheduling problem
• Preemptive multiprocessor scheduling with rejection
• Single machine scheduling with release dates and rejection
• Vector scheduling with rejection on a single machine
• Vector scheduling with rejection on two machines

Cited in

(2)

• Asymptotic Performance Ratio of an Online Algorithm for the Single Machine Scheduling With Release Dates
• Online scheduling on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost

This page was built for publication: On-line single machine scheduling with release dates and submodular rejection penalties

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