Some complexity and approximation results for coupled-tasks scheduling problem according to topology

DOI10.1051/ro/2016034zbMath1353.90058arXiv1706.02214OpenAlexW3103056982MaRDI QIDQ2954345

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

Publication date: 12 January 2017

Published in: RAIRO - Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

complexitypolynomial-time approximation algorithmcoupled-task scheduling model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25) Discrete mathematics in relation to computer science (68Rxx)

Related Items

Coupled task scheduling with exact delays: literature review and models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity and approximation for precedence constrained scheduling problems with large communication delays
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• A 3/4-approximation algorithm for multiple subset sum
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• A PTAS for the multiple subset sum problem with different knapsack capacities
• An exact algorithm for scheduling identical coupled tasks
• Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor
• The Multiple Subset Sum Problem
• Polynomial-time algorithms for scheduling problem for coupled-tasks in presence of treatment tasks
• Scheduling coupled tasks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Maximum matching and a polyhedron with 0,1-vertices
• On the complexity of coupled-task scheduling