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

DOI10.1007/978-3-031-16081-3_6zbMATH Open1526.90017OpenAlexW4296167530MaRDI QIDQ6167007FDOQ6167007

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

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

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)

Cites Work

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