Identical coupled task scheduling: polynomial complexity of the cyclic case

DOI10.1007/s10951-015-0438-9zbMath1333.90047OpenAlexW2174653384MaRDI QIDQ906560

Gerd Finke, Vassilissa Lehoux-Lebacque, Nadia Brauner

Publication date: 22 January 2016

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-015-0438-9

zbMATH Keywords

polynomial complexitycyclic schedulinghigh-multiplicitycoupled task

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (7)

A binary search algorithm for the general coupled task scheduling problem ⋮ The coupled task scheduling problem: an improved mathematical program and a new solution algorithm ⋮ Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor ⋮ Coupled task scheduling with exact delays: literature review and models ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ Minimizing the waiting time for a one-way shuttle service ⋮ Coupled task scheduling with time-dependent processing times

Cites Work

• Scheduling of coupled tasks with unit processing times
• Scheduling of coupled tasks and one-machine no-wait robotic cells
• A note on scheduling identical coupled tasks in logarithmic time
• Improved analysis of an algorithm for the coupled task problem with UET jobs
• A characterization of the minimum cycle mean in a digraph
• Scheduling for a multifunction phased array radar system
• Modelling for the control of a complex radar system
• An exact algorithm for scheduling identical coupled tasks
• Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor
• Approximation algorithms for UET scheduling problems with exact delays
• Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags
• A framework for the complexity of high-multiplicity scheduling problems
• Scheduling coupled tasks
• Radar pulse interleaving for multi‐target tracking
• Multiplicity and complexity issues in contemporary production scheduling
• On the complexity of coupled-task scheduling

This page was built for publication: Identical coupled task scheduling: polynomial complexity of the cyclic case