An exact algorithm for scheduling identical coupled tasks

DOI10.1007/S001860300328MaRDI QIDQ1762669zbMATH OpenOpenAlexFDO

Authors Dino Ahr, József Békési, Gábor Galambos, Marcus Oswald, Gerhard Reinelt

Publication date 11 February 2005

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001860300328

Mathematics Subject Classification ID

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

Recommendations

• Approximating coupled-task scheduling problems with equal exact delays
• An improved approximation algorithm for the coupled-task scheduling problem with equal exact delays
• Exact algorithms for scheduling programs with shared tasks
• A note on scheduling identical coupled tasks in logarithmic time
• Identical coupled task scheduling: polynomial complexity of the cyclic case
• New characterizations for the identical coupled tasks scheduling problem
• An exact algorithm for the identical parallel machine scheduling problem.
• Scheduling coupled tasks with exact delays for minimum total job completion time
• Approximation algorithms for coupled task scheduling minimizing the sum of completion times
• On the complexity of coupled-task scheduling

Cited in

(27)

• Improved analysis of an algorithm for the coupled task problem with UET jobs
• The coupled unit-time operations problem on identical parallel machines with respect to the makespan
• A first fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays
• Scheduling coupled tasks with exact delays for minimum total job completion time
• Coupled task scheduling with time-dependent processing times
• Coupled task scheduling with exact delays: literature review and models
• Two-machine flowshop scheduling problem with coupled-operations
• Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor
• A note on scheduling coupled tasks for minimum total completion time
• Two machines flow shop with reentrance and exact time lag
• Polynomial-time algorithms for scheduling problem for coupled-tasks in presence of treatment tasks
• Some complexity and approximation results for coupled-tasks scheduling problem according to topology
• Complexity of scheduling of coupled tasks with chains precedence constraints and constant even length of the gap
• Approximating coupled-task scheduling problems with equal exact delays
• Coupled-tasks in presence of bipartite compatibilities graphs
• A branch-and-bound algorithm for the coupled task problem
• New algorithms for coupled tasks scheduling - a survey
• Scheduling of coupled tasks with unit processing times
• New characterizations for the identical coupled tasks scheduling problem
• A binary search algorithm for the general coupled task scheduling problem
• Scheduling coupled tasks on parallel identical machines
• New efficient algorithms for the two-machine no-wait chain-reentrant shop problem
• Scheduling coupled-operation jobs with exact time-lags
• A coupled task scheduling approximation algorithm for minimizing the sum of completion times
• Identical coupled task scheduling: polynomial complexity of the cyclic case
• Scheduling of coupled tasks and one-machine no-wait robotic cells
• A note on scheduling identical coupled tasks in logarithmic time

This page was built for publication: An exact algorithm for scheduling identical coupled tasks

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