Approximation algorithms for UET scheduling problems with exact delays

DOI10.1016/j.orl.2006.09.006zbMath1149.90337MaRDI QIDQ2457273

A. A. Ageev, Alexei E. Baburin

Publication date: 30 October 2007

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

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

zbMATH Keywords

makespan; flow shop; Approximation algorithm; scheduling problem; exact delay

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

Related Items

A 3/2-Approximation for the Proportionate Two-Machine Flow Shop Scheduling with Minimum Delays, Minimizing Total Completion Time in Two-Machine Flow Shops with Exact Delays, A binary search algorithm for the general coupled task scheduling problem, Approximation algorithms for coupled task scheduling minimizing the sum of completion times, A branch-and-bound algorithm for the coupled task problem, Scheduling of coupled tasks with unit processing times, Scheduling coupled-operation jobs with exact time-lags, Identical coupled task scheduling: polynomial complexity of the cyclic case, Minimizing total completion time in two-machine flow shops with exact delays, Improved analysis of an algorithm for the coupled task problem with UET jobs, A first fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays, Coupled task scheduling with time-dependent processing times, Approximating the 2-machine flow shop problem with exact delays taking two values, Coupled task scheduling with exact delays: literature review and models, Two-machine flowshop scheduling problem with coupled-operations, Two machines flow shop with reentrance and exact time lag

Cites Work

• Unnamed Item
• Interleaving two-phased jobs on a single machine
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Radar pulse interleaving for multi‐target tracking
• On the complexity of coupled-task scheduling