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

DOI10.1016/j.tcs.2006.12.040zbMath1162.90452OpenAlexW2061287273MaRDI 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 ratiosingle machine schedulingonline algorithmrestartparallel batch

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

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 ⋮ Optimal Semi-Online Algorithm for Scheduling on Two Parallel Batch Processing Machines ⋮ Online scheduling with delivery time on a bounded parallel batch machine with limited restart ⋮ Semi-online two-level supply chain scheduling problems ⋮ 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 ⋮ Online over time scheduling on parallel-batch machines: a survey ⋮ 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 ⋮ Best semi-online algorithms for unbounded parallel batch scheduling ⋮ OPTIMAL SEMI-ONLINE ALGORITHM FOR SCHEDULING ON A BATCH PROCESSING MACHINE ⋮ Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan ⋮ On-line integrated production-distribution scheduling problems with capacitated deliveries

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