Online scheduling with rejection and withdrawal

DOI10.1016/J.TCS.2011.08.031MaRDI QIDQ650898zbMATHOpenAlexFDO

Authors Leah Epstein, Hanan Zebedat-Haider

Publication date 7 December 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.08.031

zbMATH Keywords

online algorithmsschedulingreassignment

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Online scheduling to minimize the total weighted completion time plus the rejection cost
• Online scheduling with rejection to minimize the total weighted completion time plus the total rejection cost on parallel machines
• Scheduling with rejection and non-identical job arrivals
• Online scheduling with machine cost and rejection
• A survey on job scheduling with rejection

Cites work

• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• scientific article; zbMATH DE number 1445351 (Why is no real title available?)
• A Better Algorithm for an Ancient Scheduling Problem
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Better Bounds for Online Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Multiprocessor Scheduling with Rejection
• New algorithms for an ancient scheduling problem.
• New lower and upper bounds for on-line scheduling
• On-Line Load Balancing for Related Machines
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• On-line scheduling revisited
• On-line uniform machine scheduling with rejection
• Online algorithms. The state of the art
• Online scheduling on two uniform machines to minimize the makespan
• Online scheduling with rearrangement on two related machines
• Online scheduling with reassignment
• Online scheduling with reassignment on two uniform machines
• Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines
• Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines
• Preemptive multiprocessor scheduling with rejection
• Randomized on-line scheduling on two uniform machines
• The Santa Claus problem
• Tight bounds for bandwidth allocation on two links

Cited in

(8)

• Rent or buy problems with a fixed time horizon
• Online scheduling of unit jobs on three machines with rejection: a tight result
• TWO-MACHINE FLOW SHOP SCHEDULING WITH INDIVIDUAL OPERATION'S REJECTION
• Online scheduling with reassignment
• Online scheduling with rejection and reordering: exact algorithms for unit size jobs
• Approximation algorithms for precedence-constrained identical machine scheduling with rejection
• A survey on offline scheduling with rejection
• Leasing with uncertainty

This page was built for publication: Online scheduling with rejection and withdrawal

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