Bag-Of-Tasks Scheduling on Related Machines

DOI10.4230/LIPICS.APPROX/RANDOM.2021.3arXiv2107.06216OpenAlexW3213248699MaRDI QIDQ6070373

Amit Kumar, Sahil Singla, Anupam Gupta

Publication date: 20 November 2023

Abstract: We consider online scheduling to minimize weighted completion time on related machines, where each job consists of several tasks that can be concurrently executed. A job gets completed when all its component tasks finish. We obtain an $O(K^{3}lo{g}^{2}K)$-competitive algorithm in the non-clairvoyant setting, where $K$ denotes the number of distinct machine speeds. The analysis is based on dual-fitting on a precedence-constrained LP relaxation that may be of independent interest.

Full work available at URL: https://arxiv.org/abs/2107.06216

zbMATH Keywords

schedulingapproximation algorithmsrelated machinesbag-of-tasks

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Recommendations

• Unnamed Item 👍 👎
• Unnamed Item 👍 👎
• Interval scheduling on related machines 👍 👎
• Approximation schemes for scheduling on uniformly related and identical parallel machines 👍 👎
• Bounded Parallel-Batch Scheduling on Unrelated Parallel Machines 👍 👎
• Scheduling Concurrent Bag-of-Tasks Applications on Heterogeneous Platforms 👍 👎
• Scheduling tasks on unrelated machines: large neighborhood improvement procedures 👍 👎
• Approximating scheduling unrelated parallel machines in parallel 👍 👎

This page was built for publication: Bag-Of-Tasks Scheduling on Related Machines