Penalty cost constrained identical parallel machine scheduling problem

DOI10.1016/j.tcs.2015.10.007zbMath1333.90048MaRDI QIDQ897945

Xuejie Zhang, Weidong Li, Zhibin Chen, Jianping Li

Publication date: 8 December 2015

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.10.007

zbMATH Keywords

scheduling; approximation algorithms; rejection penalty; polynomial time approximation scheme; fully polynomial time approximation scheme

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

68W25: Approximation algorithms

Related Items

Vector scheduling with rejection on two machines, Single Machine Scheduling with Outsourcing Under Different Fill Rates or Quantity Discount Rates, Algorithms for single machine scheduling problem with release dates and submodular penalties, Exact algorithms for solving the constrained parallel-machine scheduling problems with divisible processing times and penalties, Approximation scheme for single-machine rescheduling with job delay and rejection, On-line single machine scheduling with release dates and submodular rejection penalties, The constrained parallel-machine scheduling problem with divisible processing times and penalties, Order acceptance and scheduling with consideration of service level, Improved approximation algorithms for parallel machine scheduling with release dates and job rejection, Bicriteria order acceptance and scheduling with consideration of fill rate, Vector scheduling with rejection on a single machine, Approximation algorithms for the multiprocessor scheduling with submodular penalties, Parallel machine scheduling with restricted job rejection

Cites Work

• Unnamed Item
• A survey on offline scheduling with rejection
• A bicriteria approach to scheduling a single machine with job rejection and positional penalties
• The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan
• Scheduling linear deteriorating jobs with rejection on a single machine
• Single-machine scheduling under the job rejection constraint
• Bounded single-machine parallel-batch scheduling with release dates and rejection
• A PTAS for parallel batch scheduling with rejection and dynamic job arrivals
• Single machine scheduling with release dates and rejection
• Approximation schemes for scheduling on parallel machines
• An approximation algorithm for the generalized assignment problem
• Preemptive scheduling with rejection
• Minimizing the makespan on a single parallel batching machine
• Scheduling with rejection and non-identical job arrivals
• Improved approximation schemes for scheduling unrelated parallel machines
• Scheduling with Rejection to Minimize the Makespan
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Techniques for scheduling with rejection
• Multiprocessor Scheduling with Rejection
• Bounds for Certain Multiprocessing Anomalies
• Preemptive multiprocessor scheduling with rejection