Best semi-online algorithms for unbounded parallel batch scheduling

DOI10.1016/J.DAM.2011.01.003zbMath1213.68714OpenAlexW2004975914MaRDI QIDQ534351

Yong-Cai Geng, Sumit K. Garg

Publication date: 17 May 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.01.003

zbMATH Keywords

competitive ratioonline algorithmparallel batch schedulinginformation in advance

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)

Related Items (8)

A best possible on-line algorithm for scheduling on uniform parallel-batch machines ⋮ Semi-online scheduling: a survey ⋮ Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead ⋮ 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 incompatible unit-length job families with lookahead ⋮ Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time ⋮ Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan

Cites Work

• Semi-on-line multiprocessor scheduling with given total processing time
• A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan
• Online scheduling in a parallel batch processing system to minimize makespan using restarts
• Scheduling a batching machine
• Approximation algorithms in batch processing
• On-line scheduling algorithms for a batch machine with finite capacity
• Semi-on-line problems on two identical machines with combined partial information
• Minimizing makespan in batch machine scheduling
• Complexity results for single-machine problems with positive finish-start time-lags
• On-line algorithms for minimizing makespan on batch processing machines
• Online Scheduling with Known Arrival Times
• Efficient Algorithms for Scheduling Semiconductor Burn-In Operations
• Minimizing makespan on a single batch processing machine with dynamic job arrivals
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• Semi-online scheduling with decreasing job sizes

This page was built for publication: Best semi-online algorithms for unbounded parallel batch scheduling