Improved analysis of an algorithm for the coupled task problem with UET jobs

DOI10.1016/j.orl.2008.11.002zbMath1159.90398OpenAlexW2089381285MaRDI QIDQ1015304

Gábor Galambos, Marcus Oswald, Gerhard Reinelt, József Békési

Publication date: 7 May 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2008.11.002

zbMATH Keywords

schedulingapproximation algorithmscoupled tasks

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Scheduling of coupled tasks with unit processing times, A semidefinite optimization approach to the target visitation problem, Identical coupled task scheduling: polynomial complexity of the cyclic case, Coupled task scheduling with exact delays: literature review and models, A first fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays

Cites Work

• An exact algorithm for scheduling identical coupled tasks
• Approximation algorithms for UET scheduling problems with exact delays
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Scheduling coupled tasks
• On the complexity of coupled-task scheduling