Lazy local search meets machine scheduling

DOI10.1137/17M1139175zbMATH Open1439.90030arXiv1611.07371OpenAlexW2981057370WikidataQ127022609 ScholiaQ127022609MaRDI QIDQ5237306FDOQ5237306

Authors: Chidambaram Annamalai 

Publication date: 17 October 2019

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

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$.

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

Recommendations

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

zbMATH Keywords

local searchschedulingunrelated parallel machinesconfiguration of linear programs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• On \((1,\varepsilon)\)-restricted assignment makespan minimization
• An efficient local search with noising strategy for Google machine reassignment problem
• Better trees for Santa Claus
• A quasi-polynomial approximation for the restricted assignment problem
• Title not available (Why is that?)

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)