Lazy local search meets machine scheduling

DOI10.1137/17M1139175MaRDI QIDQ5237306zbMATH OpenOpenAlexWikidataFDO

Authors Chidambaram Annamalai

Publication date 17 October 2019

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

local searchschedulingunrelated parallel machinesconfiguration of linear programs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Abstract: We study the restricted case of Scheduling on Unrelated Parallel Machines. In this problem, we are given a set of jobs $J$ with processing times $p_j$ and each job may be scheduled only on some subset of machines $S_{j}subseteqM$. The goal is to find an assignment of jobs to machines to minimize the time by which all jobs can be processed. In a seminal paper, Lenstra, Shmoys, and Tardos designed an elegant $2$-approximation for the problem in 1987. The question of whether approximation algorithms with better guarantees exist for this classic scheduling problem has since remained a source of mystery. In recent years, with the improvement of our understanding of Configuration LPs, it now appears an attainable goal to design such an algorithm. Our main contribution is to make progress towards this goal. When the processing times of jobs are either $1$ or $epsilonin(0,1)$, we design an approximation algorithm whose guarantee tends to $1+sqrt3/2approx1.8660254,$ for the interesting cases when $epsilono0$. This improves on the $2-epsilo{n}_0$ guarantee recently obtained by Chakrabarty, Khanna, and Li for some constant $epsilo{n}_0>0$.

Recommendations

• Approximation algorithms for scheduling unrelated parallel machines
• On \((1,\varepsilon)\)-restricted assignment makespan minimization
• A quasi-polynomial approximation for the restricted assignment problem

Cites work

• scientific article; zbMATH DE number 5764783 (Why is no real title available?)
• scientific article; zbMATH DE number 5764883 (Why is no real title available?)
• A quasi-polynomial approximation for the restricted assignment problem
• Approximation algorithms for scheduling unrelated parallel machines
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• Introduction to algorithms.
• New constructive aspects of the Lovász local lemma
• On \((1,\varepsilon)\)-restricted assignment makespan minimization
• On the configuration-LP of the restricted assignment problem
• Quasi-polynomial local search for restricted max-min fair allocation
• Santa claus meets hypergraph matchings
• The Santa Claus problem
• The design of approximation algorithms

Cited in

(5)

• An efficient local search with noising strategy for Google machine reassignment problem
• On \((1,\varepsilon)\)-restricted assignment makespan minimization
• Better trees for Santa Claus
• A quasi-polynomial approximation for the restricted assignment problem
• scientific article; zbMATH DE number 49601 (Why is no real title available?)

This page was built for publication: Lazy local search meets machine scheduling

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