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

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) 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

(26)

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

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)