Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor

DOI10.1007/s10951-010-0193-xzbMath1280.90072arXiv1706.02202OpenAlexW2087854645MaRDI QIDQ2434251

Rodolphe Giroudeau, Gilles Simonin, Benoit Darties, Jean-Claude Konig

Publication date: 5 February 2014

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

Full work available at URL: https://arxiv.org/abs/1706.02202

zbMATH Keywords

complexitypolynomial-time approximationcompatibility graphcoupled-tasks

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (8)

Coupled-Tasks in Presence of Bipartite Compatibilities Graphs ⋮ A binary search algorithm for the general coupled task scheduling problem ⋮ Some complexity and approximation results for coupled-tasks scheduling problem according to topology ⋮ The coupled task scheduling problem: an improved mathematical program and a new solution algorithm ⋮ Identical coupled task scheduling: polynomial complexity of the cyclic case ⋮ Coupled task scheduling with exact delays: literature review and models ⋮ Scheduling coupled tasks with exact delays for minimum total job completion time ⋮ Coupled task scheduling with time-dependent processing times

Cites Work

• Unnamed Item
• Unnamed Item
• Identical coupled task scheduling: polynomial complexity of the cyclic case
• Linear algorithm for optimal path cover problem on interval graphs
• Optimal covering of cacti by vertex-disjoint paths
• A linear algorithm for the Hamiltonian completion number of a tree
• Optimal path cover problem on block graphs and bipartite permutation graphs
• A time-optimal solution for the path cover problem on cographs.
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
• An exact algorithm for scheduling identical coupled tasks
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• 8/7-approximation algorithm for (1,2)-TSP
• Scheduling coupled tasks
• Advances on the Hamiltonian Completion Problem
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• On the complexity of coupled-task scheduling

This page was built for publication: Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor