New approximation algorithms for machine scheduling with rejection on single and parallel machine

DOI10.1007/S10878-020-00642-9zbMath1468.90052OpenAlexW3082571963MaRDI QIDQ830930

Peihai Liu, Xi-wen Lu

Publication date: 10 May 2021

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

Full work available at URL: https://doi.org/10.1007/s10878-020-00642-9

zbMATH Keywords

schedulingapproximation algorithmworst-case ratiorejectionrelease date

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (8)

Single machine scheduling with rejection and generalized parameters ⋮ Single machine scheduling with rejection to minimize the weighted makespan ⋮ Scheduling problems with rejection to minimize the \(k\)-th power of the makespan plus the total rejection cost ⋮ Machine scheduling with job rejection and Dejong's learning effect ⋮ Parallel-batch scheduling with rejection: structural properties and approximation algorithms ⋮ Single machine scheduling with rejection to minimize the \(k\)-th power of the makespan ⋮ Order acceptance and scheduling with delivery under generalized parameters ⋮ Single machine scheduling to minimize maximum earliness/tardiness cost with job rejection

Cites Work

• Improved algorithms for single machine scheduling with release dates and rejections
• Faster algorithms for single machine scheduling with release dates and rejection
• Parallel-machine scheduling with release dates and rejection
• A survey on offline scheduling with rejection
• Improved approximation algorithms for parallel machine scheduling with release dates and job rejection
• Scheduling linear deteriorating jobs with rejection on a single machine
• Single machine scheduling with release dates and rejection
• Preemptive scheduling with rejection
• On-line scheduling of unit time jobs with rejection: Minimizing the total completion time
• Scheduling with release times and rejection on two parallel machines
• Online scheduling on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost
• An improved heuristic for parallel machine scheduling with rejection
• Revised Delivery-Time Quotation in Scheduling with Tardiness Penalties
• Techniques for scheduling with rejection
• Multiprocessor Scheduling with Rejection
• Theory and Applications of Models of Computation
• Algorithms and Data Structures
• Preemptive multiprocessor scheduling with rejection

This page was built for publication: New approximation algorithms for machine scheduling with rejection on single and parallel machine