Minimizing the makespan on a single parallel batching machine

DOI10.1016/J.TCS.2009.12.008MaRDI QIDQ2268874zbMATH OpenOpenAlexFDO

Authors Shenpeng Lu, Haodi Feng, Xiuqian Li

Publication date 9 March 2010

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

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

zbMATH Keywords

job sizeparallel batchingPTASrejectionrelease datescheduling

Mathematics Subject Classification ID

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

Recommendations

• Scheduling a single machine with parallel batching to minimize makespan and total rejection cost
• Bounded single-machine parallel-batch scheduling with release dates and rejection
• The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan
• Approximation algorithms for single machine parallel-batch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold
• New approximation algorithms for machine scheduling with rejection on single and parallel machine

Cites work

• Bin packing problems with rejection penalties and their dual problems
• Bin Packing with Rejection Revisited
• Bounded single-machine parallel-batch scheduling with release dates and rejection
• Integrating Scheduling with Batching and Lot-Sizing: A Review of Algorithms and Complexity
• Minimizing makespan on a single batch processing machine with nonidentical job sizes
• Minimizing makespan on a single batching machine with release times and non-identical job sizes
• Multiprocessor Scheduling with Rejection
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Preemptive multiprocessor scheduling with rejection
• Preemptive scheduling with rejection
• Scheduling a batching machine
• Scheduling a single batch processing machine with non-identical job sizes
• Scheduling Groups of Jobs on a Single Machine
• Scheduling linear deteriorating jobs with rejection on a single machine
• Scheduling with batching: A review
• Scheduling with rejection and non-identical job arrivals
• Single machine batch scheduling with rejection to minimize makespan
• Single machine scheduling with release dates and rejection
• The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan
• Theory and Applications of Models of Computation

Cited in

(11)

• Minimizing makespan in batch machine scheduling
• Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine
• Minimizing makespan on a single batching machine with release times and non-identical job sizes
• Scheduling a single machine with parallel batching to minimize makespan and total rejection cost
• A branch and bound based heuristic for makespan minimization of washing operations in hospital sterilization services
• Single machine batch scheduling with rejection to minimize makespan
• Determining optimal sizes of bounded batches with rejection via quadratic min-cost flow
• Approximation algorithms for single machine parallel-batch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold
• Penalty cost constrained identical parallel machine scheduling problem
• The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan
• The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan

This page was built for publication: Minimizing the makespan on a single parallel batching machine

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2268874)