Approximation algorithms for UET scheduling problems with exact delays

DOI10.1016/j.orl.2006.09.006zbMath1149.90337OpenAlexW2060208047MaRDI 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

makespanflow shopApproximation algorithmscheduling problemexact delay

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (17)

Scheduling of coupled tasks with unit processing times ⋮ Approximating the 2-machine flow shop problem with exact delays taking two values ⋮ A binary search algorithm for the general coupled task scheduling problem ⋮ A branch-and-bound algorithm for the coupled task problem ⋮ Approximation algorithms for coupled task scheduling minimizing the sum of completion times ⋮ The coupled task scheduling problem: an improved mathematical program and a new solution algorithm ⋮ Identical coupled task scheduling: polynomial complexity of the cyclic case ⋮ Scheduling coupled-operation jobs with exact time-lags ⋮ A 3/2-Approximation for the Proportionate Two-Machine Flow Shop Scheduling with Minimum Delays ⋮ Coupled task scheduling with exact delays: literature review and models ⋮ Minimizing total completion time in two-machine flow shops with exact delays ⋮ Two machines flow shop with reentrance and exact time lag ⋮ 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 ⋮ Two-machine flowshop scheduling problem with coupled-operations ⋮ Minimizing Total Completion Time in Two-Machine Flow Shops with Exact Delays

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

This page was built for publication: Approximation algorithms for UET scheduling problems with exact delays