On-line scheduling of unit time jobs with rejection: Minimizing the total completion time

DOI10.1016/S0167-6377(02)00160-8zbMath1013.90063MaRDI QIDQ1870022

Leah Epstein, John Noga, Gerhard J. Woeginger

Publication date: 4 May 2003

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

scheduling; competitive analysis; worst-case bounds; on-line algorithm

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

Related Items

TWO-MACHINE FLOW SHOP SCHEDULING WITH INDIVIDUAL OPERATION'S REJECTION, Two-machine open-shop scheduling with rejection to minimize the makespan, New results on two-machine flow-shop scheduling with rejection, Online scheduling with rejection to minimize the total weighted completion time plus the total rejection cost on parallel machines, Parallel-machine scheduling with release dates and rejection, Permutation flow shop scheduling with order acceptance and weighted tardiness, Scheduling on parallel identical machines with job-rejection and position-dependent processing times, Order acceptance and scheduling with consideration of service level, Parallel-machine scheduling with deteriorating jobs and rejection, Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment, Optimally competitive list batching, On-line scheduling with rejection on identical parallel machines, The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan, Scheduling linear deteriorating jobs with rejection on a single machine, Single-machine scheduling under the job rejection constraint, Bounded single-machine parallel-batch scheduling with release dates and rejection, A PTAS for parallel batch scheduling with rejection and dynamic job arrivals, On-line scheduling of unit time jobs with rejection on uniform machines, Single machine scheduling with release dates and rejection, Scheduling problems with rejection to minimize the maximum flow time, Order acceptance and scheduling with machine availability constraints, Online file caching with rejection penalties, Scheduling with rejection and non-identical job arrivals, Online scheduling on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost, Bin packing problems with rejection penalties and their dual problems, An improved heuristic for parallel machine scheduling with rejection, On Variants of File Caching, An Optimal Incremental Algorithm for Minimizing Lateness with Rejection

Cites Work

• Unnamed Item
• Unnamed Item
• Online algorithms. The state of the art
• Techniques for scheduling with rejection
• Multiprocessor Scheduling with Rejection
• Preemptive multiprocessor scheduling with rejection