Approximation algorithms for precedence-constrained identical machine scheduling with rejection

DOI10.1007/S10878-016-0044-6MaRDI QIDQ1698078zbMATH OpenOpenAlexFDO

Authors Xianzhao Zhang, Dachuan Xu, Chenchen Wu, Donglei Du

Publication date 21 February 2018

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-016-0044-6

zbMATH Keywords

linear programmingapproximation algorithmschedulingrejectionrounding

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Scheduling with rejection subject to release times and precedence constraints
• New approximation algorithms for machine scheduling with rejection on single and parallel machine
• Preemptive scheduling with rejection
• Parallel-machine scheduling with release dates and rejection
• scientific article; zbMATH DE number 1670665

Cites work

• A Heuristic for a Scheduling Problem with Communication Delays
• A study of the cyclic scheduling problem on parallel processors
• A survey on offline scheduling with rejection
• Critical-Path Planning and Scheduling: Mathematical Basis
• Multiprocessor Scheduling with Rejection
• New complexity results on scheduling with small communication delays
• On-line uniform machine scheduling with rejection
• Online scheduling with rejection and withdrawal
• Parallel-machine scheduling with deteriorating jobs and rejection
• Preemptive multiprocessor scheduling with rejection
• Preemptive online scheduling with rejection of unit jobs on two uniformly related machines
• Preemptive scheduling with rejection
• Scheduling linear deteriorating jobs with rejection on a single machine
• Scheduling on parallel identical machines with job-rejection and position-dependent processing times
• Semi-online scheduling on two identical machines with rejection
• Techniques for scheduling with rejection
• Three, four, five, six, or the complexity of scheduling with communication delays

Cited in

(13)

• Minimizing maximum delivery completion time for order scheduling with rejection
• An approximation algorithm for the parallel-machine customer order scheduling with delivery time and submodular rejection penalties
• Scheduling to maximize the weighted number of on-time jobs on parallel machines with bounded job-rejection
• Single machine lot scheduling with optional job-rejection
• Minimizing total late work on a single machine with generalized due-dates
• Approximation algorithms for the multiprocessor scheduling with submodular penalties
• Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
• Single machine scheduling to minimize maximum earliness/tardiness cost with job rejection
• Algorithms for single machine scheduling problem with release dates and submodular penalties
• Parallel-batch scheduling with deterioration and rejection on a single machine
• Scheduling with rejection subject to release times and precedence constraints
• On-line single machine scheduling with release dates and submodular rejection penalties
• A subspace derivative-free projection method for convex constrained nonlinear equations

This page was built for publication: Approximation algorithms for precedence-constrained identical machine scheduling with rejection

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