A PTAS for parallel batch scheduling with rejection and dynamic job arrivals

DOI10.1016/J.TCS.2009.04.006zbMath1175.68076OpenAlexW2087096734MaRDI QIDQ1029345

Zhigang Cao, Xiao-guang Yang

Publication date: 10 July 2009

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

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

zbMATH Keywords

schedulingPTASrejectionparallel batchdynamic job arrivals

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (18)

Scheduling a single machine with parallel batching to minimize makespan and total rejection cost ⋮ Continuous-time independent edge-Markovian random graph process ⋮ The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost ⋮ Two-agent parallel-machine scheduling with rejection ⋮ Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine ⋮ A survey on offline scheduling with rejection ⋮ Graph multi-coloring for a job scheduling application ⋮ Parallel-batch scheduling with rejection: structural properties and approximation algorithms ⋮ Penalty cost constrained identical parallel machine scheduling problem ⋮ Model and metaheuristics for a scheduling problem integrating procurement, sale and distribution decisions ⋮ A bicriteria approach to scheduling a single machine with job rejection and positional penalties ⋮ Single-machine scheduling and due date assignment with rejection and position-dependent processing times ⋮ Scheduling on parallel identical machines with job-rejection and position-dependent processing times ⋮ Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection ⋮ Scheduling a bounded parallel-batching machine with incompatible job families and rejection ⋮ Batch scheduling with proportional-linear deterioration and outsourcing ⋮ Two-machine flow-shop scheduling with rejection ⋮ Multipurpose machine scheduling with rejection and identical job processing times

Cites Work

• Unnamed Item
• Efficient scheduling algorithms for a single batch processing machine
• Scheduling a batching machine
• Preemptive scheduling with rejection
• Approximation algorithms in batch processing
• On-line uniform machine scheduling with rejection
• A PTAS for semiconductor burn-in scheduling
• Minimizing makespan with release times on identical parallel batching machines
• On-line scheduling of unit time jobs with rejection: Minimizing the total completion time
• Minimizing makespan in batch machine scheduling
• Scheduling with batching: A review
• Scheduling with rejection and non-identical job arrivals
• Minimizing makespan on a single batching machine with release times and non-identical job sizes
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Minimizing makespan on a single batch processing machine with dynamic job arrivals
• Multiprocessor Scheduling with Rejection
• Algorithmic Applications in Management
• Theory and Applications of Models of Computation
• Algorithms and Data Structures
• Preemptive multiprocessor scheduling with rejection

This page was built for publication: A PTAS for parallel batch scheduling with rejection and dynamic job arrivals