Online scheduling of unit jobs on three machines with rejection: a tight result

DOI10.1016/j.ipl.2015.11.012zbMath1348.90255OpenAlexW2195770176MaRDI QIDQ903197

Hanan Zebedat-Haider, Leah Epstein

Publication date: 5 January 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.11.012

zbMATH Keywords

schedulingonline algorithmscompetitive ratio

Mathematics Subject Classification ID

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

Related Items

Flowshop scheduling with learning effect and job rejection, Single machine lot scheduling with optional job-rejection, Applying ``peeling onion approach for competitive analysis in online scheduling with rejection, Rent or buy problems with a fixed time horizon

Cites Work

• Semi-online scheduling on two identical machines with rejection
• Preemptive online scheduling with rejection of unit jobs on two uniformly related machines
• Optimal semi-online algorithm for scheduling with rejection on two uniform machines
• Online scheduling with rejection and reordering: exact algorithms for unit size jobs
• Online scheduling with rejection and withdrawal
• Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines
• On-line uniform machine scheduling with rejection
• Rent or buy problems with a fixed time horizon
• Scheduling with machine cost and rejection
• Scheduling with Deadlines and Loss Functions
• Multiprocessor Scheduling with Rejection
• Semi-online scheduling with decreasing job sizes
• Preemptive multiprocessor scheduling with rejection