Online scheduling with rejection and reordering: exact algorithms for unit size jobs

DOI10.1007/S10878-012-9593-5zbMATH Open1307.90069OpenAlexW1999669591MaRDI QIDQ489737FDOQ489737

Authors: Leah Epstein, Hanan Zebedat-Haider 

Publication date: 21 January 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9593-5

Recommendations

• Semi-online scheduling on two identical machines with rejection
• Online minimum makespan scheduling with a buffer
• Online minimum makespan scheduling with a buffer
• On-line scheduling of unit time jobs with rejection on uniform machines
• On-line scheduling with rejection on identical parallel machines

zbMATH Keywords

scheduling with rejectionreordering buffersunit job

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• On-line scheduling revisited
• Preemptive online scheduling with reordering
• Title not available (Why is that?)
• Bounds for Certain Multiprocessing Anomalies
• Multiprocessor Scheduling with Rejection
• Preemptive multiprocessor scheduling with rejection
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• New algorithms for an ancient scheduling problem.
• A simple semi on-line algorithm for \(\mathrm{P}2//C_{\max}\) with a buffer
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• The Santa Claus problem
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
• On-line machine covering
• Approximation schemes for scheduling on parallel machines
• Semi on-line algorithms for the partition problem
• On-line uniform machine scheduling with rejection
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Semi-online algorithms for parallel machine scheduling problems
• Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines
• Online minimum makespan scheduling with a buffer
• Better Bounds for Online Scheduling
• Approximation and Online Algorithms
• New lower and upper bounds for on-line scheduling
• The Power of Reordering for Online Minimum Makespan Scheduling
• A Better Algorithm for an Ancient Scheduling Problem
• Title not available (Why is that?)
• Tight bounds for bandwidth allocation on two links
• Title not available (Why is that?)
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines
• Ancient and new algorithms for load balancing in the \(\ell_p\) norm
• Online scheduling with a buffer on related machines
• Max-min online allocations with a reordering buffer
• Online scheduling with rejection and withdrawal

Cited In (6)

• Erratum to: ``A survey on offline scheduling with rejection
• Single machine lot scheduling with optional job-rejection
• Applying ``peeling onion approach for competitive analysis in online scheduling with rejection
• Online scheduling of unit jobs on three machines with rejection: a tight result
• The Power of Reordering for Online Minimum Makespan Scheduling
• Rent or buy problems with a fixed time horizon

This page was built for publication: Online scheduling with rejection and reordering: exact algorithms for unit size jobs

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