Minimizing mean completion time in a batch processing system

DOI10.1007/S00453-003-1053-2MaRDI QIDQ1879250zbMATH OpenOpenAlexFDO

Authors Xiaotie Deng, Haodi Feng, Pixing Zhang, Hong Zhu, Yuzhong Zhang

Publication date 22 September 2004

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-003-1053-2

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Review text

We consider batch processing jobs to minimize the mean completion time. A batch processing machine can handle up to \(B\) jobs simultaneously. Each job is represented by an arrival time and a processing time. Jobs processed in a batch have the same completion time, i.e., their common starting time plus the processing time of their longest job. For batch processing, non-preemptive scheduling is usually required and we discuss this case. The batch processing problem reduces to the ordinary uniprocessor system scheduling problem if \(B=1\). We focus on the other extreme case \(B=+\infty\). Even for this seemingly simple extreme case, we are able to show that the problem is NP-hard for the weighted version. In addition, we establish a polynomial time algorithm for a special case when there are only a constant number of job processing times. Finally, we give a polynomial time approximation scheme for the general case.

Recommendations

• Batch-processing scheduling with setup times
• Minimizing makespan in batch machine scheduling
• scientific article; zbMATH DE number 2080976
• A PTAS FOR MINIMIZING TOTAL COMPLETION TIME OF BOUNDED BATCH SCHEDULING
• scientific article; zbMATH DE number 2081006

Cited in

(19)

• An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan
• Scheduling jobs with release dates on parallel batch processing machines
• On-line scheduling of unit time jobs with rejection on uniform machines
• On-line scheduling a batch processing system to minimize total weighted job completion time
• Batch-processing scheduling with setup times
• A PTAS for semiconductor burn-in scheduling
• Unbounded parallel-batch scheduling with drop-line tasks
• Minimizing total completion time on a batch processing machine with job families
• Minimizing total completion time on a batching machine with job processing time compatibilities
• No-wait scheduling problems with batching machines
• A PTAS FOR MINIMIZING TOTAL COMPLETION TIME OF BOUNDED BATCH SCHEDULING
• Minimizing makespan on a single batch processing machine with dynamic job arrivals
• scientific article; zbMATH DE number 1559487 (Why is no real title available?)
• scientific article; zbMATH DE number 2086930 (Why is no real title available?)
• Unbounded parallel-batch scheduling to minimize the total weighted tardy span
• Single machine batch scheduling with release times
• Scheduling an unbounded batching machine with job processing time compatibilities
• On-line scheduling with rejection on identical parallel machines
• The coordination of transportation and batching scheduling

This page was built for publication: Minimizing mean completion time in a batch processing system

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