Approximation algorithms for precedence-constrained identical machine scheduling with rejection
From MaRDI portal
Publication:1698078
DOI10.1007/s10878-016-0044-6zbMath1393.90062OpenAlexW2435530825MaRDI QIDQ1698078
Da-Chuan Xu, Chen-Chen Wu, Xianzhao Zhang, Dong-lei 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
Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)
Related Items
Minimizing maximum delivery completion time for order scheduling with rejection ⋮ Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties ⋮ Algorithms for single machine scheduling problem with release dates and submodular penalties ⋮ Scheduling to maximize the weighted number of on-time jobs on parallel machines with bounded job-rejection ⋮ Parallel-batch scheduling with deterioration and rejection on a single machine ⋮ On-line single machine scheduling with release dates and submodular rejection penalties ⋮ Single machine scheduling to minimize maximum earliness/tardiness cost with 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
Cites Work
- Semi-online scheduling on two identical machines with rejection
- A survey on offline scheduling with rejection
- Preemptive online scheduling with rejection of unit jobs on two uniformly related machines
- Scheduling on parallel identical machines with job-rejection and position-dependent processing times
- Online scheduling with rejection and withdrawal
- Parallel-machine scheduling with deteriorating jobs and rejection
- Scheduling linear deteriorating jobs with rejection on a single machine
- Three, four, five, six, or the complexity of scheduling with communication delays
- A study of the cyclic scheduling problem on parallel processors
- Preemptive scheduling with rejection
- On-line uniform machine scheduling with rejection
- New complexity results on scheduling with small communication delays
- Critical-Path Planning and Scheduling: Mathematical Basis
- A Heuristic for a Scheduling Problem with Communication Delays
- Techniques for scheduling with rejection
- Multiprocessor Scheduling with Rejection
- Preemptive multiprocessor scheduling with rejection