Multiprocessor Scheduling with Rejection

DOI10.1137/S0895480196300522zbMATH Open0936.68012OpenAlexW2012228660MaRDI QIDQ4943705FDOQ4943705

Authors: Jiří Sgall, Yair Bartal, Stefano Leonardi, Alberto Marchetti-Spaccamela, L. Stougie 

Publication date: 19 March 2000

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480196300522

Recommendations

• scientific article; zbMATH DE number 871904
• On-line scheduling of unit time jobs with rejection on uniform machines
• Preemptive multiprocessor scheduling with rejection
• On-line scheduling with rejection on identical parallel machines
• On-line scheduling of unit time jobs with rejection: Minimizing the total completion time

zbMATH Keywords

approximation algorithmscompetitive analysison-line algorithmsmultiprocessor scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cited In (only showing first 100 items - show all)

• Penalty cost constrained identical parallel machine scheduling problem
• Preemptive online scheduling with rejection of unit jobs on two uniformly related machines
• Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines
• In-house production and outsourcing under different discount schemes on the total outsourcing cost
• Minimizing maximum delivery completion time for order scheduling with rejection
• New approximation algorithms for machine scheduling with rejection on single and parallel machine
• Online unit clustering: Variations on a theme
• A survey on offline scheduling with rejection
• A fast asymptotic approximation scheme for bin packing with rejection
• Approximation algorithms for supply chain planning and logistics problems with market choice
• Two-machine open-shop scheduling with rejection to minimize the makespan
• New results on two-machine flow-shop scheduling with rejection
• Parallel-machine scheduling with release dates and rejection
• The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan
• Bounded single-machine parallel-batch scheduling with release dates and rejection
• Single-machine scheduling under the job rejection constraint
• A PTAS for parallel batch scheduling with rejection and dynamic job arrivals
• Single machine scheduling with release dates and rejection
• Two-machine flow shop scheduling problem with an outsourcing option
• Title not available (Why is that?)
• Bicriteria order acceptance and scheduling with consideration of fill rate
• Approximation algorithms for precedence-constrained identical machine scheduling with rejection
• On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups
• Exact methods for order acceptance and scheduling on unrelated parallel machines
• On-line scheduling with rejection on identical parallel machines
• Online scheduling with rejection to minimize the total weighted completion time plus the total rejection cost on parallel machines
• An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme
• Online scheduling to minimize the total weighted completion time plus the rejection cost
• Preemptive multiprocessor scheduling with rejection
• Parameter learning online algorithm for multiprocessor scheduling with rejection
• Online scheduling in a parallel batch processing system to minimize makespan using restarts
• Scheduling with release times and rejection on two parallel machines
• Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine
• A semi-online algorithm for single machine scheduling with rejection
• An improved heuristic for parallel machine scheduling with rejection
• Online scheduling with machine cost and rejection
• Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty
• On-line scheduling of unit time jobs with rejection: Minimizing the total completion time
• Local search algorithms for \(k\)-median and \(k\)-facility location problems with linear penalties
• Bin packing problems with rejection penalties and their dual problems
• Scheduling with job rejection and nonsimultaneous machine available time on unrelated parallel machines
• Scheduling on parallel identical machines with job-rejection and position-dependent processing times
• Online scheduling of unit jobs on three machines with rejection: a tight result
• TWO-MACHINE FLOW SHOP SCHEDULING WITH INDIVIDUAL OPERATION'S REJECTION
• Scheduling with machine cost and rejection
• Rent or buy problems with a fixed time horizon
• 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
• An Optimal Incremental Algorithm for Minimizing Lateness with Rejection
• Scheduling a bounded parallel-batching machine with incompatible job families and rejection
• Online scheduling with rejection and reordering: exact algorithms for unit size jobs
• Single machine scheduling with rejection and generalized parameters
• Single machine scheduling with rejection to minimize the weighted makespan
• Bin packing with rejection revisited
• Minimizing the makespan on a single parallel batching machine
• Online scheduling with rejection and withdrawal
• Scheduling with rejection and a deteriorating maintenance activity on a single machine
• Single-machine scheduling with production and rejection costs to minimize the maximum earliness
• Single-machine scheduling and due date assignment with rejection and position-dependent processing times
• Multicriteria scheduling
• Single-machine scheduling with maintenance activities and rejection
• Parallel machine scheduling with restricted job rejection
• Order acceptance and scheduling with consideration of service level
• Order acceptance and scheduling with machine availability constraints
• Semi-online scheduling on two identical machines with rejection
• Optimal semi-online algorithm for scheduling with rejection on two uniform machines
• Improved approximation algorithms for parallel machine scheduling with release dates and job rejection
• On the mass COVID-19 vaccination scheduling problem
• Machine scheduling with restricted rejection: an application to task offloading in cloud-edge collaborative computing
• Parallel Machines Scheduling with Deteriorating Maintenance Activities and Job Rejection
• Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines
• Batch scheduling with proportional-linear deterioration and outsourcing
• A manifesto for the computational method
• An approximation algorithm for the parallel-machine customer order scheduling with delivery time and submodular rejection penalties
• Online file caching with rejection penalties
• The online \(k\)-server problem with rejection
• Scheduling with partial rejection
• Coordinated scheduling of the outsourcing, in-house production and distribution operations
• Vector scheduling with rejection on a single machine
• The constrained parallel-machine scheduling problem with divisible processing times and penalties
• Single Machine Scheduling with an Availability Constraint and Rejection
• Exact algorithms for solving the constrained parallel-machine scheduling problems with divisible processing times and penalties
• Dynamic scheduling with uncertain job types
• Outsourcing decisions in \(m\)-machine permutation flow shop scheduling problems with machine-dependent processing times
• Scheduling problems with rejection to minimize the \(k\)-th power of the makespan plus the total rejection cost
• Single machine scheduling with outsourcing under different fill rates or quantity discount rates
• Applying ``peeling onion approach for competitive analysis in online scheduling with rejection
• Order acceptance and scheduling with delivery under generalized parameters
• Fixed interval scheduling with third‐party machines
• Scheduling deteriorating jobs on a single machine with release times and rejection
• Scheduling problems with rejection to minimize the maximum flow time
• On variants of file caching
• The prize-collecting single machine scheduling with bounds and penalties
• An \(O(n^{2})\) algorithm for the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines
• A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection
• Single-machine scheduling with coupled task and rejection
• Approximation algorithms for the multiprocessor scheduling with submodular penalties
• Due-Window Assignment for a Single Machine Scheduling with Both Deterioration and Positional Effects
• Vector scheduling with rejection on two machines
• Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties

This page was built for publication: Multiprocessor Scheduling with Rejection

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