Identical coupled task scheduling: polynomial complexity of the cyclic case

DOI10.1007/S10951-015-0438-9MaRDI QIDQ906560zbMATH OpenOpenAlexFDO

Authors Vassilissa Lehoux-Lebacque, Gerd Finke, 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)

Recommendations

• A note on scheduling identical coupled tasks in logarithmic time
• Scheduling of coupled tasks and one-machine no-wait robotic cells
• An exact algorithm for scheduling identical coupled tasks
• Scheduling of coupled tasks with unit processing times
• New algorithms for coupled tasks scheduling - a survey

Cites work

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

Cited in

(16)

• New characterizations for the identical coupled tasks scheduling problem
• A binary search algorithm for the general coupled task scheduling problem
• A note on scheduling identical coupled tasks in logarithmic time
• An exact algorithm for scheduling identical coupled tasks
• Parameterized complexity of a coupled-task scheduling problem
• Coupled task scheduling with time-dependent processing times
• The coupled task scheduling problem: an improved mathematical program and a new solution algorithm
• Coupled task scheduling with exact delays: literature review and models
• New algorithms for coupled tasks scheduling - a survey
• scientific article; zbMATH DE number 850294 (Why is no real title available?)
• Scheduling of coupled tasks and one-machine no-wait robotic cells
• Scheduling coupled tasks on parallel identical machines
• Complexity of scheduling of coupled tasks with chains precedence constraints and constant even length of the gap
• Minimizing the waiting time for a one-way shuttle service
• Polynomial-time algorithms for scheduling problem for coupled-tasks in presence of treatment tasks
• Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906560)