Preemptive multiprocessor scheduling with rejection

DOI10.1016/S0304-3975(00)00288-7zbMath0992.68072MaRDI QIDQ5958131

Steven S. Seiden

Publication date: 3 March 2002

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

zbMATH Keywords

schedulingonline algorithmsanalysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Two-machine open-shop scheduling with rejection to minimize the makespan ⋮ New results on two-machine flow-shop scheduling with rejection ⋮ New approximation algorithms for machine scheduling with rejection on single and parallel machine ⋮ Online scheduling with rejection to minimize the total weighted completion time plus the total rejection cost on parallel machines ⋮ SCHEDULING DETERIORATING JOBS ON A SINGLE MACHINE WITH RELEASE TIMES AND REJECTION ⋮ Parallel-machine scheduling with release dates and rejection ⋮ An improved heuristic for parallel machine scheduling with rejection ⋮ Scheduling with machine cost and rejection ⋮ Separating online scheduling algorithms with the relative worst order ratio ⋮ Scheduling with partial rejection ⋮ A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection ⋮ On-line scheduling with rejection on identical parallel machines ⋮ Preemptive online scheduling with rejection of unit jobs on two uniformly related machines ⋮ Graph multi-coloring for a job scheduling application ⋮ Scheduling problems with rejection to minimize the maximum flow time ⋮ Penalty cost constrained identical parallel machine scheduling problem ⋮ Scheduling with rejection and non-identical job arrivals ⋮ Permutation flow shop scheduling with order acceptance and weighted tardiness ⋮ On-line single machine scheduling with release dates and submodular rejection penalties ⋮ Approximation algorithms for precedence-constrained identical machine scheduling with rejection ⋮ 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 on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost ⋮ Online scheduling with rejection and withdrawal ⋮ The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan ⋮ Preemptive scheduling on a small number of hierarchical machines ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ An Optimal Incremental Algorithm for Minimizing Lateness with Rejection ⋮ Online scheduling with rejection and reordering: exact algorithms for unit size jobs ⋮ Online scheduling with machine cost and rejection ⋮ Non-permutation flow shop scheduling with order acceptance and weighted tardiness ⋮ On Variants of File Caching ⋮ Order acceptance and scheduling with consideration of service level ⋮ Scheduling linear deteriorating jobs with rejection on a single machine ⋮ TWO-MACHINE FLOW SHOP SCHEDULING WITH INDIVIDUAL OPERATION'S REJECTION ⋮ Single-machine scheduling under the job rejection constraint ⋮ Order acceptance and scheduling with machine availability constraints ⋮ On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups ⋮ Parallel-machine scheduling with deteriorating jobs and rejection ⋮ Minimizing the makespan on a single parallel batching machine ⋮ Bin packing problems with rejection penalties and their dual problems ⋮ Applying ``peeling onion approach for competitive analysis in online scheduling with rejection ⋮ Bounded single-machine parallel-batch scheduling with release dates and rejection ⋮ Scheduling deteriorating jobs with rejection on dominant machines ⋮ 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 ⋮ Two-agent scheduling with rejection on a single machine ⋮ The online \(k\)-server problem with rejection ⋮ Rent or buy problems with a fixed time horizon ⋮ Online file caching with rejection penalties ⋮ Optimal preemptive semi-online scheduling to minimize makespan on two related machines ⋮ On-line scheduling of unit time jobs with rejection: Minimizing the total completion time ⋮ Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines

Cites Work

• Unnamed Item
• A lower bound for randomized on-line multiprocessor scheduling
• New algorithms for an ancient scheduling problem.
• Competitive snoopy caching
• A better lower bound for on-line scheduling
• A lower bound for randomized on-line scheduling algorithms
• New lower and upper bounds for on-line scheduling
• An optimal algorithm for preemptive on-line scheduling
• Scheduling with Deadlines and Loss Functions
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Better Bounds for Online Scheduling
• Techniques for scheduling with rejection
• A Better Algorithm for an Ancient Scheduling Problem
• Multiprocessor Scheduling with Rejection
• Randomized algorithms for that ancient scheduling problem