On-line uniform machine scheduling with rejection

MaRDI QIDQ1583671zbMATH OpenFDO

Authors R. Smith

Publication date 30 October 2000

Published in Computing (Search for Journal in Brave)

zbMATH Keywords

competitive ratioworst-case analysison-line schedulinguniform machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• A special case of on-line scheduling on two uniformly machines with rejection
• Uniform machine scheduling with arrival time and rejection
• On-line scheduling of unit time jobs with rejection on uniform machines
• Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines
• On-line scheduling with rejection on identical parallel machines

Cited in

(18)

• A PTAS for parallel batch scheduling with rejection and dynamic job arrivals
• Graph multi-coloring for a job scheduling application
• Scheduling with machine cost and rejection
• Online scheduling of unit jobs on three machines with rejection: a tight result
• Uniform machine scheduling with arrival time and rejection
• Preemptive online scheduling with rejection of unit jobs on two uniformly related machines
• Scheduling with rejection and non-identical job arrivals
• Online scheduling with rejection and reordering: exact algorithms for unit size jobs
• Scheduling deteriorating jobs with rejection on dominant machines
• Semi-online scheduling on two identical machines with rejection
• Online scheduling with rejection and withdrawal
• Scheduling linear deteriorating jobs with rejection on a single machine
• A special case of on-line scheduling on two uniformly machines with rejection
• Approximation algorithms for precedence-constrained identical machine scheduling with rejection
• 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
• Optimal semi-online algorithm for scheduling with rejection on two uniform machines
• Exact algorithms for solving the constrained parallel-machine scheduling problems with divisible processing times and penalties

This page was built for publication: On-line uniform machine scheduling with rejection

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