Identical coupled task scheduling: polynomial complexity of the cyclic case

DOI10.1007/S10951-015-0438-9zbMATH Open1333.90047OpenAlexW2174653384MaRDI QIDQ906560FDOQ906560

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Scheduling coupled tasks on parallel identical machines
• Scheduling of coupled tasks and one-machine no-wait robotic cells
• 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)