A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan

DOI10.1007/S10951-010-0172-2MaRDI QIDQ657251zbMATH OpenOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 16 January 2012

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-010-0172-2

zbMATH Keywords

competitive ratioonline algorithmrestartparallel-batch scheduling

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Online scheduling in a parallel batch processing system to minimize makespan using restarts
• Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan
• Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart
• Online scheduling with delivery time on a bounded parallel batch machine with limited restart
• On-line scheduling on a batch machine to minimize makespan with limited restarts

Cites work

• Approximation algorithms in batch processing
• Lower bounds for on-line single-machine scheduling.
• Minimizing makespan on a single batch processing machine with dynamic job arrivals
• Minimizing the total completion time on-line on a single machine, using restarts
• On-line algorithms for minimizing makespan on batch processing machines
• On-line scheduling algorithms for a batch machine with finite capacity
• On-line scheduling on a batch machine to minimize makespan with limited restarts
• On-line scheduling on a single machine: Maximizing the number of early jobs
• Online scheduling in a parallel batch processing system to minimize makespan using restarts
• Restarts can help in the on-line minimization of the maximum delivery time on a single machine
• Scheduling a batching machine

Cited in

(18)

• On-line scheduling on a batch machine to minimize makespan with limited restarts
• On-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs
• Online single machine scheduling to minimize the maximum starting time
• Best semi-online algorithms for unbounded parallel batch scheduling
• Online parallel-batch scheduling to minimize total weighted completion time on single unbounded machine
• Online scheduling in a parallel batch processing system to minimize makespan using restarts
• Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart
• Online scheduling on a parallel batch machine with delivery times and limited restarts
• Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time
• Online scheduling with delivery time on a bounded parallel batch machine with limited restart
• Online makespan minimization: the power of restart
• Minimizing the total completion time on-line on a single machine, using restarts
• Online batch scheduling with kind release times and incompatible families to minimize makespan
• Online over time scheduling on parallel-batch machines: a survey
• Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart
• Online scheduling with restart on parallel machines
• Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan
• Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan

This page was built for publication: A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan

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