Penalty cost constrained identical parallel machine scheduling problem

DOI10.1016/j.tcs.2015.10.007zbMath1333.90048OpenAlexW1854554296MaRDI 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

schedulingapproximation algorithmsrejection penaltypolynomial time approximation schemefully polynomial time approximation scheme

Mathematics Subject Classification ID

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

Related Items (13)

Vector scheduling with rejection on two machines ⋮ Parallel machine scheduling with restricted job rejection ⋮ Bicriteria order acceptance and scheduling with consideration of fill rate ⋮ 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 ⋮ Vector scheduling with rejection on a single machine ⋮ Improved approximation algorithms for parallel machine scheduling with release dates and job rejection ⋮ Order acceptance and scheduling with consideration of service level ⋮ Approximation algorithms for the multiprocessor scheduling with submodular penalties ⋮ Single Machine Scheduling with Outsourcing Under Different Fill Rates or Quantity Discount Rates

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

This page was built for publication: Penalty cost constrained identical parallel machine scheduling problem