Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines

DOI10.1007/s00607-005-0130-6zbMath1081.90028OpenAlexW1974058801MaRDI QIDQ817020

György Dósa, Yong He

Publication date: 2 March 2006

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-005-0130-6

zbMATH Keywords

competitive analysisSchedulingon-line algorithmspreemptionrejection

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (15)

Scheduling with machine cost and rejection ⋮ Scheduling with partial rejection ⋮ Semi-online scheduling on two identical machines with rejection ⋮ Preemptive online scheduling with rejection of unit jobs on two uniformly related machines ⋮ Graph multi-coloring for a job scheduling application ⋮ Optimal semi-online algorithm for scheduling with rejection on two uniform machines ⋮ Model and metaheuristics for a scheduling problem integrating procurement, sale and distribution decisions ⋮ Online scheduling of unit jobs on three machines with rejection: a tight result ⋮ Online scheduling with rejection and withdrawal ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Semi-online scheduling on two uniform machines with the known largest size ⋮ Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling ⋮ TWO-MACHINE FLOW SHOP SCHEDULING WITH INDIVIDUAL OPERATION'S REJECTION ⋮ Semi-online scheduling on two uniform processors ⋮ Applying ``peeling onion approach for competitive analysis in online scheduling with rejection

Cites Work

• Preemptive on-line scheduling for two uniform processors
• Preemptive scheduling with rejection
• Online randomized multiprocessor scheduling
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Multiprocessor Scheduling with Rejection
• Randomized on-line scheduling on two uniform machines
• Preemptive multiprocessor scheduling with rejection

This page was built for publication: Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines