Online scheduling in a parallel batch processing system to minimize makespan using restarts

DOI10.1016/j.tcs.2006.12.040zbMath1162.90452MaRDI QIDQ1022602

Tian Ji, Ruyan Fu, Jinjiang Yuan, Yanpei Liu

Publication date: 22 June 2009

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

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

zbMATH Keywords

competitive ratio; single machine scheduling; online algorithm; restart; parallel batch

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90B35: Deterministic scheduling theory in operations research

Related Items

Online parallel-batch scheduling to minimize total weighted completion time on single unbounded machine, Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart, Online over time scheduling on parallel-batch machines: a survey, Best semi-online algorithms for unbounded parallel batch scheduling, A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan, On-line scheduling on a batch machine to minimize makespan with limited restarts, On-line integrated production-distribution scheduling problems with capacitated deliveries, Online scheduling with delivery time on a bounded parallel batch machine with limited restart, Online batch scheduling with kind release times and incompatible families to minimize makespan, Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart, Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan, Semi-online two-level supply chain scheduling problems, Optimal Semi-Online Algorithm for Scheduling on Two Parallel Batch Processing Machines, OPTIMAL SEMI-ONLINE ALGORITHM FOR SCHEDULING ON A BATCH PROCESSING MACHINE

Cites Work

• Approximation algorithms in batch processing
• Restarts can help in the on-line minimization of the maximum delivery time on a single machine
• On-line scheduling algorithms for a batch machine with finite capacity
• Lower bounds for on-line single-machine scheduling.
• Scheduling with machine cost and rejection
• Separating online scheduling algorithms with the relative worst order ratio
• On-line algorithms for minimizing makespan on batch processing machines
• Minimizing makespan on a single batch processing machine with dynamic job arrivals
• Multiprocessor Scheduling with Rejection
• Minimizing the total completion time on-line on a single machine, using restarts
• On-line scheduling on a single machine: Maximizing the number of early jobs